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).

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

Offset: 1

Author

Hamid Kulosman, Dec 19 2011

Keywords

• nonn

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. 143-150.

Programs

Mathematica

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

PARI

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

Formula

h(n) = symb floor(prod_{i=1..k} (p_i^a_i - p_i^(a_i-1) + 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).