138  Street Numbers
Moderator: Board moderators
Related Math
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.
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.

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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
#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

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
For solving this problem is best to learn a tiny bit of math. Here's a
good reference:
http://wwwgap.dcs.stand.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
...
good reference:
http://wwwgap.dcs.stand.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.
My captain is Stanley Tweedle. I blow up planets for him.
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
David
138  Street Numbers
Problem 138 states
Also the problem gives the first two such pairs 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.Output will consist of 10 lines each containing a pair of numbers...
Also the problem gives the first two such pairs of numbers:
But I think that 1 1 should really be the first solution (i.e., there's only her house on the street)6 8
35 49
problem 138
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?
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?
check :n^2=m*(m+1)/2
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
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

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Help understanding P 138 (street numbers)
I don't understand at all p 138.
Can anyone help me ?
Thanks
Can anyone help me ?
Thanks

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Problem 138
Thanks,
I'll Try it.
I'll Try it.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Street Number
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
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