|
%I #22 Apr 10 2024 10:40:43
%S 1,2,3,4,6,6,7,8,9,10,10,11,12,12,13,14,15,15,16,16,16,17
%N 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.
%H P. Erdős and H. Heilbronn, <a href="https://users.renyi.hu/~p_erdos/1964-18.pdf">On the addition of residue classes mod p</a>, Acta Arithmetica 9 (1964), 149-159.
%H John E. Olson, <a href="https://doi.org/10.1016/S0021-9800(68)80027-4">An addition theorem modulo p</a>, Journal of Combinatorial Theory 5 (1968), pp. 45-52.
%F 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.
%o (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
%o 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)
%Y Cf. A060019
%K hard,more,nonn,changed
%O 1,2
%A _Charles R Greathouse IV_, Jan 24 2018
%E a(13) from _Charles R Greathouse IV_, Jan 27 2018
%E a(14)-a(22) from _Bert Dobbelaere_, Apr 20 2019
|
