suna@aecom.UUCP (David Suna) (04/17/85)
One of my computer teachers presented this problem to the class.
I am looking for an efficient algorithm to be run on a VAX11/780.
Find the smallest integer which can be broken up into:
a^4 + b^4 = k
c^4 + d^4 = k
I have heard that there was a paper written by Russian mathematicians
but i haven't found it yet.
Replies should please be sent to :
...{philabs,cucard,pegasus,ihnp4,rocky2}!aecom!suna
Thanx in advance,
David Sunabs@faron.UUCP (Robert D. Silverman) (04/20/85)
> One of my computer teachers presented this problem to the class. > I am looking for an efficient algorithm to be run on a VAX11/780. > > Find the smallest integer which can be broken up into: > > a^4 + b^4 = k > c^4 + d^4 = k > > I have heard that there was a paper written by Russian mathematicians > but i haven't found it yet. > > Replies should please be sent to : > ...{philabs,cucard,pegasus,ihnp4,rocky2}!aecom!suna > > > Thanx in advance, > David Suna *** REPLACE THIS LINE WITH YOUR MESSAGE *** I'll start by giving you a hint: since it's the sum of two fourth powers and must be odd it is necessarily of the form 8n+1.
eppstein@columbia.UUCP (David Eppstein) (04/21/85)
> One of my computer teachers presented this problem to the class. > I am looking for an efficient algorithm to be run on a VAX11/780. > > Find the smallest integer which can be broken up into: > > a^4 + b^4 = k > c^4 + d^4 = k Since you just want one number, the most efficient algorithm I can think of to print it out is a single printf(). Or did you want to solve all such problems (including Fermat's last theorem)? In the latter case I have to warn you that I think it's been proven undecidable (no not Fermat, the general problem).
gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins) (04/21/85)
In article <288@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >> Find the smallest integer which can be broken up into: >> a^4 + b^4 = k >> c^4 + d^4 = k >> David Suna > >I'll start by giving you a hint: since it's the sum of two fourth powers >and must be odd it is necessarily of the form 8n+1. The reasoning behind this conclusion escapes me. Why must it be odd? -- Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo {allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins
gjerawlins@watdaisy.UUCP (Gregory J.E. Rawlins) (04/22/85)
In article <1418@aecom.UUCP> suna@aecom.UUCP (David Suna) writes: >I am looking for an efficient algorithm to be run on a VAX11/780. >Find the smallest integer which can be broken up into: > a^4 + b^4 = k > c^4 + d^4 = k >I have heard that there was a paper written by Russian mathematicians >but i haven't found it yet. A partial solution to this problem can be found in Hardy and Littlewood's "The theory of Numbers" 4th ed, O.U.P. 1960. I don't know of any paper on this problem written by Russians, the above reference is the only one i have. The smallest solution is 133^4 + 134^4 = 158^4 + 59^4 On page 201, Hardy and Littlewood give an algorithm for generating infinitely many such solutions. Let: A = a^7 ; B = a^6 * b ; C = a^5 * b^2 ; D = 3 * C E = 2 * a^3 * b^4 ; F = 2 * a^4 * b^3 ; G = 3 * a^2 * b^5 ; H = G / 3 I = a * b^6 ; J = b^7 then x = A + C - E + G + I y = B - D - F + H + J u = A + C - E - G + I v = B + D - F + H + J is a solution to x^4 + y^4 = u^4 + v^4 for all a,b. If anyone knows of any more recent work on this problem please post it. -- Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo {allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins
bs@faron.UUCP (Robert D. Silverman) (04/24/85)
> In article <288@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: > >> Find the smallest integer which can be broken up into: > >> a^4 + b^4 = k > >> c^4 + d^4 = k > >> David Suna > > > >I'll start by giving you a hint: since it's the sum of two fourth powers > >and must be odd it is necessarily of the form 8n+1. > > The reasoning behind this conclusion escapes me. Why must it > be odd? > -- > Gregory J.E. Rawlins, Department of Computer Science, U. Waterloo > {allegra|clyde|linus|inhp4|decvax}!watmath!watdaisy!gjerawlins It's fairly simple: assume k is even. Then we have one of two cases either a and b must be even or a and b must be odd. Either assumption leads to a simple algebraic demonstration by infinite descent that there must be a smaller solution.
bprice@bmcg.UUCP (Bill Price) (04/26/85)
> >I am looking for an efficient algorithm to be run on a VAX11/780. > >Find the smallest integer which can be broken up into: > > a^4 + b^4 = k > > c^4 + d^4 = k > >I have heard that there was a paper written by Russian mathematicians > >but i haven't found it yet. > ^^^ ^ ^^^^^^^ ^^^^^ ^^ ^^^ > The smallest solution is > 133^4 + 134^4 = 158^4 + 59^4 Yes, you have: the algorithm seems to start with the word "postnews".... --Bill Price -- --Bill Price uucp: {Most Anybody}!sdcsvax!bmcg!bprice arpa:? sdcsvax!bmcg!bprice@nosc
chuck@dartvax.UUCP (Chuck Simmons) (04/27/85)
> > >> Find the smallest integer which can be broken up into: > > >> a^4 + b^4 = k > > >> c^4 + d^4 = k > > > > > >I'll start by giving you a hint: since it's the sum of two fourth powers > > >and must be odd it is necessarily of the form 8n+1. > > > > The reasoning behind this conclusion escapes me. Why must it > > be odd? > > It's fairly simple: assume k is even. Then we have one of two cases either > a and b must be even or a and b must be odd. Either assumption leads to > a simple algebraic demonstration by infinite descent that there must be > a smaller solution. Call me dense, but this little "hint" doesn't do anything for me. I see 3 cases: clearly a = b mod 2 and c = d mod 2. So the 3 cases are a even, c even; a odd, c odd; a even, c odd. I can handle the first of these cases. But for the rest, I remain clueless. Could you provide a slightly more elaborate hint? -- Chuck Simmons
mvm9745@acf4.UUCP (Michael V. Mascagni) (05/03/85)
Your problem can be found with solution in STRUCTURED PROGRAMMING by
Dahl, Dijkstra and Hoare although I recall it was posed by Joe
Weizenbaum. This problem for fifth powers is also interesting in that
no solution is known. The question of efficiency is related to generality,
in that an algorithm (if a solution exists) that works for any power
may not be as efficient as one that uses information specific to a given
power, e.g. 4.
A.P. Mullhaupt, CIMS