A164022 a(n) = the smallest prime that, when written in binary, starts with the substring of n in binary.

2, 2, 3, 17, 5, 13, 7, 17, 19, 41, 11, 97, 13, 29, 31, 67, 17, 37, 19, 41, 43, 89, 23, 97, 101, 53, 109, 113, 29, 61, 31, 131, 67, 137, 71, 73, 37, 307, 79, 163, 41, 337, 43, 89, 181, 373, 47, 97, 197, 101, 103, 211, 53, 109, 223, 113, 229, 233, 59, 241, 61, 251, 127, 257

Offset: 1

Author

Leroy Quet, Aug 08 2009

Keywords

• base
• nonn

Comments

The argument used to prove that A018800(n) always exists applies here also. - N. J. A. Sloane, Nov 14 2014

Examples

			4 in binary is 100. Looking at the binary numbers that begin with 100: 100 = 4 in decimal is composite; 1000 = 8 in decimal is composite; 1001 = 9 in decimal is composite; 10000 = 16 in decimal is composite. But 10001 = 17 in decimal is prime. So a(4) = 17.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000
• Index entries for primes involving decimal expansion of n

Crossrefs

A018800 is the base-10 analog.

Row n=1 of A262365. Cf. A108234 (number of new bits), A208241 (proper substring).

Programs

Maple

A164022 := proc(n) dgs2 := convert(n,base,2) ; ldgs := nops(dgs2) ; for i from 1 do p := ithprime(i) ; if p >= n then pdgs := convert(p,base,2) ; if [op(nops(pdgs)+1-ldgs.. nops(pdgs),pdgs)] = dgs2 then RETURN( p) ; fi; fi; od: end: seq(A164022(n),n=1..120) ; # R. J. Mathar, Sep 13 2009

Mathematica

With[{s = Map[IntegerDigits[#, 2] &, Prime@ Range[10^4]]}, Table[Block[{d = IntegerDigits[n, 2]}, FromDigits[#, 2] &@ SelectFirst[s, Take[#, UpTo@ Length@ d] == d &]], {n, 64}]] (* Michael De Vlieger, Sep 23 2017 *)

Extensions

Corrected terms a(1) and a(2) (with help from Ray Chandler) Leroy Quet, Aug 16 2009

Extended by R. J. Mathar, Sep 13 2009