Euler's sum of powers conjecture: Difference between revisions

===Alternative===

{{works with|XDS Modula-2}}

Uses the same idea as the QL SuperBASIC solution, i.e. if the desired equation holds modulo several positive integers M0, M1, ..., and if the LCM of M0, M1, ... is greater than 4*(249^5), then the equation holds absolutely. This makes it unnecessary to have variables with enough bits to store the fifth powers up to 249^5. It isn't clear why the fifth powers in a counterexample must be all different, as the task description seems to assume, so the demo program doesn't enforce this.

<syntaxhighlight lang="modula2">

MODULE EulerFifthPowers;

FROM InOut IMPORT WriteString, WriteLn, WriteCard;

TYPE

(* CARDINAL in XDS Modula-2 is 32-bit unsigned integer *)

TModArray = ARRAY [0..4] OF CARDINAL;

CONST

Modulus = TModArray {327, 329, 334, 335, 337};

MaxTerm = 249;

VAR

res : ARRAY [0..4] OF ARRAY [0..Modulus[4]-1] OF CARDINAL;

inv : ARRAY [0..Modulus[0]-1] OF CARDINAL;

m, s0, s1, s2, s3, x, x0, x1, x2, x3, y : CARDINAL;

BEGIN

(* Set up arrays of 5th powers w.r.t. each modulus *)

FOR m := 0 TO 4 DO

FOR x := 0 TO Modulus[m] - 1 DO

y := (x*x) MOD Modulus[m];

y := (y*y) MOD Modulus[m];

res[m][x] := (x*y) MOD Modulus[m];

END;

END;

(* For Modulus[0] only, set up an inverse array (having checked

elsewhere that 5th powers MOD Modulus[0] are all different) *)

FOR x := 0 TO Modulus[0] - 1 DO

y := res[0][x];

inv[y] := x;

END;

(* Test sums of four 5th powers *)

FOR x0 := 1 TO MaxTerm DO

s0 := res[0][x0];

FOR x1 := x0 TO MaxTerm DO

s1 := (s0 + res[0][x1]) MOD Modulus[0];

FOR x2 := x1 TO MaxTerm DO

s2 := (s1 + res[0][x2]) MOD Modulus[0];

FOR x3 := x2 TO MaxTerm DO

s3 := (s2 + res[0][x3]) MOD Modulus[0];

y := inv[s3];

IF y <= MaxTerm THEN

(* Here, by definition of y, we have

x0^5 + x1^5 + x2^5 + x3^5 = y^5 MOD Modulus[0].

Now test the congruence for the other moduli. *)

m := 1;

WHILE (m <= 4) AND

((res[m][x0] + res[m][x1] + res[m][x2] + res[m][x3])

MOD Modulus[m] = res[m][y])

DO INC(m); END;

IF (m = 5) THEN

WriteString('Counterexample: ');

WriteCard( x0, 1); WriteString('^5 + ');

WriteCard( x1, 1); WriteString('^5 + ');

WriteCard( x2, 1); WriteString('^5 + ');

WriteCard( x3, 1); WriteString('^5 = ');

WriteCard( y, 1); WriteString('^5');

WriteLn;

END; (* IF m... *)

END; (* IF y... *)

END; (* FOR x3 *)

END; (* FOR x2 *)

END; (* FOR x1 *)

END; (* FOR x0 *)

END EulerFifthPowers.

</syntaxhighlight>

{{out}}

<pre>

Counterexample: 27^5 + 84^5 + 110^5 + 133^5 = 144^5

</pre>