A246369 a(1)=0, a(p_n) = a(n), a(c_n) = 1 + a(n), where p_n = n-th prime = A000040(n), c_n = n-th composite number = A002808(n); Also one less than the binary weight of terms of A135141.

0, 0, 0, 1, 0, 1, 1, 1, 2, 1, 0, 2, 1, 2, 2, 3, 1, 2, 1, 1, 3, 2, 2, 3, 3, 4, 2, 3, 1, 2, 0, 2, 4, 3, 3, 4, 2, 4, 5, 3, 1, 4, 2, 2, 3, 1, 2, 3, 5, 4, 4, 5, 3, 3, 5, 6, 4, 2, 1, 5, 2, 3, 3, 4, 2, 3, 1, 4, 6, 5, 1, 5, 3, 6, 4, 4, 6, 7, 2, 5, 3, 2, 2, 6, 3, 4, 4, 5, 3, 3, 4, 2, 5, 7, 6, 2, 3, 6, 4, 7, 4, 5, 2, 5, 7, 8, 3, 3, 1, 6, 4, 3, 2, 3, 7, 4, 5, 5, 6, 4

Offset: 1

Author

Antti Karttunen, Aug 27 2014

Keywords

• nonn

Comments

Consider the following algorithm:

Start:

If n is 1, we have finished,

Otherwise:

If n is a prime, replace it with its index among the primes, n <- A000720(n), and go back to the start.

Otherwise, if n is a composite, replace it with its index among the composites, n <- A065855(n), and go back to the start.

At some point, the process is guaranteed to reach the number 1 at which point we stop.

a(n) tells how many times a composite number was encountered in the process, before 1 was reached. This count includes also +1 for the cases where the initial n was composite at the beginning.

Examples

			Consider n=30. It is the 19th composite number in A002808: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, ...
Thus we consider next n=19, which is the 8th prime in A000040: 2, 3, 5, 7, 11, 13, 17, 19, ...
So we proceed with n=8, which is the 3rd composite number, and then with n=3, which is the 2nd prime, and then with n=2 which is the 1st prime, and we have finished.
All in all, it took us 5 steps (A246348(30) = 6 = 5+1) to reach 1, and on the journey, we encountered two composites, 30 and 8, thus a(30) = 2.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..32998

Crossrefs

Cf. A000040, A002808, A000120, A000720, A065855, A135141, A246348, A246370, A246377.

Formula

a(1) = 1, and for n >= 1, if A010051(n) = 1 [that is, when n is prime], a(n) = a(A000720(n)), otherwise a(n) = 1 + a(A065855(n)). [A000720(n) and A065855(n) tell the number of primes, and respectively, composites <= n].

a(n) = A000120(A135141(n)) - 1. [a(n) is also one less than the Hamming weight (number of 1-bits) of the n-th term of A135141].

a(n) = A080791(A246377(n)). [Respectively, the number of 0-bits for 0/1-swapped version of that sequence].

a(n) = A246348(n) - A246370(n) - 1.