login
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

%I #21 Jun 10 2017 23:01:37

%S 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,

%T 40,29,29,31,5,128,33,10,35,37,9,9,39,41,41,49,12,44,15,47,10,64,13,

%U 62,51,53,53,81,60,56,14,59,5,61,11,12,63,256,65,67,12,68,69

%N 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.

%C Primitive solution is a solution in which not all x_i are 0 (mod p).

%C This quantity is usually denoted by Gamma(n).

%C 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.

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

%H Hiroshi Sekigawa and Kenji Koyama, <a href="https://doi.org/10.1090/S0025-5718-99-01067-4">Nonexistence conditions of a solution for the congruence x_1^k + ... + x_s^k = N (mod p^n)</a>, Math. Comp. 68 (1999), 1283-1297.

%F For k > 2:

%F if k = 2^t, t>1, then a(k) = 4*k = 2^(t+2);

%F if k = 3*2^t, t>1, then a(k) = 2^(t+2);

%F if k = p^t*(p-1), where p is an odd prime and t>0, then a(k) = p^(t+1);

%F if k = p^t*(p-1)/2, then a(k) = (p^(t+1)-1)/2, except when k=p=3;

%F otherwise, if k = p-1, then a(k) = k+1 = p;

%F otherwise, if k = (p-1)/2, then a(k) = k = (p-1)/2;

%F in other cases, 3 < a(k) <= k.

%Y Cf. A079611, A174406, A287286.

%K nonn

%O 1,2

%A _Simon Plouffe_, Aug 01 1998

%E More terms and a(30) corrected from the Sekigawa & Koyama paper by _Andrey Zabolotskiy_, May 31 2017

%E Edited by _Andrey Zabolotskiy_, Jun 10 2017