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
Offset: 1
Keywords
Links
- Robert Israel, Table of n, a(n) for n = 1..1000
Programs
-
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; od 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 *) -
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
Formula
a(n) = A000120(A278967(n)). In particular, a(n) = A000120(prime(n)) whenever prime(n) is in A143027. - Max Alekseyev, May 22 2025
Comments