A079611 -id:A079611 - cp's OEIS frontend

A018887 Waring's problem: historical upper bounds on A079611, as stated in a web page in 1996.

1, 4, 7, 16, 18, 27, 36, 42, 55, 63, 70, 79, 87, 95, 103, 112, 120, 129, 138, 146

Offset: 1

dead

In 1996, these values were listed as upper bounds on A079611 in Eric Weisttein's former web page www.gps.caltech.edu/~eww/math/wnode21.html.

Included for historical reasons only.

See A079611 for the current information about this sequence.

Entry revised by N. J. A. Sloane, Jun 29 2014

Edited by M. F. Hasler, Jun 29 2014

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

Original entry on oeis.org

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

A099591 Numbers that are the sum of no fewer than 17 biquadrates (4th powers).

Original entry on oeis.org

47, 62, 63, 77, 78, 79, 127, 142, 143, 157, 158, 159, 207, 222, 223, 237, 238, 239, 287, 302, 303, 317, 318, 319, 367, 382, 383, 397, 398, 399, 447, 462, 463, 477, 478, 479, 527, 542, 543, 557, 558, 559, 607, 622, 623, 687, 702, 703, 752, 767, 782, 783

Offset: 1

Ralf Stephan, Oct 25 2004

There are 96 members in the sequence, the largest being 13792, see the Deshouillers et al. references.

			62 is the sum of 17 4th powers and no fewer, so 62 is a member.
63 is the sum of 18 4th powers and no fewer, so 63 is a member, although it is not a member of A046048.

T. D. Noe, Table of n, a(n) for n = 1..96 (complete sequence)
J.-M. Deshouillers, F. Hennecart and B. Landreau, Waring's Problem for sixteen biquadrates - numerical results, Journal de Théorie des Nombres de Bordeaux 12 (2000), pp. 411-422.
J.-M. Deshouillers, K. Kawada and T. D. Wooley, On Sums of Sixteen Biquadrates, Mém. Soc. Math. de France, Paris, 2005.
Eric Weisstein's World of Mathematics, Biquadratic Number
Eric Weisstein's World of Mathematics, Warings Problem

Cf. A002377, A079611, A046048.

f[n_] := f[n] = (k = 0; While[k++; PowersRepresentations[n, k, 4] == {}]; k); Select[Range[800], f[#] >= 17 &] (* Jean-François Alcover, Sep 02 2011 *)

a(25) changed from 368 to 367 by T. D. Noe, Sep 07 2006

A174406 a(n) = smallest number u such that almost every number is the sum of at most u n-th powers of positive numbers.

Original entry on oeis.org

1, 4, 4, 15

Offset: 1

N. J. A. Sloane, Nov 27 2010

A variant of Waring's problem.
"Almost all" means that the exceptions have zero density.
Only three other values of the sequence are known: a(8) = 32, a(16) = 64, and a(32) = 128. The cited survey by Vaughan and Wooley shows that G_1(8) = 32, G_1(16) = 64, and G_1(32) = 128.  The quantity G_1(5) has not been evaluated, nor have G_1(6) and G_1(7). - David Covert, Jun 29 2016

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. A002804, A079611.

a(5)-a(7) removed by David Covert, Jun 29 2016

A274459 Least number of perfect powers that add up to n.

Original entry on oeis.org

1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 3, 2, 2, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 1, 2, 1, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 3, 3, 2, 2, 3, 2, 2, 2, 3, 3, 2, 1, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 3, 2, 1, 2, 3, 3, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 1, 2, 3, 3, 2

Offset: 1

Sergio Pimentel, Jun 23 2016

nonn

Least number of perfect powers (A001597) needed to add up to n.
This sequence is close to but not exactly equal to A063274.
a(n) is at most 4 since any number can be written as a sum of 4 squares (Lagrange's theorem), but it is possible that for a sufficiently large n, a(n) < 4.
a(n) <= a(i) + a(n-i) for 1 <= i <= n-1. (for computational ease, the maximum value for i can be chosen as floor(n/2)). a(1991) = 4. for 1992 <= k <= 20000, there is no k such that a(k) = 4. - David A. Corneth, Jun 24 2016 [Next such k is 25887, see A113505. - Vaclav Kotesovec, Jun 25 2016]

			a(31) = 2 since 31 can be written as the sum of two (31 = 3^3 + 2^2 = 27 + 4) but no fewer than two perfect powers.

David A. Corneth, Table of n, a(n) for n = 1..10000

Cf. A001597, A002376, A002377, A002828, A002804, A079611, A063274, A188462, A225926.

Cf. A063275 (indices for which a(n)=3), A113505 (indices for which a(n)=4).

nn = 72; t = Select[Range@ nn, # == 1 || GCD @@ FactorInteger[#][[All, 2]] > 1 &]; Table[Min@ Map[Length, Select[IntegerPartitions@ n, AllTrue[#, MemberQ[t, #] &] &]], {n, nn}] (* Michael De Vlieger, Jun 23 2016, after Ant King at A001597 *)

lista(n) = {my(v = vector(n)); for(i = 2,sqrtint(n), for(j = 2, logint(n, i), v[i^j] = 1)); v[1]=1; v[2]=2; for(i=3, #v, if(v[i]==0, v[i] = vecmin(vector( i\2, k,v[k] + v[i-k]))));v} \\ David A. Corneth, Jun 24 2016; corrected by Peter Schorn, Jun 09 2022

More terms from Michael De Vlieger, Jun 23 2016

Terms from a(74) from David A. Corneth, Jun 24 2016

A018886 Waring's problem: least positive integer requiring maximum number of terms when expressed as a sum of positive n-th powers.

Original entry on oeis.org

1, 7, 23, 79, 223, 703, 2175, 6399, 19455, 58367, 176127, 528383, 1589247, 4767743, 14319615, 42991615, 129105919, 387186687, 1161822207, 3486515199, 10458497023, 31377588223, 94136958975, 282427654143, 847282962431, 2541815332863

Offset: 1

N. J. A. Sloane

a(n) = (Q-1)*(2^n) + (2^n-1)*(1^n) is a sum of Q + 2^n - 2 terms, Q = trunc(3^n / 2^n).

			a(3) = 23 = 16 +  7 = 2*(2^3) +  7*(1^3) is a sum of 9 cubes;
a(4) = 79 = 64 + 15 = 4*(2^4) + 15*(1^4) is a sum of 19 biquadrates.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 393.

T. D. Noe, Table of n, a(n) for n = 1..200
P. Pollack, Analytic and Combinatorial Number Theory Course Notes, exercise 7.1.1. p. 277.
Eric Weisstein's World of Mathematics, Waring's Problem.

Cf. A079611, A185187.

Cf. A000079, A002379.

A018886 := proc(n)
2^n*floor((3/2)^n)-1
end proc: # R. J. Mathar, May 07 2015

a[n_]:=-1+2^n*Floor[(3/2)^n]
a[Range[1,20]] (* Julien Kluge, Jul 21 2016 *)

def a(n): return (3**n//2**n-1)*2**n + (2**n-1)
print([a(n) for n in range(1, 27)]) # Michael S. Branicky, Dec 17 2021

def A018886(n): return (3**n&-(1<Chai Wah Wu, Jun 25 2024

a(n) = 2^n*floor((3/2)^n) - 1 = 2^n*A002379(n) - 1.

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

A356037 Conjecturally, a(n) is the smallest number m such that every natural number is a sum of at most m n-simplex numbers.

Original entry on oeis.org

1, 3, 5, 8, 10, 13, 15, 15, 19, 24

Offset: 1

Mohammed Yaseen, Jul 24 2022

n-simplex numbers are {binomial(k,n); k>=n}.
This problem is the simplex number analog of Waring's problem.
a(2) = 3 was proposed by Fermat and proved by Gauss, see A061336.
Pollock conjectures that a(3) = 5. Salzer and Levine prove this for numbers up to 452479659. See A104246 and A000797.
Kim gives a(4)=8, a(5)=10, a(6)=13 and a(7)=15 (not proved).

			2-simplex numbers are {binomial(k,2); k>=2} = {1,3,6,10,...}, the triangular numbers. 3 is the smallest number m such that every natural number is a sum of at most m triangular numbers. So a(2)=3.
3-simplex numbers are {binomial(k,3); k>=3} = {1,4,10,20,...}, the tetrahedral numbers. 5 is presumed to be the smallest number m such that every natural number is a sum of at most m tetrahedral numbers. So a(3)=5.

Hyun Kwang Kim, On regular polytope numbers, Proc. Amer. Math. Soc. 131 (2003), p. 65-75.

Cf. A002804, A079611.
Minimal number of x-simplex numbers whose sum equals n: A061336 (x=2), A104246 (x=3), A283365 (x=4), A283370 (x=5).
x-simplex numbers: A000217 (x=2), A000292 (x=3), A000332 (x=4), A000389 (x=5), A000579 (x=6), A000580 (x=7), A000581 (x=8), A000582 (x=9).

cp's OEIS Frontend

A018887 Waring's problem: historical upper bounds on A079611, as stated in a web page in 1996.

Views

Author

Keywords

Comments

Crossrefs

Extensions

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

A099591 Numbers that are the sum of no fewer than 17 biquadrates (4th powers).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A174406 a(n) = smallest number u such that almost every number is the sum of at most u n-th powers of positive numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A274459 Least number of perfect powers that add up to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A018886 Waring's problem: least positive integer requiring maximum number of terms when expressed as a sum of positive n-th powers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

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.