Chapter 3

The Extended Euler Conjecture

The Euler Conjecture is associated with the minimum length representation of a power xm as the sum of less mth powers. We now consider extending the search to obtain primitive solutions of the equation

(3.1)

where, for convenience, we consider k £ n, and, for all i and j, xi yj, xi ³ xi+1 and yj ³ yj+1 and add the additional constraint x1 > y1 . This last condition means that a small area of the full search space is ignored. However, the algorithm used to find solutions of equation 3.1 is such that any gaps are eventually closed.

Definition: Let s(m,k) be the minimum value of n such that equation (1) has a non-trivial solution. Thus s(m) = s(m,1). For each m, we may consider k only until the point is reached where a solution is found for k = n. We may also consider restricting search limits on n by making the reasonable assumption that s(m,k) £ s(m,k-1).

Definition: Let t(m) be the minimum value of k + n such that a non-trivial solution of equation 3.1 exists. Alternatively, t(m) is the minimum of s(m,k) + k over all k.

This function t(m) is a better guide than s(m) to the decomposition of powers. The extended Euler's Conjecture may then be stated as: t(m) ³ m. There are no known counterexamples to this conjecture.

Perhaps a more familiar way of considering the extended conjecture (see, for example, [20]) is to consider representations of the form

xm = (3.2)

In this way, we may define s*(m) to be the minimum value of k in equation 3.2 over all x > 1. It is obvious that t(m) = s*(m) + 1. However, algorithms to find solutions in the form of equation 3.2 are not amenable to tight control, whereas the main algorithm used to find solutions in the form of equation 3.1 is a slightly altered version of the decomposition algorithm mentioned in Chapter 1 and defined in Chapter 2. The only differences are to enforce the xi ¹ yj condition. With this understanding, we present the available results.

We have s(2,1) = 2, s(3,1) = 3 and s(4,1) = 3. The equation 123 + 13 = 103 + 93 provides s(3,2) = 2, and the equation 1584 + 594 = 1344 + 1334 gives s(4,2) = 2 (see [27] for a comprehensive list of solutions). In the following, we use the unsubscripted x instead of x1.

For k = 2 we have:

 m = 5: n = 5: (22,1)5 = (21,16,7,5,4)5 n = 4: (29,3)5 = (28,20,10,4)5 (38,12)5 = (37,25,13,5)5 (52,28)5 = (50,35,29,26)5 (64,61)5 = (63,62,25,5)5 (85,16)5 = (82,53,50,6)5 (96,31)5 = (86,72,63,56)5 (99,14)5 = (94,67,58,44)5 no more solutions for x up to 100. n £ 3: no solutions for x up to 835. m = 6: n = 10: (12,12)6 = (11,11,11,9,7,4,4,1,1,1)6 n = 9: (21,6)6 = (19,17,13,13,13,7,5,5,1)6 n = 8: (37,35)6 = (36,33,30,24,15,12,10,8)6 n = 7: (91,56)6 = (78,78,69,58,36,22,18)6 n £ 6: no solutions for x up to 131. m = 7: n = 18: (12,9)7 = (10,10,10,8,8,8,8,7,7,6,6,4,3,2,2,2,2,2)7 n = 14: (13,9)7 = (12,11,8,8,8,7,7,7,7,7,7,7,5,5)7 n = 13: (16,13)7 = (15,14,10,10,10,10,9,9,9,6,6,3,2)7 n = 11: (21,16)7 = (18,18,18,14,14,11,8,6,5,5,4)7 n = 10: (25,14)7 = (21,21,20,20,12,10,7,5,4,3)7 n = 8: (33,10)7 = (31,28,20,15,15,7,6,5)7 n £ 7: no solutions for x up to 100. m = 8: n = 40: (7,6)8 = (18x5,6x4,3x3,1x2,12x1)8 n = 37: (8,4)8 = (2x7,2x6,5x5,3x2,25x1)8 n = 36: (10,6)8 = (1x9,2x8,4x7,5x5,10x3,2x2,12x1)8 n = 33: (11,3)8 = (1x10,6x8,8x6,4x4,12x2,2x1)8 n = 25: (11,9)8 = (2x10,3x8,1x7,1x5,14x4,4x2)8 n = 23: (17,1)8 = (16,14,12,6x10,2x9,5x8,3x6,4x2)8 n = 22: (17,17)8 = (2x16,3x14,2x12,1x9,1x8,1x7,5x6,4x4,3x2)8 n = 9: (27,11)8 = (24,24,20,20,17,16,8,7,2)8 n £ 8: no solutions for x up to 85. m = 9: n = 30: (10,10)9 = (2x9,7x8,7x7,1x5,4x4,8x3,1x2)9 n = 25: (13,10)9 = (4x11,5x9,1x8,2x7,2x6,2x4,3x2,6x1)9 n = 20: (14,11)9 = (2x13,1x10,1x9,3x8,1x6,5x5,4x3,3x1)9 n = 17: (19,1)9 = (3x16,4x14,3x13,5x9,1x8,1x4)9 n = 12: (21,15)9 = (19,19,17,16,7,4,3,3,2,2,2,2)9 n £ 11: no solutions for x up to 55. m = 10: n = 24: (10,5)10 = (9x8,1x7,1x6,3x4,2x2,8x1)10 n = 19: (17,9)10 = (3x15,2x12,6x11,1x10,1x6,1x5,5x2)10 n = 15: (35,3)10 = (33,32,24,21,20,20,13,13,13,12,11,9,7,1,1)10 n £ 14: no solutions for x up to 42. m = 11: n = 37: (13,7)11 = (1x12,3x11,4x9,8x8,2x6,4x5,7x4,2x3,1x2,5x1)11 n = 35: (19,11)11 = (3x17,1x15,7x12,1x10,1x8,1x6,2x5,4x4,13x2,2x1)11 n = 34: (19,12)11 = (1x18,2x16,2x14,5x13,7x10,1x8,6x7,2x5,7x3,1x1)11 n = 32: (21,4)11 = (7x17,6x16,1x14,1x11,4x10,2x9,2x8,3x7,1x6,4x3,1x2)11 n = 28: (21,5)11 = (2x19,3x17,1x14,5x13,4x11,3x10,3x8,2x7,1x4,1x3,3x1)11 n £ 27: no solutions for x up to 26. m = 12: n = 40: (21,3)12 = (2x19,2x18,3x15,4x14,2x12,4x10,2x9,6x8,4x6,1x5,8x3,2x1)12 n = 38: (22,5)12 = (21,20,18,10x13,12,11,10,9,12x6,3x4,2x3,2x3,2x1)12 n £ 37: no solutions for x up to 22.

For k = 3 we have:

 m = 5: n = 5: (19,8,3)5 = (17,15,11,11,6)5 (21,12,8)5 = (19,18,2,1,1)5 (24,15,14)5 = (20,19,19,16,9)5 (28,15,2)5 = (27,20,13,8,7)5 (28,25,1)5 = (27,26,13,13,5)5 (29,5,3)5 = (28,20,10,5,4)5 (29,21,20)5 = (27,25,18,17,13)5 (29,26,9)5 = (27,25,24,13,5)5 (30,21,20)5 = (28,27,7,6,3)5 (31,18,16)5 = (28,27,6,3,1)5 (31,23,19)5 = (30,25,18,16,14)5 (31,28,14)5 = (30,26,25,13,9)5 (32,15,3)5 = (31,20,19,6,4)5 no more solutions for x up to 32. n = 4: (33,17,2)5 = (30,27,18,7)5 (34,10,1)5 = (33,20,20,2)5 (34,19,16)5 = (33,25,9,2)5 (36,25,2)5 = (35,27,20,11)5 (38,2,2)5 = (35,29,22,16)5 (38,21,10)5 = (35,30,23,11)5 (43,22,12)5 = (39,32,31,5)5 (45,22,16)5 = (41,36,27,9)5 (46,12,8)5 = (41,39,11,5)5 (46,26,4)5 = (44,31,30,1)5 (47,15,8)5 = (44,31,31,24)5 (50,44,26)5 = (49,46,15,10)5 no more solutions for x up to 50. n = 3: (66,44,18)5 = (64,51,13)5 (67,28,24)5 = (62,54,3)5 (74,43,21)5 = (68,62,8)5 (83,67,56)5 = (81,72,53)5 no more solutions for x up to 100. The case for m = 5 ends here. m = 6: n = 16: (7,5,5)6 = (6,6,6,4,4,3,1,1,1,1,1,1,1,1,1,1)6 n = 13: (8,6,6)6 = (7,7,7,3,3,3,2,2,2,2,2,1,1)6 n = 11: (10,4,4)6 = (9,8,7,6,6,3,3,3,3,3,1)6 n = 10: (13,11,1)6 = (12,12,9,6,6,3,3,2,2,2)6 (15,3,3)6 = (13,11,10,10,10,10,9,8,2,2)6 n = 9: (21,5,5)6 = (18,18,15,12,11,10,9,6,6)6 (22,7,7)6 = (18,18,18,14,12,9,9,2,2)6 n = 8: (22,7,7)6 = (20,18,13,12,12,12,11,6)6 n = 5: (34,13,13)6 = (32,27,21,14,2)6 (37,24,1)6 = (36,28,21,15,10)6 (41,8,1)6 = (35,35,32,6,6)6 (45,13,13)6 = (43,35,21,18,18)6 (47,40,19)6 = (44,42,36,7,5)6 no more solutions for x up to 50. n = 4: (73,58,41)6 = (70,65,32,15)6 no more solutions for x up to 75. n = 3: (23,15,10)6 = (22,19,3)6 (67,37,36)6 = (65,52,15)6 (74,47,33)6 = (73,54,23)6 (81,43,32)6 = (80,55,3)6 (81,50,37)6 = (78,65,11)6 no more solutions for x up to 100. The case for m = 6 ends here. m = 7: n = 16: (6,6,2)7 = (5,5,5,5,5,5,5,3,3,3,3,3,3,1,1,1)7 n = 13: (9,5,1)7 = (8,7,7,7,6,3,3,3,3,3,3,2,2)7 n = 11: (14,12,6)7 = (13,11,11,11,11,7,3,3,2,1,1)7 n = 10: (22,11,3)7 = (21,16,15,15,13,12,8,7,7,6)7 n = 8: (32,28,1)7 = (30,29,25,22,14,11,10,4)7 n = 7: (62,45,21)7 = (60,47,44,43,9,7,2)7 n £ 6: no solutions for x up to 80. m = 8: n = 30: (9,7,7)8 = (1x8,22x6,2x5,1x4,3x2,1x1)8 n = 27: (11,1,1)8 = (2x10,8x6,2x5,2x4,1x3,12x2)8 n = 26: (11,3,1)8 = (1x10,1x9,4x8,2x6,2x5,1x4,15x2)8 n = 23: (11,5,1)8 = (1x10,5x8,3x7,8x6,2x4,4x2)8 n = 21: (13,1,1)8 = (1x11,6x10,2x5,9x4,3x2)8 n = 18: (13,13,4)8 = (1x11,14x10,1x8,1x5,1x2)8 n = 9: (14,9,9)8 = (13,12,11,10,6,4,4,2,2)8 n = 8: (50,17,8)8 = (47,40,38,38,16,16,12,6)8 n £ 7: no solutions for x up to 60. m = 9: n = 24: (14,2,2)9 = (2x12,4x11,1x9,2x8,6x7,6x5,3x1)9 n = 19: (15,5,4)9 = (5x12,4x11,3x10,1x8,1x7,4x6,1x1)9 n = 17: (17,6,5)9 = (16,15,4x11,10,9,4x8,2x7,4,3,1)9 n = 16: (22,8,2)9 = (20,19,17,16,4x15,13,4x12,9,2x5)9 n = 15: (22,21,9)9 = (2x20,2x19,18,17,3x12,8,2x4,2x3,1)9 n = 11: (30,16,13)9 = (29,25,21,19,19,9,9,7,6,3,2)9 n £ 10: no solutions for x up to 47. m = 10: n = 16: (19,14,2)10 = (18,17,15,12,12,12,11,11,9,9,9,9,9,8,8,4)10 n = 15: (32,13,4)10 = (29,29,26,25,22,21,18,15,15,12,12,8,7,5,1)10 n £ 14: no solutions for x up to 32. m = 11: n = 36: (16,9,3)11 = (1x15,5x13,4x7,14x6,5x4,7x2)11 n = 31: (16,10,10)11 = (1x15,1x14,3x12,10x11,1x8,1x7,3x5,2x4,6x3,3x1)11 n = 30: (20,15,5)11 = (3x17,6x16,2x13,1x12,2x11,5x9,3x8,1x6,2x4,4x3,1x2)11 n £ 29: no solutions for x up to 20. m = 12: n = 40: (18,13,13)12 = (2x17,4x12,1x10,4x9,5x8,2x7,8x6,1x5,1x4,4x3,3x2,5x1)12 n = 32: (19,14,14)12 = (1x17,5x16,2x15,3x13,2x11,1x10,3x7,1x5,4x4,5x2,5x1)12 n £ 31: no solutions for x up to 19.

For k = 4 we have:

 m = 5: n = 4: (8,6,6,5)5 = (7,7,7,4)5 (14,11,11,7)5 = (13,12,12,6)5 (19,16,7,7)5 = (18,17,12,2)5 no more solutions for x up to 20. m = 6: n = 4: (10,6,5,3)6 = (9,9,2,2)6 (20,13,13,9)6 = (19,17,12,5)6 (20,16,11,3)6 = (18,17,17,8)6 no more solutions for x up to 20. m = 7: n = 10: (11,3,3,3)7 = (9,9,9,9,6,4,4,4,4,4)7 n = 7: (16,7,6,3)7 = (15,13,11,9,9,9,8)7 n = 6: (23,19,4,4)7 = (21,21,18,13,11,8)7 n £ 5: no solutions for x up to 50. m = 8: n = 10: (9,9,2,2)8 = (8,8,8,8,8,6,5,4,4,3)8 n = 8: (16,6,5,5)8 = (14,14,13,12,10,4,4,3)8 n = 7: (35,20,11,6)8 = (34,28,22,22,16,9,7)8 n £ 6: no solutions for x up to 43. m = 9: n = 29: (8,8,2,2)9 = (6x7,13x5,3x4,7x3)9 n = 20: (11,11,6,6)9 = (3x10,4x9,8,7,6x5,4x3,1)9 n = 16: (16,9,9,6)9 = (3x14,12,11,5,6x4,2x2,2x1)9 n = 11: (20,13,3,3)9 = (19,18,10,8,8,8,8,6,6,4,4)9 n = 10: (21,16,12,5)9 = (19,19,18,14,11,10,9,6,6,2)9 n £ 9: no solutions for x up to 32. m = 10: n = 19: (17,12,8,2)10 = (1x15,10x13,4x11,2x10,2x1)10 n = 16: (26,22,19,15)10 = (25,23,21,20,20,14,13,11,11,8,7,7,7,4,4,1)10 n = 15: (27,11,9,8)10 = (24,24,22,20,20,20,20,20,15,14,14,13,12,5,2)10 n £ 14: no solutions for x up to 28. m = 11: n = 28: (14,8,2,2)11 = (1x13,3x12,1x9,2x7,3x6,11x5,2x4,5x1)11 n £ 27: no solutions for x up to 19. m = 12: n = 33: (15,6,6,2)12 = (3x13,5x12,2x11,8x10,3x9,2x8,1x7,2x5,1x4,6x3)12 n £ 32: no solutions for x up to 18.

For k = 5 we have:

 m = 7: n = 10: (10,7,6,6,6)7 = (9,9,8,2,2,1,1,1,1,1)7 n = 8: (15,2,2,2,1)7 = (14,12,11,10,5,4,4,4)7 n = 7: (17,11,9,9,1)7 = (16,15,5,4,3,2,2)7 n = 5: (19,16,13,8,8)7 = (18,17,15,12,2)7 (23,16,14,8,4)7 = (22,20,9,7,7)7 no more solutions for x up to 25. The case for m = 7 ends here. m = 8: n = 15: (7,3,1,1,1)8 = (6,6,5,5,5,5,5,4,4,4,4,4,4,4,2)8 n = 12: (10,5,5,3,3)8 = (8,8,8,8,8,8,4,4,1,1,1,1)8 n = 11: (11,11,8,3,3)8 = (10,10,10,10,9,6,5,5,2,2,1)8 n = 9: (12,7,7,6,1)8 = (10,10,10,10,9,4,4,3,3)8 n = 8: (17,13,13,13,2)8 = (16,15,15,6,5,4,4,1)8 n = 7: (28,25,25,25,2)8 = (26,26,26,26,11,9,3)8 n = 6: (39,33,32,25,19)8 = (37,35,35,17,16,2)8 n = 5: (43,20,11,10,1)8 = (41,35,32,28,5)8 no more solutions for x up to 43. The case for m = 8 ends here. m = 9: n = 25: (8,8,5,5,3)9 = (6x7,3x6,13x2,3x1)9 n = 15: (14,6,4,4,4)9 = (13,12,11,10,4x9,3x2,4x1)9 n = 11: (22,20,14,8,7)9 = (21,21,16,15,15,12,9,9,5,5,3)9 n = 10: (25,14,8,4,3)9 = (22,22,20,20,19,16,12,9,2,2)9 n £ 9: no solutions for x up to 30. m = 10: n = 19: (16,8,8,7,1)10 = (1x15,1x13,5x12,3x11,3x5,4x4,2x3)10 n = 16: (16,14,8,3,3)10 = (1x15,5x13,2x12,1x6,2x4,1x2,4x1)10 n = 15: (20,11,8,3,1)10 = (2x18,1x17,1x16,1x10,2x7,6x4,2x2)10 n £ 14: no solutions for x up to 26. m = 11: n = 25: (18,12,12,5,5)11 = (1x17,1x16,1x15,1x14,4x11,1x9,1x8,5x7,4x4,4x2,2x1)11 n £ 24: no solutions for x up to 18. m = 12: n £ 33: no solutions for x up to 17.

For k = 6 we have:

 m = 7: n = 6: (13,10,6,6,3,2)7 = (12,12,7,7,1,1)7 no more solutions for x up to 16. m = 8: n = 8: (14,11,10,8,5,5)8 = (12,12,12,12,9,9,6,3)8 n = 7: (19,14,7,7,2,2)8 = (18,17,12,9,6,5,4)8 n = 6: (23,15,10,8,6,3)8 = (22,20,12,9,9,5)8 (25,15,14,5,5,5)8 = (23,23,7,3,2,1)8 no more solutions for x up to 25. m = 9: n = 10: (18,15,9,5,5,5)9 = (17,17,6,6,3,2,2,2,1,1)9 n = 6: (23,18,14,13,13,1)9 = (22,21,15,10,9,5)9 no more solutions for x up to 25. The case for m = 9 ends here. m = 10: n £ 15: no solutions for x up to 22. m = 11: n = 30: (12,8,8,8,2,2)11 = (6x10,5x9,6x7,2x4,3x3,8x1)11 n = 26: (15,12,6,6,6,2)11 = (2x14,4x11,4x9,3x8,1x7,4x5,2x4,3x3,3x1)11 n £ 25: no solutions for x up to 17. m = 12: n = 32: (14,10,10,7,1,1)12 = (2x12,13x11,1x8,3x6,3x5,3x3,7x2)12 n £ 31: no solutions for x up to 16.

For k = 7 we have:

 m = 8: n = 7: (13,8,6,6,5,3,1)8 = (12,11,10,9,9,7,4)8 no more solutions for x up to 15. m = 9: n = 9: (15,10,10,10,9,7,1)9 = (14,13,13,4,4,4,4,3,3)9 n £ 8: no solutions for x up to 21. m = 10: n £ 15: no solutions for x up to 19. m = 11: n = 25: (14,12,7,4,4,4,3)11 = (1x13,10x11,1x10,1x9,2x8,2x6,2x2,6x1)11 n £ 24: no solutions for x up to 16. m = 12: n £ 32: no solutions for x up to 15.

For k = 8 we have:

 m = 9: n = 10: (14,10,10,9,9,9,7,5)9 = (13,13,11,8,8,6,6,6,1,1)9 n = 8: (16,12,11,11,10,9,3,2)9 = (15,14,14,8,7,7,5,4)9 no more solutions for x up to 16. m = 10: n £ 15: no solutions for x up to 18. m = 11: n £ 25: no solutions for x up to 15. m = 12: n = 20: (13,8,8,8,7,7,6,2)12 = (7x11,1x10,2x9,1x5,2x3,7x1)12 n £ 19: no solutions for x up to 18.

After all of this searching, we can now present the following.

 t(2) = 3 from k = 1 t(3) = 4 from k = 1 and 2 t(4) = 4 from k = 1 and 2 t(5) £ 5 from k = 1 t(6) £ 6 from k = 3 t(7) £ 9 from k = 1 t(8) £ 11 from k = 2, 3, 4 and 5 t(9) £ 12 from k = 6 t(10) £ 17 from k = 2 t(11) £ 30 from k = 2 t(12) £ 28 from k = 8

The Extended Euler Conjecture is therefore not in any imminent danger of being disproved by counterexample.

For each power m, the following is also of interest.

Definition: Let t*(m) denote the smallest value of k such that a solution of 3.1 exists for k = n.

Then, we have

t*(2) = t*(3) = t*(4) = 2

t*(5) = 2 or 3

t*(6) = 3 (not proved but a fairly safe assumption)

t*(7) £ 5

t*(8) £ 5

t*(9) £ 6

For higher powers, no tight bounds are available.