%I #22 Nov 23 2020 01:47:23

%S 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,

%T 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,

%U 1,2,3,3,2,1,1,2,2,1,2,3,1,2,1,2,3,1,2

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

%C 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.

%F a(n) = bitlength(A208241(n)) - bitlength(n), where bitlength = A070939. - _Kevin Ryde_, Nov 13 2020

%o (Python)

%o from sympy import isprime

%o for n in range(1,101):

%o a = 0

%o k = i = 1

%o while isprime(i) == 0:

%o a += 1

%o k = 2*k

%o for i in range(k*n + 1, k*n + k):

%o if isprime(i) == 1: break

%o print(a)

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

%Y Cf. A108234 (zero or more bits).

%K nonn

%O 1,4

%A _Ya-Ping Lu_, Nov 13 2020