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,4

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.

Links

Table of n, a(n) for n=1..87.

Formula

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

Prog

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

Crossrefs

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

Cf. A108234 (zero or more bits).

Sequence in context: A076845 A161906 A319135 * A204901 A016014 A067760

Adjacent sequences: A338881 A338882 A338883 * A338885 A338886 A338887

Keyword

nonn

Author

Ya-Ping Lu, Nov 13 2020

Status

approved