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

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, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44, 24

Offset: 0

Author

Peter Luschny, Jun 07 2025

Keywords

• nonn

Comments

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.

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

Examples

			[gcd(0,0)] = [0] => a(0) = 0.
[gcd(0,1), gcd(1,1)] = [1, 1] => a(1) = 2.
[gcd(0,2), gcd(1,2), gcd(2,2)] = [2, 1, 2] => a(2) = 1.
		

References

• R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 2nd ed., 1994, ch. 4.5.

Crossrefs

Cf. A000010, A217831, A109004, A372728.

Programs

Maple

isPrimeTo := (k, n) -> ifelse(igcd(k, n) = 1, 1, 0):
a := n -> add(isPrimeTo(k, n), k = 0..n): seq(a(n), n = 0..70);

Mathematica

Table[Sum[Boole[CoprimeQ[k, n]], {k, 0, n}], {n, 0, 70}] (* Michael De Vlieger, Jun 07 2025 *)

PARI

a(n) = sum(k = 0, n, gcd(k, n) == 1); \\ Amiram Eldar, Jun 08 2025

Python

from math import gcd
def a(n: int) -> int: return sum(int(1 == gcd(n, k)) for k in range(n + 1))
print([a(n) for n in range(71)])

Formula

The row sums of Euclid's triangle A217831.

The row sums of absolute terms of Kronecker's triangle A372728.

a(n) = card({A109004(n, k) = 1 : 0 <= k <= n}).