

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



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 alleven powers are allowed, 15 is enough.


REFERENCES

G. H. Hardy and J. E. Littlewood, Some problems of `Partito Numerorum', IV, Math. Zeit., 12 (1922), 161168. [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), 12831297.


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*(p1), where p is an odd prime and t>0, then a(k) = p^(t+1);
if k = p^t*(p1)/2, then a(k) = (p^(t+1)1)/2, except when k=p=3;
otherwise, if k = p1, then a(k) = k+1 = p;
otherwise, if k = (p1)/2, then a(k) = k = (p1)/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



