A278968 -id:A278968 - cp's OEIS frontend

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

Charles R Greathouse IV, Dec 02 2016

nonn

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

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

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

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

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 *)

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

a(n) = A000120(A278967(n)). In particular, a(n) = A000120(prime(n)) whenever prime(n) is in A143027. - Max Alekseyev, May 22 2025

A278967 a(n) = least multiple of the n-th prime that has the minimum Hamming weight (=A278966(n)).

Original entry on oeis.org

2, 3, 5, 7, 33, 65, 17, 513, 69, 16385, 31, 262145, 1025, 129, 517, 67108865, 536870913, 1073741825, 8589934593, 8449, 73, 1027, 2199023255553, 89, 16777217, 1125899906842625, 515, 9007199254740993, 262145, 16385, 127, 36893488147419103233, 17179869185, 590295810358705651713, 18889465931478580854785

Offset: 1

Charles R Greathouse IV, Dec 02 2016

nonn

Apart from the first term, all terms are odd.

			2 = 2^1 has Hamming weight 1 and so a(1) = 2.
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.
5 = 2^2 + 2^0 has Hamming weight 2 and so similarly a(3) = 5.
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.
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.

Contains A143027 as subsequence.

Cf. A278966, A278968, A086342.

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
a(n,p=prime(n))=my(m=min1s(p),t=p,k=2*p); while(hammingweight(t)>m, t+=k); t

a(n) = 2^(A014664(n)/2) + 1 whenever A014664(n) is even. Also, a(n) = prime(n) whenever prime(n) is in A143027. - Max Alekseyev, May 22 2025

a(23)-a(25) from Charles R Greathouse IV, Dec 09 2016

Name clarified and terms a(26) onward added by Max Alekseyev, May 22 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula