A278966 - OEIS

A278966

Least Hamming weight of multiples of the n-th prime.

1, 2, 2, 3, 2, 2, 2, 2, 3, 2, 5, 2, 2, 2, 3, 2, 2, 2, 2, 3, 3, 3, 2, 4, 2, 2, 3, 2, 2, 2, 7, 2, 2, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 2, 2, 3, 2, 4, 2, 2, 4, 3, 2, 2, 2, 3, 2, 3, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 2, 2, 2, 4, 2, 3, 2, 2, 2, 2, 3, 2, 3, 3, 2, 2, 3, 2, 2, 2, 2

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

Since all primes after the first are odd, a(n) > 1 for n > 1.

a(n) = 2 if and only if A014664(n) is even, or equivalently prime(n) is not in A014663. - Robert Israel, Dec 08 2016

If prime(n) = A000668(k), then a(n) = A000043(k). - Robert Israel, Dec 20 2016

LINKS

Robert Israel, Table of n, a(n) for n = 1..1000

MAPLE

f:= proc(n) local p, R, V, W, k, v, r;

p:= ithprime(n);

R:= {seq(2 &^ i mod p, i=0..numtheory:-order(2, p)-1)};

Rm:= map(t -> p-t, R);

V:= R;

W:= V;

for k from 2 do

if nops(V intersect Rm) > 0 then return k fi;

V:= {seq(seq(v+r mod p, v=V), r=R)} minus W;

W:= W union V;

end proc:

f(1):= 1:

map(f, [$1..100]); # Robert Israel, Dec 20 2016

MATHEMATICA

a[n_] := Module[{p, R, V, W, k, v, r}, p = Prime[n]; R = Union @ Table[ PowerMod[2, i, p], {i, 0, MultiplicativeOrder[2, p]-1}]; Rm = p - R; V = R; W = V; For[k = 2, True, k++, If[Length[V ~Intersection~ Rm] > 0, Return[k]]; V = Union@ Flatten@ Table[Table[v + Mod[r, p], {v, V}], {r, R}] ~Complement~ W; {W, W ~Union~ V}]];

a[1] = 1;

Array[a, 100] (* Jean-François Alcover, Jun 08 2020, after Robert Israel *)

PROG

(PARI) a(n, p=prime(n))=my(o=znorder(Mod(2, p)), v1=Set(powers(Mod(2, p), o)), v=v1, s=1); while(!setsearch(v, Mod(0, p)), v=setbinop((x, y)->x+y, v, v1); s++); s

CROSSREFS

Cf. A014663, A014664, A278967, A278968, A086342.

Sequence in context: A078545 A163105 A152235 * A374383 A123582 A214861

Adjacent sequences: A278963 A278964 A278965 * A278967 A278968 A278969

KEYWORD

nonn

AUTHOR

Charles R Greathouse IV, Dec 02 2016

STATUS

approved