A233412 c-analog of Euler phi-function: a(n) is number of nonnegative integers not exceeding n and c-prime to n.

1, 1, 2, 2, 4, 2, 2, 3, 8, 3, 7, 3, 4, 3, 3, 5, 16, 5, 8, 5, 8, 4, 4, 4, 7, 5, 4, 4, 5, 4, 4, 8, 32, 8, 15, 8, 28, 4, 4, 7, 17, 4, 21, 6, 4, 6, 6, 6, 12, 10, 4, 9, 4, 6, 6, 6, 10, 9, 6, 6, 9, 6, 6, 13, 64, 13, 27, 13, 41, 6, 6, 12, 41, 11, 21, 5, 11, 5, 5, 11

Offset: 0

Author

Vladimir Shevelev, Dec 09 2013

Keywords

• nonn
• base

Comments

Every number in binary is a concatenation of parts of the form 10...0 with k>=0 zeros. For example, 5=(10)(1), 11=(10)(1)(1), 7=(1)(1)(1). We call d>0 is a c-divisor of m, if d consists of some consecutive parts of m which are following in natural order (from the left to the right) in m (cf. comment in A124771). Note that, to d=0 corresponds an empty set of parts. So it is natural to consider 0 as a c-divisor of every m. For example, 3=(1)(1) is a c-divisor of 23, since (1)(1) includes in 23=(10)(1)(1)(1) in a natural order. Analogously, 1,2,5,7,11,23 are c-divisors of 23. But 6=(1)(10) is not a c-divisor of 23.

c-GCD(k,m) is called maximal common c-divisor of k,m. For example, c-GCD(7,11)=3.

Two numbers k,m are called mutually c-prime one to another, if c-GCD(k,m)=0.

In particular, 0 is c-prime to 0 (cf. 1 is prime to 1). Therefore, a(0)=1. Besides, every positive integer is c-prime to 0.

Examples

			Let n=12=(1)(100). It is clear that odd numbers end in (1) and are not prime to 12.
Besides, 6=(1)(10) also contains part (1) and 4=(100) is c-divisor of 12. Other even <=10 {0,2,8,10} are prime to 12. Thus a(12)=4.
		

Links

• Peter J. C. Moses, Table of n, a(n) for n = 0..4999

Crossrefs

Cf. A000010, A124771.

Formula

a(2^n)=2^n.

Extensions

More terms from Peter J. C. Moses, Dec 09 2013