A308732 Primes p such that the smallest possible number of 1's in binary representation of a multiple of p equals 3.

7, 23, 47, 71, 73, 79, 103, 151, 167, 191, 199, 239, 263, 271, 311, 337, 359, 367, 383, 439, 463, 479, 487, 503, 599, 607, 631, 647, 719, 727, 743, 751, 823, 839, 863, 887, 919, 937, 967, 983, 991, 1031, 1039, 1063, 1087, 1151, 1223, 1231, 1279, 1289, 1303

Offset: 1

Author

Jeffrey Shallit, Jun 20 2019

Keywords

• nonn
• base

Comments

The first few corresponding multipliers that give three 1's are (for the numbers listed above) are 1, 3, 11, 119, 1, 13, 5, 7, 791, 87839, 247, 17970575, 3987, 8048111, 7, 49, 23, 2995944847, 5607007, 7, 2319663.

Links

• Robert Israel, Table of n, a(n) for n = 1..10000
• Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, Bull. Aust. Math. Soc. 94 (2016), 224-235.
• Eugen J. Ionascu, Florian Luca, and Thomas Merino, On the average value of the minimal Hamming multiple, arXiv:2412.10839 [math.NT], 2024. See pp. 4, 17.
• Kenneth B. Stolarsky, Integers whose multiples have anomalous digital frequencies, Acta Arithmetica 38 (1980), 117-128.

Crossrefs

Cf. A014662, which enumerates the same sequence for two 1's instead of three.

Programs

Maple

filter:= proc(n) local S, r, j;
  if not isprime(n) then return false fi;
  r:= numtheory:-order(2,n);
  if r::even then return false fi;
  S:= {seq(2 &^ j mod n, j=1..r)};
  S intersect map(t -> -t-1 mod n, S) <> {}
end proc:
select(filter, [seq(i,i=3..2000, 2)]); # Robert Israel, Jun 23 2019