A086342 -id:A086342 - 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

A143069 Least number k such that n*k has the fewest possible ones in its binary expansion.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 5, 1, 1, 1, 1, 1, 27, 1, 1, 3, 3, 1, 41, 5, 19, 1, 565, 1, 1, 1, 1, 1, 1, 1, 7085, 27, 7, 1, 25, 1, 3, 3, 1, 3, 11, 1, 1, 41, 1, 5, 1266205, 19, 7, 1, 9, 565, 9099507, 1, 17602325, 1, 1, 1, 1, 1, 128207979, 1, 1, 1, 119, 1, 1, 7085, 1, 27, 5, 7, 13

Offset: 1

T. D. Noe, Jul 22 2008

nonn

a(n)=1 indicates that n is a sturdy number (A125121); that is, no multiple of n has fewer ones than the binary expansion of n. A086342(n) gives the least possible number of ones in the binary expansion of a multiple of n. Compare with A143073.

T. D. Noe, Table of n, a(n) for n=1..1000
Trevor Clokie et al., Computational Aspects of Sturdy and Flimsy Numbers, arxiv preprint arXiv:2002.02731 [cs.DS], February 7 2020.

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

A278968 Least number k such that pk is of minimal Hamming weight, where p is the n-th prime.

Original entry on oeis.org

1, 1, 1, 1, 3, 5, 1, 27, 3, 565, 1, 7085, 25, 3, 11, 1266205, 9099507, 17602325, 128207979, 119, 1, 13

Offset: 1

Charles R Greathouse IV, Dec 02 2016

Cf. A278966, A278967, 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/p

A308730 Smallest prime p for which n is the least number of 1's in the base-2 representation of a multiple of p.

Original entry on oeis.org

2, 3, 7, 89, 31, 13367, 127, 2099863, 178481

Offset: 1

Jeffrey Shallit, Jun 20 2019

It is not known if a(n) actually exists for all n. If there are infinitely many Mersenne primes, then a(n) is defined for infinitely many n.

The corresponding multipliers for n = 1,2,...,7 are 1,1,1,1,1,5,1,1,1. (Computations done by Leon Witzman.)

K. B. Stolarsky, Integers whose multiples have anomalous digital frequencies, Acta Arithmetica 38 (1980), 117-128, DOI:10.4064/aa-38-2-117-128.

Cf. A086342, A278966.

A086342(a(n)) = n. - Rémy Sigrist, Jul 06 2019

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

A143069 Least number k such that n*k has the fewest possible ones in its binary expansion.

Views

Author

Keywords

Comments

Links

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A278968 Least number k such that pk is of minimal Hamming weight, where p is the n-th prime.

Views

Author

Keywords

Crossrefs

Programs

PARI

A308730 Smallest prime p for which n is the least number of 1's in the base-2 representation of a multiple of p.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula