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