

A233412


canalog of Euler phifunction: a(n) is number of nonnegative integers not exceeding n and cprime to n.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


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 cdivisor 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 cdivisor of every m. For example, 3=(1)(1) is a cdivisor of 23, since (1)(1) includes in 23=(10)(1)(1)(1) in a natural order. Analogously, 1,2,5,7,11,23 are cdivisors of 23. But 6=(1)(10) is not a cdivisor of 23.
cGCD(k,m) is called maximal common cdivisor of k,m. For example, cGCD(7,11)=3.
Two numbers k,m are called mutually cprime one to another, if cGCD(k,m)=0.
In particular, 0 is cprime to 0 (cf. 1 is prime to 1). Therefore, a(0)=1. Besides, every positive integer is cprime to 0.


LINKS



FORMULA

a(2^n)=2^n.


EXAMPLE

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 cdivisor of 12. Other even <=10 {0,2,8,10} are prime to 12. Thus a(12)=4.


CROSSREFS



KEYWORD

nonn,base


AUTHOR



EXTENSIONS



STATUS

approved



