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

%I #15 Jun 23 2019 21:48:48

%S 7,23,47,71,73,79,103,151,167,191,199,239,263,271,311,337,359,367,383,

%T 439,463,479,487,503,599,607,631,647,719,727,743,751,823,839,863,887,

%U 919,937,967,983,991,1031,1039,1063,1087,1151,1223,1231,1279,1289,1303

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

%C 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.

%H Robert Israel, <a href="/A308732/b308732.txt">Table of n, a(n) for n = 1..10000</a>

%H C. Elsholtz, <a href="https://doi.org/10.1017/S000497271600023X">Almost all primes have a multiple of small Hamming weight</a>, Bull. Aust. Math. Soc. 94 (2016), 224-235.

%H K. B. Stolarsky, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa38/aa3825.pdf">Integers whose multiples have anomalous digital frequencies</a>, Acta Arithmetica 38 (1980), 117-128.

%p filter:= proc(n) local S, r, j;

%p if not isprime(n) then return false fi;

%p r:= numtheory:-order(2,n);

%p if r::even then return false fi;

%p S:= {seq(2 &^ j mod n, j=1..r)};

%p S intersect map(t -> -t-1 mod n, S) <> {}

%p end proc:

%p select(filter, [seq(i,i=3..2000, 2)]); # _Robert Israel_, Jun 23 2019

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

%K nonn,base

%O 1,1

%A _Jeffrey Shallit_, Jun 20 2019