138 - Street Numbers

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

Post by oker » Wed Apr 17, 2002 2:52 am

Thank you!

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

Related Math

Post by Cubist » Sun Jun 09, 2002 5:28 am

See the topics "quadratic forms" and "continued fractions". The key is
finding base solutions; from those you have a nice recursion that
generates others.
--
Chris Long, Mathematics Department, Rutgers University

It is pitch black. You are likely to be eaten by a grue.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn » Sat Jun 22, 2002 2:15 pm

Yes, the brute force solution sounds great! But it doesn't execute well. Problem -- variables can't be made large enough. I was using unsigned long integers and didn't get the same solution as above, because the sums computed blew out the long integers! Some kind of formula is required here.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat Jun 22, 2002 11:59 pm

dawynn: You mean you have intermediate values that exceed the range, right? Because the resulting numbers fit perfectly, even in "int". So it depends on how you get there, maybe we could see how you do it?

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn » Sun Jun 23, 2002 2:33 pm

As stated, I went with the brute force method:
#include <iostream.h>
#include <iomanip.h>

int main()
{
unsigned long LowTot = 10, House = 5, High = 7, HighTot = 13, Printouts = 0;

while (Printouts < 10)
{
while (HighTot < LowTot)
{
High ++;
HighTot += High;
}

if (HighTot == LowTot)
{
cout << setw(10) << House << setw(10) << High << endl;
Printouts++;
}

LowTot += House;
House ++;
HighTot -= House;

while (LowTot < HighTot)
{
LowTot += House;
House ++;
HighTot -= House;
}
}
}

It can produce correct results up through house number 40391. After that, the output is incorrect. I'm guessing because the sums are too large and blowing out the long integer. The rest of my output is:
153706 253832
319959 680033
1554453142505116215
2457989524173149055
Yes, those last two are a 9 digit number followed by a 10 digit number.

David

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sun Jun 23, 2002 11:44 pm

Ok, I see... you're right, the sums are of course out of int-range. What you could do is use "long long" or "double", both should work. Don't use "long", because that's usually the same as "int", even though they have different names.

Cubist
New poster
Posts: 17
Joined: Sun May 26, 2002 7:56 am
Location: San Diego, CA

Post by Cubist » Mon Jun 24, 2002 4:03 am

For solving this problem is best to learn a tiny bit of math. Here's a
good reference:

http://www-gap.dcs.st-and.ac.uk/~histor ... /Pell.html

Basically, if you're trying to solve an equation like

m^2 - d*n^2 = 1

where d is squarefree, all you need to do is find an initial (smallest)
solution m_1, n_1, then as m_0=1, n_0=0 is always a solution you
generate all of them via the recursion:

m_{i+2} = 2*m_1*m_{i+1} - m_i
n_{i+2} = 2*m_1*n_{i+1} - n_i

For example, if d=2, then the smallest positive solution is
m_1=3, n_1=2, giving the recursion:

m_{i+2} = 6*m_{i+1} - m_i
n_{i+2} = 6*n_{i+1} - n_i

giving solutions

1 0
3 2
17 12
99 70
...
Chris Long, San Diego Padres, 100 Park Boulevard, San Diego CA

My captain is Stanley Tweedle. I blow up planets for him.

dawynn
New poster
Posts: 47
Joined: Fri Jun 21, 2002 3:08 pm

Post by dawynn » Mon Jun 24, 2002 1:02 pm

If you're not looking for record times, brute force can win the day, despite my previous postings. But, understand that if using integer variables, you will not be able to keep running totals. My brute force solution ran (accepted) in just over 2 seconds, with some simple modifications. Good luck.

David

Ed
New poster
Posts: 1
Joined: Sun Nov 24, 2002 4:53 am

138 - Street Numbers

Post by Ed » Sun Nov 24, 2002 5:00 am

Problem 138 states
Output will consist of 10 lines each containing a pair of numbers...
I imagine that the problem is really asking for a list of the ten lowest house numbers in order, but it doesn't specifically ask for it.

Also the problem gives the first two such pairs of numbers:
6 8
35 49
But I think that 1 1 should really be the first solution (i.e., there's only her house on the street)

imorpheus
New poster
Posts: 1
Joined: Wed Nov 27, 2002 1:37 am

problem 138

Post by imorpheus » Wed Nov 27, 2002 9:18 pm

I have the same problem... I can get 10 valid lines...
My algorithm is pretty slow... but once I get 10 valid lines I simply put them in the program.
I've tested all the lines and I'me sure they obey the required property,
But I get a WA

Am I missing something?

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

check :n^2=m*(m+1)/2

Post by yiuyuho » Sat Nov 30, 2002 1:40 am

check that for all your 10 outputs n,m
that n^2=m*(m+1)/2

1 1 should not be an output since in the problem, she was able to "walk pass" some houses, if 1 1 that she can'y "pass" any house

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Help understanding P 138 (street numbers)

Post by Red Scorpion » Sat Dec 21, 2002 8:47 am

I don't understand at all p 138.
Can anyone help me ?

Thanks :oops:

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Sat Dec 21, 2002 2:07 pm

The problem is that you have to find out 10 pairs of n,m which 1+2+3+4+.....+n=n+(n+1)+(n+2)+.....+m
An example is 6 and 8.1+2+3+4+5+6=21=6+7+8
You need to find out the first 10 pairs that satisfy this condition.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Problem 138

Post by Red Scorpion » Mon Dec 23, 2002 5:08 am

Thanks,
I'll Try it.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Street Number

Post by Red Scorpion » Wed Jan 08, 2003 7:17 am

I know that is Diophantine Equation :
x(x+1) = 2Y*Y

but, how can I solved that equation (I try every x and y, and got time limit).

Can anyone help me?

Thanks :cry:

Post Reply

Return to “Volume 1 (100-199)”