## 10569 - Number Theory

Moderator: Board moderators

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
2one & only:
let, f=an+1,

so, 3an^2+3an+1=a1+a2+a3+.....+an-1

choose randomly value for a1 to an-1, check that you get a integer solution for an
How do you know (I mean can you prove) that there is an integer solution to the equation?

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
I used the wrong thread for this post. So here it is again:

2one & only:
let, f=an+1,

so, 3an^2+3an+1=a1+a2+a3+.....+an-1

choose randomly value for a1 to an-1, check that you get a integer solution for an
How do you know (I mean can you prove) that there is an integer solution to the equation?

one & only
New poster
Posts: 7
Joined: Mon Oct 13, 2003 8:33 pm
Location: in front of pc (sust, bangladesh)
Contact:
No, i dont have any mathematical prove that i always get an iteger solution. But my mathematical intution says that i always get an interger solution. If someone have any mathematical prove please post here.

zubair
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm
2 one & only,

your algo is interesting. but how can i check the unsuccessful input?
To make the program more efficient choose the value for a[n-1] from
i= 1 to 220 where the value of i should not chosen for a1 to an-2.
i did not get this point. can u please explain.
zubair-CUET old sailor

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm
Similar to what one & only pointed out, we can take advantage of cubic quadruples similar to pythagorean triples. The best quadruple that I have found is:

3 4 5 = 6 (exponents have been omitted for clarity)

6 8 10 = 12
12 16 20 = 24
24 32 40 = 48
and so on, doubling the previous equation each time.

If you notice, these have a nice relationship, the previous answer equals the first number in the next line. We can use these equations and simply substitute until we fill the desired number of numbers.

If n is odd:
n = 3, 3 4 5 = 6
n = 5, 3 4 5 8 10 = 12
n = 7, 3 4 5 8 10 16 20 = 24
n = 9, 3 4 5 8 10 16 20 32 40 = 48
and so on.

If n is even start off with:
4 7 8 17 = 18 (base quintuple)
18 24 30 = 36 (base quadruple multiplied by 6)
36 48 60 = 72
72 96 120 = 144
and so on doubling the previous quadruple.

Using substitution:
n = 4, 4 7 8 17 = 18
n = 6, 4 7 8 17 (24 30 = 36)
n = 8, 4 7 8 17 24 30 (48 60 = 72)
n = 10, 4 7 8 17 24 30 48 60 (96 120 = 144)
and so on.

Two nice features of this algorithm are that it is O(n) and that you only need to use long 64-bit integers since the numbers double every odd or even length and the length is at most 100.
LL Cool Jay
LL Cool Jay
The Formula Wizard
Jason Winokur