A384628 a(n) = Sum_{k = 1..n} gcd(n, floor(n / k)).

1, 3, 5, 8, 9, 14, 13, 20, 19, 25, 21, 35, 25, 37, 37, 44, 33, 56, 37, 60, 51, 58, 45, 84, 53, 71, 69, 85, 57, 103, 61, 99, 83, 93, 83, 130, 73, 104, 101, 136, 81, 146, 85, 140, 129, 124, 93, 188, 103, 155, 131, 163, 105, 191, 127, 185, 145, 159, 117, 251, 121

Offset: 1

Author

Ctibor O. Zizka, Jun 05 2025

Keywords

• nonn

Comments

a(p) = A018804(p) for p prime (A000040).

Empirical observation: A005408(n) <= a(n) < (2 + sqrt(2)/10)*A000203(n).

Examples

			n = 3: a(3) = Sum_{k = 1..3} gcd(3, floor(3 / k)) = 3 + 1 + 1 = 5.
n = 4: a(4) = Sum_{k = 1..4} gcd(4, floor(4 / k)) = 4 + 2 + 1 + 1 = 8.
		

Crossrefs

Cf. A000040, A000203, A005408, A018804.

Programs

Mathematica

a[n_] := Sum[GCD[n, Floor[n/k]], {k, 1, n}]; Array[a, 100] (* Amiram Eldar, Jun 05 2025 *)

PARI

a(n) = sum(k=1, n, gcd(n, n\k)); \\ Michel Marcus, Jun 05 2025

Python

from math import gcd
def A384628(n):
    c, j = (n<<1)+1, 2
    k1 = n//j
    while k1>1:
        j2 = n//k1+1
        c += (j2-j)*gcd(n,k1)
        j, k1 = j2, n//j2
    return c-j # Chai Wah Wu, Jun 17 2025

Formula

For p prime: a(p) = 2*p - 1.