A174406 -id:A174406 - cp's OEIS frontend

A002804 (Presumed) solution to Waring's problem: g(n) = 2^n + floor((3/2)^n) - 2.

1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223, 8384, 16673, 33203, 66190, 132055, 263619, 526502, 1051899, 2102137, 4201783, 8399828, 16794048, 33579681, 67146738, 134274541, 268520676, 536998744, 1073933573, 2147771272, 4295398733, 8590581749

Offset: 1

N. J. A. Sloane

g(n) is the smallest number s such that every natural number is the sum of at most s n-th powers of natural numbers.
It is known (Kubina and Wunderlich, 1990) that g(n) = 2^n + floor((3/2)^n) - 2 for all n <= 471600000. This formula is conjectured to be correct for all n (see A174420).
Mahler showed that there are only finitely many n's for which this formula fails. - Tomohiro Yamada, Sep 23 2017
This sequence (which corresponds to Waring's original conjecture) is much easier to compute than A079611, the problem of finding the minimal s = G(n) for almost all (= sufficienly large) integers. See Wikipedia for a one-line proof that this value for g(n), conjectured by J. A. Euler in 1772, is indeed a lower bound; it is known to be tight if 2^n*frac((3/2)^n) + floor((3/2)^n) <= 2^n, and no counterexample to this inequality is known. - M. F. Hasler, Jun 29 2014

Calvin C. Clawson, Mathematical Mysteries: The Beauty and Magic of Numbers (Basic Books 1996) 252-257.
Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 2.30.1, p. 195.
G. H. Hardy, Collected Papers. Vols. 1-, Oxford Univ. Press, 1966-; see vol. 1, p. 668.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 337.
S. Pillai, On Waring's Problem, Journal of Indian Math. Soc., 2 (1936), 16-44
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 138.
P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 239.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 249-250.
R. C. Vaughan and T. D. Wooley, Waring's problem: a survey, pp. 285-324 of Surveys in Number Theory (Urbana, May 21, 2000), ed. M. A. Bennett et al., Peters, 2003.
Edward Waring, Meditationes algebraicae, Cantabrigiae: typis Academicis excudebat J. Archdeacon, 1770.

T. D. Noe, Table of n, a(n) for n = 1..200
Brennan Benfield and Oliver Lippard, Integers that are not the sum of positive powers, arXiv:2404.08193 [math.NT], 2024.
Leonard E. Dickson, The Waring Problem and its generalizations, Bulletin of the AMS, 42 (1936) 833-842.
Jeffrey M. Kubina and Marvin C. Wunderlich, Extending Waring's conjecture to 471,600,000, Math. Comp., 55, no. 192 (1990): 815-820.
A. V. Kumchev and D. I. Tolev, An invitation to additive number theory, arXiv:math/0412220 [math.NT], 2004.
Feihu Liu and Guoce Xin, On Frobenius Formulas of Power Sequences, arXiv:2210.02722 [math.CO], 2022. See p. 22.
Kurt Mahler, On the fractional parts of the powers of a rational number (II), Mathematika, 4 (1957) 122-124 Math. Rev. 20:33.
Ramin Takloo-Bighash, What about geometry?, A Pythagorean Introduction to Number Theory, Undergraduate Texts in Mathematics, Springer, Cham, 2018, 165-185.
Michel Waldschmidt, Open Diophantine problems, arXiv:math/0312440 [math.NT], 2003-2004.
Eric Weisstein's World of Mathematics, Waring's Problem.
Wikipedia, Waring's Problem.

Cf. A002376, A002377, A079611, A174406, A174420, A297446 (for info on Mathematica functions).

[2^n+Floor((3/2)^n)-2: n in [1..40]]; // Vincenzo Librandi, Aug 15 2015

Maple
```
A002804 := n->2^n+floor( (3/2)^n ) -2;
```

a[n_] := 2^n + Floor[(3/2)^n] - 2; Array[a, 31] (* Robert G. Wilson v, Oct 29 2013 *)
x[n_] := -(1/2) + (3/2)^n + ArcTan[Cot[(3/2)^n Pi]]/Pi; a[n_] := 2^n + x[n] - 2; Array[a, 31]  (* Fred Daniel Kline, Jan 11 2018 *)

a(n)=2^n+(3^n>>n)-2 \\ Charles R Greathouse IV, Feb 01 2013

def A002804(n): return (1<>n)-2 # Chai Wah Wu, Jun 25 2024

[2^n+int((3/2)^n)-2 for n in range(1,34)] # Stefano Spezia, Dec 08 2024

A079611 Waring's problem: conjectured values for G(n), the smallest number m such that every sufficiently large number is the sum of at most m n-th powers of positive integers.

Original entry on oeis.org

1, 4, 4, 16, 6, 9, 8, 32, 13, 12, 12, 16, 14, 15, 16, 64, 18, 27, 20, 25

Offset: 1

N. J. A. Sloane, Jan 28 2003

The only certain values are G(1) = 1, G(2) = 4 and G(4) = 16.

See A002804 for the simpler problem of Waring's original conjecture, which does not restrict the bound to "sufficiently large" numbers. - M. F. Hasler, Jun 29 2014

			It is known that every sufficiently large number is the sum of 16 fourth powers, and 16 is the smallest number with this property, so a(4) = G(4) = 16. (The numbers 16^k*31 are not the sum of fewer than 16 fourth powers.)

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 395 (shows G(4) >= 16).
R. C. Vaughan and T. D. Wooley, Waring's problem: a survey, pp. 285-324 of Surveys in Number Theory (Urbana, May 21, 2000), ed. M. A. Bennett et al., Peters, 2003.

H. Davenport, On Waring's problem for fourth powers, Annals of Mathematics, 40 (1939), 731-747. (Shows that G(4) <= 16.)
Wikipedia, Waring's Problem.
Trevor D. Wooley, On Waring's problem for intermediate powers, arXiv:1602.03221 [math.NT], 2016.

Cf. A002376, A002377, A002804, A174406.

Entry revised Jun 29 2014

A287286 a(n) = smallest integer s such that every element of the ring of integers mod t for any t can be written as a sum of s n-th powers.

Original entry on oeis.org

1, 4, 4, 15, 5, 9, 4, 32, 13, 12, 11, 16, 6, 14, 15, 64, 6, 27, 4, 25, 24, 23, 23, 32, 10, 26, 40, 29, 29, 31, 5, 128, 33, 10, 35, 37, 9, 9, 39, 41, 41, 49, 12, 44, 15, 47, 10, 64, 13, 62, 51, 53, 53, 81, 60, 56, 14, 59, 5, 61, 11, 12, 63, 256, 65, 67, 12, 68, 69, 71, 6, 73, 16, 74, 75, 16, 14, 84

Offset: 1

David Covert, May 22 2017

nonn

One needs only check a finite number of values (depending on the power).
See Small's paper in references for precise quantitive information.
a(2) <= 4 follows from Lagrange's four squares theorem.
Differs from A040004 only at k=4. - Andrey Zabolotskiy, Jun 03 2017

			a(3) <= 4 states that every element of every ring of integers mod m can be written as a sum of 4 (or fewer) cubes. a(3) >= 4, since in Z/9Z, the cubes are {0,1,8} so that 4 is not the sum of any three cubes in Z/9Z. Hence a(3) = 4.

G. H. Hardy and J. E. Littlewood, Some Problems of "Partitio Numerorum" (VIII): The Number Gamma(k) in Waring's Problem, Proc London Math Soc. 28 (1928), 518--542. [G. H. Hardy, Collected Papers. Vols. 1-, Oxford Univ. Press, 1966-; see vol. 1, pp. 406-530.]
Wladyslaw Narkiewicz, Rational Number Theory in the 20th Century: From PNT to FLT, Springer Science & Business Media, 2011, pages 154-155.

H. Sekigawa and K. Koyama, Nonexistence Conditions of a Solution for the congruence x_1^k + ... + x_s^k = N (mod p^n), Math. Comp. 68 (1999), 1283--1297.
C. Small, Waring's problem mod n, Amer. Math. Monthly 84 (1977), no. 1, 12--25.
R. C. Vaughan and T. D. Wooley, Waring’s problem: a survey, Number Theory for the Millennium, III (Urbana, IL, 2000), A K Peters, Natick, MA, 2002, pp. 301-340.

Cf. A079611, A174406, A040004.

Edited by Andrey Zabolotskiy, Jun 10 2017

A040004 a(n) = smallest integer s such that for all i, all primes p and all m the congruence (x_1)^n + ... + (x_s)^n == m (mod p^i) has a primitive solution.

Original entry on oeis.org

1, 4, 4, 16, 5, 9, 4, 32, 13, 12, 11, 16, 6, 14, 15, 64, 6, 27, 4, 25, 24, 23, 23, 32, 10, 26, 40, 29, 29, 31, 5, 128, 33, 10, 35, 37, 9, 9, 39, 41, 41, 49, 12, 44, 15, 47, 10, 64, 13, 62, 51, 53, 53, 81, 60, 56, 14, 59, 5, 61, 11, 12, 63, 256, 65, 67, 12, 68, 69

Offset: 1

Simon Plouffe, Aug 01 1998

nonn

Primitive solution is a solution in which not all x_i are 0 (mod p).
This quantity is usually denoted by Gamma(n).
A287286 differs only at n=4: as any 4th power equals 0 or 1 (mod 16) and at least one odd 4th power is needed, 16 odd 4th powers are needed because of 0 (mod 16), but if all-even powers are allowed, 15 is enough.

G. H. Hardy and J. E. Littlewood, Some problems of `Partito Numerorum', IV, Math. Zeit., 12 (1922), 161-168. [G. H. Hardy, Collected Papers. Vols. 1-, Oxford Univ. Press, 1966-; see vol. 1, p. 466.]

Hiroshi Sekigawa and Kenji Koyama, Nonexistence conditions of a solution for the congruence x_1^k + ... + x_s^k = N (mod p^n), Math. Comp. 68 (1999), 1283-1297.

Cf. A079611, A174406, A287286.

For k > 2:
if k = 2^t, t>1, then a(k) = 4*k = 2^(t+2);
if k = 3*2^t, t>1, then a(k) = 2^(t+2);
if k = p^t*(p-1), where p is an odd prime and t>0, then a(k) = p^(t+1);
if k = p^t*(p-1)/2, then a(k) = (p^(t+1)-1)/2, except when k=p=3;
otherwise, if k = p-1, then a(k) = k+1 = p;
otherwise, if k = (p-1)/2, then a(k) = k = (p-1)/2;
in other cases, 3 < a(k) <= k.

More terms and a(30) corrected from the Sekigawa & Koyama paper by Andrey Zabolotskiy, May 31 2017

Edited by Andrey Zabolotskiy, Jun 10 2017

cp's OEIS Frontend

A002804 (Presumed) solution to Waring's problem: g(n) = 2^n + floor((3/2)^n) - 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Sage

A079611 Waring's problem: conjectured values for G(n), the smallest number m such that every sufficiently large number is the sum of at most m n-th powers of positive integers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A287286 a(n) = smallest integer s such that every element of the ring of integers mod t for any t can be written as a sum of s n-th powers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A040004 a(n) = smallest integer s such that for all i, all primes p and all m the congruence (x_1)^n + ... + (x_s)^n == m (mod p^i) has a primitive solution.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions