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.

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,2

Comments

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.

References

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.]

Links

Table of n, a(n) for n=1..69.

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.

Formula

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.

Crossrefs

Cf. A079611, A174406, A287286.

Sequence in context: A091278 A127473 A289625 * A079611 A246763 A319070

Adjacent sequences: A040001 A040002 A040003 * A040005 A040006 A040007

Keyword

nonn

Author

Simon Plouffe, Aug 01 1998

Extensions

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

Edited by Andrey Zabolotskiy, Jun 10 2017

Status

approved