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,2

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

References

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

Links

Table of n, a(n) for n=0..70.

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

Example

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

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

Prog

(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)])
(PARI) a(n) = sum(k = 0, n, gcd(k, n) == 1); \\ Amiram Eldar, Jun 08 2025

Crossrefs

Cf. A000010, A217831, A109004, A372728.

Sequence in context: A339219 A308302 A225530 * A020475 A156995 A131183

Adjacent sequences: A384707 A384708 A384709 * A384711 A384712 A384713

Keyword

nonn

Author

Peter Luschny, Jun 07 2025

Status

approved