A377483 Smallest index k such that prime(k) in base-2 contains n in base-2 as a contiguous substring.

1, 1, 2, 7, 3, 6, 4, 7, 8, 13, 5, 24, 6, 10, 11, 19, 7, 12, 8, 13, 14, 24, 9, 25, 24, 16, 17, 30, 10, 18, 11, 32, 19, 33, 20, 21, 12, 63, 22, 38, 13, 68, 14, 24, 29, 70, 15, 25, 30, 26, 27, 47, 16, 29, 48, 30, 50, 51, 17, 53, 18, 54, 31, 55, 32, 77, 19, 33, 34, 60, 20, 79

Offset: 1

Author

Charles Marsden, Oct 29 2024

Keywords

• nonn
• base

Comments

The intersections between this sequence and similar sequences in base-B occur at values of n that are the sequence of prime numbers, and values of a(n) that are the sequence of positive integers.

Examples

			For n=1 -> 1 in base-2. The first prime containing 1 in its base-2 form is prime(1)=2 -> 10. Therefore, a(1)=1.
For n=3 -> 11 in base-2. The first prime containing 11 in its base-2 form is prime(2)=3 -> 11. Therefore, a(3)=2.
For n=5 -> 101 in base-2. The first prime containing 101 in its base-2 form is prime(3)=5 -> 101. Therefore, a(5)=3.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000
• Charles Marsden, Python program

Crossrefs

Cf. A000040, A004676, A062584, A082058.

Programs

Mathematica

s={}; Do[k=0;Until[SequenceCount[IntegerDigits[Prime[k],2],IntegerDigits[n,2]]>0,k++]; AppendTo[s,k],{n,72}];s (* James C. McMahon, Nov 20 2024 *)

PARI

a(n) = { my (w = 2^#binary(n), k = 0, r); forprime (p = 2, oo, k++; r = p; while (r >= n, if (r % w == n, return (k), r \= 2;););); } \\ Rémy Sigrist, Nov 20 2024

Python

# See links.

Python

from sympy import nextprime, primepi
def A377483(n):
    p, k, a = nextprime(n-1), primepi(n-1)+1, bin(n)[2:]
    while True:
        if a in bin(p)[2:]:
            return k
        p = nextprime(p)
        k += 1 # Chai Wah Wu, Nov 20 2024