A040004 - OEIS

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

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