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

Author

Simon Plouffe, Aug 01 1998

Keywords

• nonn

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

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

Crossrefs

Cf. A079611, A174406, A287286.

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.

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