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

Author

Charles R Greathouse IV, Jan 24 2018

Keywords

• hard
• more
• nonn

Links

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

Crossrefs

Cf. A060019

Programs

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)

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.

Extensions

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

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