A297351 Smallest number k such that, for any set S of k distinct nonzero residues mod p = prime(n), any residue mod p can be represented as a sum of zero or more distinct elements of S.

1, 2, 3, 4, 6, 6, 7, 8, 9, 10, 10, 11, 12, 12, 13, 14, 15, 15, 16, 16, 16, 17

Offset

1,2

Links

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

P. Erdős and H. Heilbronn, On the addition of residue classes mod p, Acta Arithmetica 9 (1964), 149-159.

John E. Olson, An addition theorem modulo p, Journal of Combinatorial Theory 5 (1968), pp. 45-52.

Formula

For p = prime(n) > 3, sqrt(4p + 5) - 2 < a(n) <= sqrt(4p). The former bound is due to Erdős & Heilbronn and the latter to Olson.

Prog

(PARI) sumHitsAll(v, m)=my(u=[0], n); for(i=1, #v, n=v[i]; u=Set(concat(u, apply(j->(j+n)%m, u))); if(#u==m, return(1))); 0
a(n, p=prime(n))=for(s=sqrtint(4*p+2)-1, sqrtint(4*p)-1, forvec(v=vector(s, i, [1, p-1]), if(!sumHitsAll(v, p), next(2)), 2); return(s)); sqrtint(4*p)

Crossrefs

Cf. A060019

Sequence in context: A325869 A154257 A336406 * A060019 A359100 A093451

Adjacent sequences: A297348 A297349 A297350 * A297352 A297353 A297354

Keyword

hard,more,nonn,changed

Author

Charles R Greathouse IV, Jan 24 2018

Extensions

a(13) from Charles R Greathouse IV, Jan 27 2018

a(14)-a(22) from Bert Dobbelaere, Apr 20 2019

Status

approved