cp's OEIS Frontend

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

%I A164022 #28 Nov 15 2020 03:44:21
%S A164022 2,2,3,17,5,13,7,17,19,41,11,97,13,29,31,67,17,37,19,41,43,89,23,97,
%T A164022 101,53,109,113,29,61,31,131,67,137,71,73,37,307,79,163,41,337,43,89,
%U A164022 181,373,47,97,197,101,103,211,53,109,223,113,229,233,59,241,61,251,127,257
%N A164022 a(n) = the smallest prime that, when written in binary, starts with the substring of n in binary.
%C A164022 The argument used to prove that A018800(n) always exists applies here also. - _N. J. A. Sloane_, Nov 14 2014
%H A164022 Alois P. Heinz, <a href="/A164022/b164022.txt">Table of n, a(n) for n = 1..20000</a>
%H A164022 <a href="/index/Pri#piden">Index entries for primes involving decimal expansion of n</a>
%e A164022 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.
%p A164022 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
%t A164022 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 *)
%Y A164022 A018800 is the base-10 analog.
%Y A164022 Row n=1 of A262365.  Cf. A108234 (number of new bits), A208241 (proper substring).
%K A164022 base,nonn
%O A164022 1,1
%A A164022 _Leroy Quet_, Aug 08 2009
%E A164022 Corrected terms a(1) and a(2) (with help from Ray Chandler) _Leroy Quet_, Aug 16 2009
%E A164022 Extended by _R. J. Mathar_, Sep 13 2009