login
Least number k which is (1) a multiple of the n-th prime and (2) of minimal Hamming weight.
2

%I #10 Jan 25 2024 07:54:39

%S 2,3,5,7,33,65,17,513,69,16385,31,262145,1025,129,517,67108865,

%T 536870913,1073741825,8589934593,8449,73,1027,2199023255553,89,

%U 16777217

%N Least number k which is (1) a multiple of the n-th prime and (2) of minimal Hamming weight.

%C Apart from the first term, all terms are odd.

%e 2 = 2^1 has Hamming weight 1 and so a(1) = 2.

%e 3 = 2^1 + 2^0 has Hamming weight 2, and any multiple of 3 has a Hamming weight at least as high, so a(2) = 3.

%e 5 = 2^2 + 2^0 has Hamming weight 2 and so similarly a(3) = 5.

%e 7 = 2^2 + 2^1 + 2^0 has Hamming weight 3, and all powers of 2 are 1, 2, or 4 mod 7, and so all multiples of 7 have Hamming weight at least 3, so a(4) = 7.

%e 11 = 2^3 + 2^1 + 2^0 has Hamming weight 3 but 33 = 2^5 + 2^0 has Hamming weight 2 so a(5) = 33.

%o (PARI) min1s(p)=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

%o a(n,p=prime(n))=my(m=min1s(p),t=p,k=2*p); while(hammingweight(t)>m, t+=k); t

%Y Cf. A278966, A278968, A086342.

%K nonn,more

%O 1,1

%A _Charles R Greathouse IV_, Dec 02 2016

%E a(23)-a(25) from _Charles R Greathouse IV_, Dec 09 2016