

A202479


The number of equivalence classes of the set {1,2,...,n} under the equivalence relation x ~ y iff lcm(x,n) = lcm(y,n).


2



1, 1, 2, 2, 4, 3, 6, 4, 6, 6, 10, 6, 12, 9, 9, 8, 16, 9, 18, 10, 14, 15, 22, 10, 20, 18, 18, 15, 28, 15, 30, 16, 23, 24, 25, 16, 36, 27, 28, 19, 40, 21, 42, 25, 26, 33, 46, 20, 42, 30, 37, 30, 52, 27, 42, 28, 42, 42, 58, 23, 60, 45, 39, 32, 50, 35, 66, 40, 51
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


LINKS

Amiram Eldar, Table of n, a(n) for n = 1..10000
Hamid Kulosman, The number of equivalence classes of the relation lcm(x,n) = lcm(y,n) on the set {1,2,...,n}, Rad. Mat. 7 (1991), pp. 143150.


FORMULA

h(n) = symb floor(prod_{i=1..k} (p_i^a_i  p_i^(a_i1) + 1/p_i), where n=p_1^a_1 * ... * p_k^a_k and the symbol symb symbolizes that first the multiplication of all factors is performed and then floor is assigned to each of the 3^k terms, keeping the sign of the term outside (this symbol is occurring in W. Sierpinski's 1950 monograph Number Theory).


MATHEMATICA

a[n_] := Length @ Union @ Table[LCM[n, i], {i, 1, n}]; Array[a, 100] (* Amiram Eldar, Apr 23 2020 *)


PROG

(PARI) a(n)=#Set(vector(n, i, lcm(n, i))) \\ Charles R Greathouse IV, Dec 19 2011


CROSSREFS

Sequence in context: A126080 A302043 A060681 * A161660 A060766 A321015
Adjacent sequences: A202476 A202477 A202478 * A202480 A202481 A202482


KEYWORD

nonn


AUTHOR

Hamid Kulosman, Dec 19 2011


STATUS

approved



