A208241 -id:A208241 - cp's OEIS frontend

A004676 Primes written in base 2.

10, 11, 101, 111, 1011, 1101, 10001, 10011, 10111, 11101, 11111, 100101, 101001, 101011, 101111, 110101, 111011, 111101, 1000011, 1000111, 1001001, 1001111, 1010011, 1011001, 1100001, 1100101, 1100111, 1101011, 1101101, 1110001, 1111111, 10000011, 10001001

Offset: 1

N. J. A. Sloane

The only primes of binary weight 2 are the Fermat primes (only five are known: 11, 101, 10001, 100000001, 10000000000000001); the repunits base 2 are the Mersenne primes. - Daniel Forgues, Nov 07 2011

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 3.

T. D. Noe, Table of n, a(n) for n = 1..1000
Chris Caldwell, The prime pages, The first 1000 primes.

Cf. A019434 Fermat primes (base 10), A000668 Mersenne primes (base 10).

Cf. A174332, A208238, A208241.

a004676 = a007088 . a000040  -- Reinhard Zumkeller, Aug 06 2012

FromDigits /@ IntegerDigits[ Prime[ Range[31]], 2] (* Robert G. Wilson v, Jun 30 2005 *)

a(n)=subst(Pol(binary(prime(n))), 'x, 10) \\ Charles R Greathouse IV, Mar 20 2013

a(n) = A007088(A000040(n)). - R. J. Mathar, Jun 03 2011

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

Original entry on oeis.org

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

Leroy Quet, Aug 08 2009

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

			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.

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

A018800 is the base-10 analog.

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

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

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 *)

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

A055011 a(n+1) = next smallest prime beginning with a(n) when written in binary, starting with 2.

Original entry on oeis.org

2, 5, 11, 23, 47, 191, 383, 3067, 12269, 196307, 6281839, 50254717, 201018869, 804075479, 1608150959, 102921661397, 1646746582367, 13173972658937, 105391781271503, 210783562543007, 3372537000688127, 26980296005505019, 863369472176160611, 6906955777409284889

Offset: 0

Henry Bottomley, May 31 2000

a(5)=191 because a(4)=47 which in binary is 101111, none of 1011110(94) 1011111(95) 10111100(188) 10111101(189) 10111110 (190) are prime, but 10111111(191) is.

Cf. A048549 for base 10 analog.

A055011, A261200 and A261201 are all essentially the same sequence.

a055011 n = a055011_list !! n
a055011_list = iterate a208241 2  -- Reinhard Zumkeller, Feb 14 2013

A055011 := proc(n)
    option remember;
    if n = 0 then
        2 ;
    else
        A208241(procname(n-1)) ;
    end if;
end proc: # R. J. Mathar, May 06 2017

a(n+1) = A208241(a(n)). - Reinhard Zumkeller, Feb 14 2013

A174332 Least prime q of which prime(n) is a proper binary substring.

Original entry on oeis.org

5, 7, 11, 23, 23, 29, 71, 79, 47, 59, 127, 101, 83, 107, 191, 107, 239, 251, 269, 199, 293, 317, 167, 179, 353, 229, 359, 431, 439, 227, 383, 263, 787, 557, 599, 607, 631, 419, 1447, 347, 359, 727, 383, 449, 709, 797, 467, 479, 739, 919, 467, 479, 967, 503, 769

Offset: 1

Robert G. Wilson v, Mar 15 2010

a(n) = A208238(A000040(n)) = A208241(A000040(n)). - Reinhard Zumkeller, Feb 14 2013

			a(1)=5 since 2_10 = 10_2 is a substring of 5_10 = 101_2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000040, A004676, A007088.

a174332 = a208238 . a000040  -- Reinhard Zumkeller, Feb 14 2013

f[n_] := Block[{k = n + 1, p = StringTake[ ToString@ IntegerDigits[ Prime@n, 2], {2, -2}]}, While[q = StringTake[ ToString@ IntegerDigits[ Prime@k, 2], {2, -2}]; StringPosition[q, p] == {}, k++ ]; Prime@k]; Array[f, 55]

A208238 Smallest prime greater than n, containing it in binary representation.

Original entry on oeis.org

2, 2, 5, 7, 17, 11, 13, 23, 17, 19, 41, 23, 89, 29, 29, 31, 67, 71, 37, 79, 41, 43, 89, 47, 97, 89, 53, 59, 113, 59, 61, 127, 131, 67, 137, 71, 73, 101, 307, 79, 163, 83, 337, 107, 89, 109, 349, 191, 97, 113, 101, 103, 211, 107, 109, 223, 113, 229, 233, 239

Offset: 0

Reinhard Zumkeller, Feb 14 2013

nonn

a(n) <= A208241(n);

A174332(n) = a(A000040(n)).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A208241, A004676, A007088, A010051, A030308.

import Data.List (genericIndex, find, isInfixOf)
import Data.Maybe (fromJust)
a208238 = genericIndex a208238_list
a208238_list = f nns $ filter ((== 1) . a010051' . fst) nns where
   f mms'@((m,ms):mms) pps'@((p,ps):pps) =
     if m == p then f mms' pps else q : f mms pps'
     where q = fst $ fromJust $ find ((ms `isInfixOf`) . snd) pps'
   nns = zip [0..] a030308_tabf

spgn[n_]:=Module[{idn2=IntegerDigits[n,2],p=NextPrime[n]},While[SequenceCount[ IntegerDigits[ p,2],idn2] == 0,p = NextPrime[p]];p]; Array[spgn,60,0] (* Harvey P. Dale, Dec 23 2023 *)

A338884 The smallest number of bits which need to be appended to the binary representation of n to reach a prime greater than n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 3, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 3, 2, 1, 2, 3, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 1, 2, 1, 4, 2, 1, 1, 2, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2

Offset: 1

Ya-Ping Lu, Nov 13 2020

nonn

a(n) is also the distance from a node to its first prime-number descendant in a binary tree defined as: root = 1 and, for any node n, the left child = 2*n and right child = 2*n + 1. The number of primes among the nodes of depth m is equal to A036378(m) for m>=2.

Cf. A000040, A036378, A208241, A005097 (where a(n)=1).

Cf. A108234 (zero or more bits).

from sympy import isprime
for n in range(1,101):
    a = 0
    k = i = 1
    while isprime(i) == 0:
        a += 1
        k = 2*k
        for i in range(k*n + 1, k*n + k):
            if isprime(i) == 1: break
    print(a)

a(n) = bitlength(A208241(n)) - bitlength(n), where bitlength = A070939. - Kevin Ryde, Nov 13 2020

A339134 Indices in A338884 where records occur.

Original entry on oeis.org

1, 4, 12, 66, 346, 5876, 95078, 9411222, 1894078221

Offset: 1

Ya-Ping Lu, Nov 24 2020

It seems that A338884(a(n)) = n and 3*sqrt(log(a(n)))/n ~ O(1).

Cf. A000040, A070939, A208241, A338884.

from sympy import isprime
def search(n):
    k = 1
    while 1:
        i = k*n + 1
        while i < k*n + k:
            if isprime(i) == 1: return i
            i += 2
        k = 2*k
a_rec = 0
n = 1
while 1:
    m = search(n)
    a = m.bit_length() - n.bit_length()
    if a > a_rec:
        print(n)
        a_rec = a
    n += 1

cp's OEIS Frontend

A004676 Primes written in base 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A055011 a(n+1) = next smallest prime beginning with a(n) when written in binary, starting with 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

Haskell

Maple

Formula

A174332 Least prime q of which prime(n) is a proper binary substring.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A208238 Smallest prime greater than n, containing it in binary representation.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A338884 The smallest number of bits which need to be appended to the binary representation of n to reach a prime greater than n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python

Formula

A339134 Indices in A338884 where records occur.

Views

Author

Keywords

Comments

Crossrefs

Programs

Python