10569 - Number Theory

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

Moderator: Board moderators

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by 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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by 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
New poster
Posts: 7
Joined: Mon Oct 13, 2003 8:33 pm
Location: in front of pc (sust, bangladesh)
Contact:

Post by 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
New poster
Posts: 17
Joined: Fri Apr 18, 2003 2:22 pm

Post by 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.
zubair-CUET old sailor

jaywinyeah
New poster
Posts: 19
Joined: Sun Aug 17, 2003 10:40 pm

Post by 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
LL Cool Jay
The Formula Wizard
Jason Winokur

Post Reply

Return to “Volume 105 (10500-10599)”