|
| |
|
|
A233412
|
|
c-analog of Euler phi-function: a(n) is number of nonnegative integers not exceeding n and c-prime 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 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.
|
|
|
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 c-divisor 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
|
| |
|
|
