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

abc
New poster
Posts: 15
Joined: Sun Dec 15, 2002 2:51 pm

10569 Number Theory

Post by abc » Tue Oct 14, 2003 11:59 pm

Is there a solution for f = 7?

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

10569 - Number Theory

Post by Maarten » Tue Oct 14, 2003 11:59 pm

For the input

Code: Select all

30
1
....
30
my program gives the output below.
I checked with mathematica and the answers are correct. Why do I still get WA ?? Anyone please help me!

Code: Select all

Case 1: 1 1
Case 2: -1 0 0
Case 3: 42288400756279755000 41738316205970650321 9448388419029349679 12743419233793500000
Case 4: 10629385789398750 10038062059019434 2333639845277441 2987331625687500 5314692894699375
Case 5: 2141586707424199320000 1847207988708862383979 429812555291137616021 549257487699888000000 713862235808066440000 1427724471616132880000
Case 6: 1167805814955000 875450283525397 205885653974603 257565569625000 291951453738750 583902907477500 875854361216250
Case 7: 3178668225924000 1835656852265351 431824747734649 539915712480000 635733645184800 1271467290369600 1907200935554400 2542934580739200
Case 8: 1973268899169904609560000 1364750637779727126297757 310128440748272873702243 415177097972190768000000 281895557024272087080000 563791114048544174160000 845686671072816261240000 1127582228097088348320000 1409477785121360435400000
Case 9: 10986238805835340800 5612262236942732207 1266306243825267793 1718788270111488000 1373279850729417600 2746559701458835200 4119839552188252800 5493119402917670400 6866399253647088000 8239679104376505600
Case 10: 48553566687543100000 28766143805670305387 6732664194329694613 8504041196268000000 4855356668754310000 9710713337508620000 14566070006262930000 19421426675017240000 24276783343771550000 29132140012525860000 33987496681280170000
Case 11: 150214324926821760 44105199120984133 10270923165095867 13103843045529600 13655847720620160 27311695441240320 40967543161860480 54623390882480640 68279238603100800 81935086323720960 95590934044341120 109246781764961280
Case 12: 200823692507287200 84852402464329021 20283596511670979 24553271371968000 15447976346714400 30895952693428800 46343929040143200 61791905386857600 77239881733572000 92687858080286400 108135834427000800 123583810773715200 139031787120429600
Case 13: 181904976292498632000 84417581593072593179 20357660749327406821 24205300178935680000 12126998419499908800 24253996838999817600 36380995258499726400 48507993677999635200 60634992097499544000 72761990516999452800 84888988936499361600 97015987355999270400 109142985775499179200 121269984194999088000
Case 14: 29360363703458563920000 14042320125161176193131 3562373378838823806869 3808543277694816000000 1727080217850503760000 3454160435701007520000 5181240653551511280000 6908320871402015040000 8635401089252518800000 10362481307103022560000 12089561524953526320000 13816641742804030080000 15543721960654533840000 17270802178505037600000 18997882396355541360000
Case 15: 1871604412346524800 894177948553782571 228721609846217429 240211024439040000 98505495386659200 197010990773318400 295516486159977600 394021981546636800 492527476933296000 591032972319955200 689538467706614400 788043963093273600 886549458479932800 985054953866592000 1083560449253251200 1182065944639910400
Case 16: 2681587618187937228000 1253606270809632165217 328755919270367834783 326873612372932800000 127694648485139868000 255389296970279736000 383083945455419604000 510778593940559472000 638473242425699340000 766167890910839208000 893862539395979076000 1021557187881118944000 1149251836366258812000 1276946484851398680000 1404641133336538548000 1532335781821678416000 1660030430306818284000
Case 17: 2028010133131200 910619798336749 226044777663251 253103232384000 88174353614400 176348707228800 264523060843200 352697414457600 440871768072000 529046121686400 617220475300800 705394828915200 793569182529600 881743536144000 969917889758400 1058092243372800 1146266596987200 1234440950601600
Case 18: 6013372840695000 2542755861306541 626887538693459 712077998940000 240534913627800 481069827255600 721604740883400 962139654511200 1202674568139000 1443209481766800 1683744395394600 1924279309022400 2164814222650200 2405349136278000 2645884049905800 2886418963533600 3126953877161400 3367488790789200 3608023704417000
Case 19: 97784591887839285000 37901400100355557727 10087971274644442273 9702320475721500000 3621651551401455000 7243303102802910000 10864954654204365000 14486606205605820000 18108257757007275000 21729909308408730000 25351560859810185000 28973212411211640000 32594863962613095000 36216515514014550000 39838167065416005000 43459818616817460000 47081470168218915000 50703121719620370000 54324773271021825000 57946424822423280000
Case 20: 3703144806069056172000 1253606270809632165217 328755919270367834783 326873612372932800000 127694648485139868000 255389296970279736000 383083945455419604000 510778593940559472000 638473242425699340000 766167890910839208000 893862539395979076000 1021557187881118944000 1149251836366258812000 1276946484851398680000 1404641133336538548000 1532335781821678416000 1660030430306818284000 1787725078791958152000 1915419727277098020000 2043114375762237888000 2170809024247377756000
Case 21: 650367725742212400 169686412488538361 38927337911461639 51156147976560000 20979604056200400 41959208112400800 62938812168601200 83918416224801600 104898020281002000 125877624337202400 146857228393402800 167836832449603200 188816436505803600 209796040562004000 230775644618204400 251755248674404800 272734852730605200 293714456786805600 314694060843006000 335673664899206400 356653268955406800 377632873011607200
Case 22: 83597572590000 35806773849357 8693226150643 10194416000000 2458752135000 4917504270000 7376256405000 9835008540000 12293760675000 14752512810000 17211264945000 19670017080000 22128769215000 24587521350000 27046273485000 29505025620000 31963777755000 34422529890000 36881282025000 39340034160000 41798786295000 44257538430000 46716290565000
Case 23: 1097282295106740000 411918374025332233 111316125974667767 103415205987000000 30480063752965000 60960127505930000 91440191258895000 121920255011860000 152400318764825000 182880382517790000 213360446270755000 243840510023720000 274320573776685000 304800637529650000 335280701282615000 365760765035580000 396240828788545000 426720892541510000 457200956294475000 487681020047440000 518161083800405000 548641147553370000 579121211306335000 609601275059300000
Case 24: 34802794260385616763360000 10383690450159870158623409 2572945880336129841376591 2891816046273163104000000 915863006852253072720000 1831726013704506145440000 2747589020556759218160000 3663452027409012290880000 4579315034261265363600000 5495178041113518436320000 6411041047965771509040000 7326904054818024581760000 8242767061670277654480000 9158630068522530727200000 10074493075374783799920000 10990356082227036872640000 11906219089079289945360000 12822082095931543018080000 13737945102783796090800000 14653808109636049163520000 15569671116488302236240000 16485534123340555308960000 17401397130192808381680000 18317260137045061454400000 19233123143897314527120000
Case 25: 199149954675879375 81495365700890917 18458317892859083 24869187259875000 4857315967704375 9714631935408750 14571947903113125 19429263870817500 24286579838521875 29143895806226250 34001211773930625 38858527741635000 43715843709339375 48573159677043750 53430475644748125 58287791612452500 63145107580156875 68002423547861250 72859739515565625 77717055483270000 82574371450974375 87431687418678750 92289003386383125 97146319354087500 102003635321791875 106860951289496250
Case 26: 28141143550940616950160000 9660498460476751875953339 2685776613059248124046661 2334973926176675424000000 654445198859084115120000 1308890397718168230240000 1963335596577252345360000 2617780795436336460480000 3272225994295420575600000 3926671193154504690720000 4581116392013588805840000 5235561590872672920960000 5890006789731757036080000 6544451988590841151200000 7198897187449925266320000 7853342386309009381440000 8507787585168093496560000 9162232784027177611680000 9816677982886261726800000 10471123181745345841920000 11125568380604429957040000 11780013579463514072160000 12434458778322598187280000 13088903977181682302400000 13743349176040766417520000 14397794374899850532640000 15052239573758934647760000
Case 27: 79837799040 18235843475 4696513645 4859688960 1774173312 3548346624 5322519936 7096693248 8870866560 10645039872 12419213184 14193386496 15967559808 17741733120 19515906432 21290079744 23064253056 24838426368 26612599680 28386772992 30160946304 31935119616 33709292928 35483466240 37257639552 39031812864 40805986176 42580159488
Case 28: 36889999038134426880000 12959240113439919051211 3726065230560080948789 2985448500791136000000 768541646627800560000 1537083293255601120000 2305624939883401680000 3074166586511202240000 3842708233139002800000 4611249879766803360000 5379791526394603920000 6148333173022404480000 6916874819650205040000 7685416466278005600000 8453958112905806160000 9222499759533606720000 9991041406161407280000 10759583052789207840000 11528124699417008400000 12296666346044808960000 13065207992672609520000 13833749639300410080000 14602291285928210640000 15370832932556011200000 16139374579183811760000 16907916225811612320000 17676457872439412880000 18444999519067213440000 19213541165695014000000
Case 29: 61512164886070236000000 14773432173112723019671 3439240850887276980329 4390630393889376000000 1230243297721404720000 2460486595442809440000 3690729893164214160000 4920973190885618880000 6151216488607023600000 7381459786328428320000 8611703084049833040000 9841946381771237760000 11072189679492642480000 12302432977214047200000 13532676274935451920000 14762919572656856640000 15993162870378261360000 17223406168099666080000 18453649465821070800000 19683892763542475520000 20914136061263880240000 22144379358985284960000 23374622656706689680000 24604865954428094400000 25835109252149499120000 27065352549870903840000 28295595847592308560000 29525839145313713280000 30756082443035118000000 31986325740756522720000
Case 30: 60938353914878636820000 20629055089595805298939 4966856134404194701061 5924914512225228000000 1149780262544879940000 2299560525089759880000 3449340787634639820000 4599121050179519760000 5748901312724399700000 6898681575269279640000 8048461837814159580000 9198242100359039520000 10348022362903919460000 11497802625448799400000 12647582887993679340000 13797363150538559280000 14947143413083439220000 16096923675628319160000 17246703938173199100000 18396484200718079040000 19546264463262958980000 20696044725807838920000 21845824988352718860000 22995605250897598800000 24145385513442478740000 25295165775987358680000 26444946038532238620000 27594726301077118560000 28744506563621998500000 29894286826166878440000 31044067088711758380000

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Wed Oct 15, 2003 12:14 am

yes.. I assume you mean n=7... see for example my post on this topic... apparantly we posted at exactly the same time :P

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Oct 15, 2003 12:26 am

Seems to be right. But f goes up to 100. Just curious, how did you generate those?

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 » Wed Oct 15, 2003 7:44 pm

You can solve the problem in two ways.
simpliest one is:

1^3+6^3+8^3=9^3
9^3+54^3+72^3=81^3
so, 1^3+6^3+8^3+54^3+72^3=81^3 and so.
this for n is odd.
when n is even
the initial equation is,
5^3+7^3+ 9^3+10^3=13^3
so for n=6 ,
5^3+7^3+9^3+10^3=13^3+78^3+104^3=117^3

so for n=100 it will be a big number.
you can also find your own equation.

second approach is,

let, f=an+1,

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

choose randomly value for a1 to an-1, check that you get a integer solution for an. in this approach we get a solution for n=100 with in integer range,that is below 10000. here choose a=2*i+1 or 2*i+2,
randomly and calculate an. so, the value of an will not gteater 10000.

i apply the second one. because i always avoid big number.
[/code]
Last edited by one & only on Thu Oct 30, 2003 1:22 am, edited 1 time in total.

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 » Wed Oct 15, 2003 8:26 pm

for n=2 we dont gets any solution as we know from fermats theorem.
for any other value of n we always gets a solution.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Wed Oct 15, 2003 11:36 pm

hmm.. am not sure if i understand your second approach, are you trying to say we should solve the equation 3a_n(a_n + 1) + 1 = a_1^3 + ... + a_n^3 ?
And then I don't get how we should choose those a_i.. should it be a_i = 2*i + 1 or a_i = 2*i + 2, or something different? It seems to me that if we just randomly choose those a_i and check if they yield an integer value value for a_n, we're back at an exponential (i.e. bad) algorithm. Can you be a bit more specific please ?

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 » Fri Oct 17, 2003 1:39 am

Sorry for writing wrong equation. it is a typing mistake.

The equation will be
3an^2+3an+1=a1^3+a2^3+.....+(an-1)^3

To choose the value a i use rand() function. The pseudocode is
b=rand()
if(b&1) a=2*i+1;
else a=2*i+2;

Since it is a randomize algorithm ,it seems it takes two much time but i got accepted in 0.051 seconds. So donot worry about TLE.

To make the program more efficient choose the value for a[n-1] from
i= 1 to 220 where the value of i should chosen for a1 to an-2 as before.
and check that you get a integer solution for an.
i think it is enough to understand the way of approach to solve the problem

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 » Fri Oct 17, 2003 2:14 am

Sorry again for a mistake in previous post.
To make the program more efficient choose the value for a[n-1] from
i= 1 to 220 where the value of i should chosen for a1 to an-2 as be
please read it as
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.

Saranga
New poster
Posts: 4
Joined: Thu Oct 16, 2003 10:25 pm

Post by Saranga » Fri Oct 17, 2003 11:19 am

I like this problem, it looks like there are many ways to solve it.

Maarten:

Your numbers are very large, how did you generate them? It is interesting that you get numbers of that size.

one&only:

Why are you randomly picking odd or even numbers? I did not use randomness and just did permutations with that formula (3x^2+3x+1-d=0) and found many straight sequences:

Code: Select all

1477 1 2 3 4 5 9 187 1476
for one example. Isn't this way faster?

Also, where did you get the identity:

Code: Select all

5^3+7^3+9^3+10^3=13^3
Use another program to generate it or a formula?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Oct 17, 2003 12:08 pm

Where do you derive:

3an^2+3an+1=a1^3+a2^3+.....+(an-1)^3
?

Saranga
New poster
Posts: 4
Joined: Thu Oct 16, 2003 10:25 pm

Post by Saranga » Fri Oct 17, 2003 2:25 pm

Just take (x+1)^3 and expand symbolically. You get:

(x+1)^3 = x^3 + 3x^2 + 3x + 1

This assumes that the sum and the largest a[n]^3 are 1 apart, so the remaining terms fall within the rest of the formula. This may not be a good assumption, but since there are many solutions to each case (infinitely many?), it does work. Especially good with large numbers I think.

For example, for case n=100 I get:

Code: Select all

3565 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 197 199 3564
Don't have to permute up to 3565, only to 199.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Fri Oct 17, 2003 3:48 pm

Hi guys! Let me explain how we (I solved this problem with someone else) came up with those large numbers. At first, we didn't have a clue how to solve the problem, apart from just trying possibilities. So we looked up some facts about number theory and found the following:

Theorem (Riley, 1825) Any natural number n can be written as the sum of three positive rational cubes in infinitely many ways.

Now the interesting thing is, the proof in constructive, ie it gives a way to find rational numbers A, B, C such that A^3+B^3+C^3 = n.

Our idea then is the following. We want to solve f^3 = a_1^3 + ... + a_n^3. Now choose b_1 = 1, b_2 = 2, ... b_{n-3} = n-3, and choose g such that g^3 > b_1^3 + ... + b_{n-3}^3, and let n = g^3 - b_1^3 - ... - b_{n-3}^3. By the above theorem, n = A^3+B^3+C^3 has a solution for rational A, B, C. If we now multiply both sides by the least common multiple d of the denominators of A, B, C to the third power, both sides will be integers, and moreover, we have
d^3 n = (Ad)^3 + (Bd)^3 + (Cd)^3.
If we write f = dg, a_4 = db_1, a_5 = db_2 etc, and a_1=Ad, a_2=Bd, a_3 = Cd, we obtain
f^3 - a_4^3 - ... - a_n^3 = a_1^3 + a_2^3 + a_3^3,
which is what we wanted.

For the sake of completeness, let me give the proof of the above theorem:
Let A = 12t(t+1)-(t+1)^3, B = (t+1)^3 - 12t(t-1), C = 12t(t-1), then A^3+B^3+C^3 = 72t(t+1)^6.
Then choose u rational such that 1 < nu^3/72 < 2, and take t = nu^3/72, and observe that with d = u(t+1)^2,
(A/d)^3 + (B/d)^3 + (C/d)^3 = n.
Moreover, we can choose u in infinitely many ways[/b]

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Fri Oct 17, 2003 7:03 pm

one & only wrote:Sorry for writing wrong equation. it is a typing mistake.

The equation will be
3an^2+3an+1=a1^3+a2^3+.....+(an-1)^3

To choose the value a i use rand() function. The pseudocode is
b=rand()
if(b&1) a=2*i+1;
else a=2*i+2;

Hello , one & only
I used your method and implement it, I can run the condiction n=98
but got TLE in n=99 and n=100
What's the problem ?
Thx :)

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 » Fri Oct 17, 2003 7:44 pm

Also, where did you get the identity:
Code:
5^3+7^3+9^3+10^3=13^3

Use another program to generate it or a formula?
yes, i use another sample program to generate it.

i think using randomize algorithm is more efficient than generating permutation sequence.

Post Reply

Return to “Volume 105 (10500-10599)”