cp's OEIS Frontend

A384710 a(n) = Sum_{k=0..n} [gcd(k, n) = 1], where [.] are the Iverson brackets.

%I A384710 #15 Jun 09 2025 14:43:27
%S A384710 0,2,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10,22,8,20,12,18,12,
%T A384710 28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,42,20,32,
%U A384710 24,52,18,40,24,36,28,58,16,60,30,36,32,48,20,66,32,44,24
%N A384710 a(n) = Sum_{k=0..n} [gcd(k, n) = 1], where [.] are the Iverson brackets.
%C A384710 For n >= 2 identical to A000010, which is the main entry for this sequence. However, the fact that the function gcd as well as the Euclidean algorithm are defined for pairs (n >= 0, k >= 0) makes the choice of offset 0 appear more natural than that in A000010.
%C A384710 Graham, Knuth and Patashnik write: "We can make many formulas clearer by adopting a new notation now! Let us agree to write 'm ⟂ n', and to say "m is prime to n," if m and n are relatively prime." Here '⟂' is the perpendicular symbol (\perp in LaTeX, U+27C2 in Unicode), a binary relation symbol not to be confused with the "up tack" symbol (\bot in LaTeX, U+22A5 in Unicode).
%D A384710 R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.5.
%F A384710 The row sums of Euclid's triangle A217831.
%F A384710 The row sums of absolute terms of Kronecker's triangle A372728.
%F A384710 a(n) = card({A109004(n, k) = 1 : 0 <= k <= n}).
%e A384710 [gcd(0,0)] = [0] => a(0) = 0.
%e A384710 [gcd(0,1), gcd(1,1)] = [1, 1] => a(1) = 2.
%e A384710 [gcd(0,2), gcd(1,2), gcd(2,2)] = [2, 1, 2] => a(2) = 1.
%p A384710 isPrimeTo := (k, n) -> ifelse(igcd(k, n) = 1, 1, 0):
%p A384710 a := n -> add(isPrimeTo(k, n), k = 0..n): seq(a(n), n = 0..70);
%t A384710 Table[Sum[Boole[CoprimeQ[k, n]], {k, 0, n}], {n, 0, 70}] (* _Michael De Vlieger_, Jun 07 2025 *)
%o A384710 (Python)
%o A384710 from math import gcd
%o A384710 def a(n: int) -> int: return sum(int(1 == gcd(n, k)) for k in range(n + 1))
%o A384710 print([a(n) for n in range(71)])
%o A384710 (PARI) a(n) = sum(k = 0, n, gcd(k, n) == 1); \\ _Amiram Eldar_, Jun 08 2025
%Y A384710 Cf. A000010, A217831, A109004, A372728.
%K A384710 nonn
%O A384710 0,2
%A A384710 _Peter Luschny_, Jun 07 2025