A147814 Number of bits in Elias omega-coded prime numbers.

4, 4, 7, 7, 8, 8, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17

Offset: 1

Author

Reikku Kulon, Nov 13 2008

Keywords

• base
• easy
• nonn
• uned

Comments

a(n) increases very slowly, gradually diverging from 3 + floor(log_2(n)).

Links

• Indranil Ghosh, Table of n, a(n) for n = 1..10000
• Wikipedia, Elias omega coding

Crossrefs

Cf. A000040, A147764.

Formula

a(n) = 2 + Sum_{i=0..k} d(i), where

d(0) = bits(p_n)

d(x) = bits(d(x-1)-1)

...

d(k) = 2,

and bits(p_n) = 1 + floor(log_2(prime(n))) is the number of bits in the binary representation of the n-th prime.