The Erdős–Moser equation 1^{𝑘}+2^{𝑘}+…+(𝑚-1)^{𝑘}=𝑚^{𝑘} revisited using continued fractions

Gallot, Yves; Moree, Pieter; Zudilin, Wadim

doi:10.1090/S0025-5718-2010-02439-1

The Erdős–Moser equation $1^k+2^k+\dots +(m-1)^k=m^k$ revisited using continued fractions
HTML articles powered by AMS MathViewer

by Yves Gallot, Pieter Moree and Wadim Zudilin PDF

Math. Comp. 80 (2011), 1221-1237 Request permission

Abstract:

If the equation of the title has an integer solution with $k\ge 2$, then $m>10^{9.3\cdot 10^6}$. This was the current best result and proved using a method due to L. Moser (1953). This approach cannot be improved to reach the benchmark $m>10^{10^7}$. Here we achieve $m>10^{10^9}$ by showing that $2k/(2m-3)$ is a convergent of $\log 2$ and making an extensive continued fraction digits calculation of $(\log 2)/N$, with $N$ an appropriate integer. This method is very different from that of Moser. Indeed, our result seems to give one of very few instances where a large scale computation of a numerical constant has an application.

References

Horst Alzer, Über eine Verallgemeinerung der Bernoullischen Ungleichung, Elem. Math. 45 (1990), no. 2, 53–54 (German). MR 1039461
Jonathan Borwein and David Bailey, Mathematics by experiment, 2nd ed., A K Peters, Ltd., Wellesley, MA, 2008. Plausible reasoning in the 21st Century. MR 2473161
M. R. Best and H. J. J. te Riele, On a conjecture of Erdős concerning sums of powers of integers, Report NW 23/76 (Mathematisch Centrum Amsterdam, 1976).
R. P. Brent, A. J. van der Poorten, and H. te Riele, A comparative study of algorithms for computing continued fractions of algebraic numbers, Algorithmic number theory (Talence, 1996), Lecture Notes in Comput. Sci. 1122 (Springer, Berlin, 1996), 35–47.
Lawrence Brenton and Ana Vasiliu, Znam’s problem, Math. Mag. 75 (2002), no. 1, 3–11. MR 2107286, DOI 10.2307/3219178
William Butske, Lynda M. Jaje, and Daniel R. Mayernik, On the equation $\sum _{p|N}(1/p)+(1/N)=1$, pseudoperfect numbers, and perfectly weighted graphs, Math. Comp. 69 (2000), no. 229, 407–420. MR 1648363, DOI 10.1090/S0025-5718-99-01088-1
L. Carlitz, The Staudt-Clausen theorem, Math. Mag. 34 (1960/61), 131–146. MR 130397, DOI 10.2307/2688488
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
D. R. Curtiss, On Kellogg’s Diophantine Problem, Amer. Math. Monthly 29 (1922), no. 10, 380–387. MR 1520110, DOI 10.2307/2299023
Hubert Delange, Sur les zéros réels des polynômes de Bernoulli, Ann. Inst. Fourier (Grenoble) 41 (1991), no. 2, 267–309 (French, with English summary). MR 1137289
P. Erdős, Advanced Problem 4347, Amer. Math. Monthly 56 (1949), 343.
Leon Gerber, An extension of Bernoulli’s inequality, Amer. Math. Monthly 75 (1968), 875–876. MR 240263, DOI 10.2307/2314344
Daniel B. Grünberg and Pieter Moree, Sequences of enumerative geometry: congruences and asymptotics, Experiment. Math. 17 (2008), no. 4, 409–426. With an appendix by Don Zagier. MR 2484425
Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
Glyn Harman and Kam C. Wong, A note on the metrical theory of continued fractions, Amer. Math. Monthly 107 (2000), no. 9, 834–837. MR 1792416, DOI 10.2307/2695739
Christopher Hooley, On Artin’s conjecture, J. Reine Angew. Math. 225 (1967), 209–220. MR 207630, DOI 10.1515/crll.1967.225.209
Hendrik Jager and Pierre Liardet, Distributions arithmétiques des dénominateurs de convergents de fractions continues, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 2, 181–197 (French). MR 952514
Y. Kanada, Kanada $\pi$-Laboratory, available at http://www.super-computing.org/.
B. C. Kellner, Über irreguläre Paare höhere Ordnungen, Diplomarbeit (Mathematisches Institut der Georg-August-Universität zu Göttingen, Germany, 2002); available at http://www.bernoulli.org/˜bk/irrpairord.pdf.
Bronisław Krzysztofek, The equation $1^{n}+2^{n}+\cdots +m^{n}=(m+1)^{n}\cdot k$, Wyż. Szkoł. Ped. w Katowicach—Zeszyty Nauk. Sekc. Mat. 5 (1966), 47–54 (1967) (Polish, with English summary). MR 364097
Paul Lévy, Sur le développement en fraction continue d’un nombre choisi au hasard, Compositio Math. 3 (1936), 286–303 (French). MR 1556945
P. Liardet, Propriétés arithmétiques presque sûres des convergents, Séminaire de théorie des Nombres de Bordeaux (1986-87), exp. no. 36, 20 pp.
R. Moeckel, Geodesics on modular surfaces and continued fractions, Ergodic Theory Dynam. Systems 2 (1982), no. 1, 69–83. MR 684245, DOI 10.1017/s0143385700009585
Niels Möller, On Schönhage’s algorithm and subquadratic integer GCD computation, Math. Comp. 77 (2008), no. 261, 589–607. MR 2353968, DOI 10.1090/S0025-5718-07-02017-0
Pieter Moree, On a theorem of Carlitz-von Staudt, C. R. Math. Rep. Acad. Sci. Canada 16 (1994), no. 4, 166–170. MR 1299606
Pieter Moree, Diophantine equations of Erdős-Moser type, Bull. Austral. Math. Soc. 53 (1996), no. 2, 281–292. MR 1381770, DOI 10.1017/S0004972700017007
P. Moree, H. J. J. te Riele, and J. Urbanowicz, Divisibility properties of integers $x,\ k$ satisfying $1^k+\cdots +(x-1)^k=x^k$, Math. Comp. 63 (1994), no. 208, 799–815. MR 1257577, DOI 10.1090/S0025-5718-1994-1257577-1
P. Moree, A top hat for Moser’s four mathemagical rabbits, Amer. Math. Monthly (to appear).
Leo Moser, On the diophantine equation $1^n+2^n+3^n+\cdots +(m-1)^n=m^n.$, Scripta Math. 19 (1953), 84–88. MR 54627
R. W. K. Odoni, On the prime divisors of the sequence $w_{n+1}=1+w_1\cdots w_n$, J. London Math. Soc. (2) 32 (1985), no. 1, 1–11. MR 813379, DOI 10.1112/jlms/s2-32.1.1
Jerzy Urbanowicz, Remarks on the equation $1^k+2^k+\cdots +(x-1)^k=x^k$, Nederl. Akad. Wetensch. Indag. Math. 50 (1988), no. 3, 343–348. MR 964840
A. J. Yee, $\gamma$-cruncher—A Multi-Threaded Pi-Program, see http://www.numberworld.org/.