138 - Street Numbers

[oker]

Thank you!

[Cubist]

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]

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]

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]

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]

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]

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
...

[dawynn]

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]

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]

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]

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]

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

Thanks

[FlyDeath]

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]

Thanks,
I'll Try it.

[Red Scorpion]

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