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

%I #17 Dec 25 2013 02:22:14

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

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

%U 13,64,13,27,13,41,6,6,12,41,11,21,5,11,5,5,11

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

%C 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 c-GCD(k,m) is called maximal common c-divisor of k,m. For example, c-GCD(7,11)=3.

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

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

%H Peter J. C. Moses, <a href="/A233412/b233412.txt">Table of n, a(n) for n = 0..4999</a>

%F a(2^n)=2^n.

%e Let n=12=(1)(100). It is clear that odd numbers end in (1) and are not prime to 12.

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

%Y Cf. A000010, A124771.

%K nonn,base

%O 0,3

%A _Vladimir Shevelev_, Dec 09 2013

%E More terms from _Peter J. C. Moses_, Dec 09 2013