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

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

Author

Ya-Ping Lu, Nov 13 2020

Keywords

• nonn

Comments

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.

Crossrefs

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

Cf. A108234 (zero or more bits).

Programs

Python

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)

Formula

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