10569 - Number Theory

[BiK]

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]

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]

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]

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.

[jaywinyeah]

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)

This yields other quadrupals:
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