A332468 a(n) = Sum_{k=1..n} mu(k) * floor(n/k)^n.

1, 3, 25, 239, 3091, 45863, 821227, 16711423, 387138661, 9990174303, 285262663291, 8913906888703, 302861978789371, 11111328334033327, 437889112287422401, 18446462446101903615, 827238009323454485641, 39346257879101283645743, 1978418304199236175597105

Offset: 1

Author

Ilya Gutkovskiy, Feb 13 2020

Keywords

• nonn

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..386

Crossrefs

Main diagonal of A344527.

Cf. A008683, A018805, A071778, A082540, A082544, A332469, A343978.

Programs

Magma

[&+[MoebiusMu(k)*Floor(n/k)^n:k in [1..n]]:n in [1..20]]; // Marius A. Burtea, Feb 13 2020

Mathematica

Table[Sum[MoebiusMu[k] Floor[n/k]^n, {k, 1, n}], {n, 1, 19}]
b[n_, k_] := b[n, k] = n^k - Sum[b[Floor[n/j], k], {j, 2, n}]; a[n_] := b[n, n]; Table[a[n], {n, 1, 19}]

PARI

a(n)={sum(k=1, n, moebius(k) * floor(n/k)^n)} \\ Andrew Howroyd, Feb 13 2020

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A344527_T(n,k):
    if n == 0:
        return 0
    c, j, k1 = 1, 2, n//2
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A344527_T(k1,k)
        j, k1 = j2, n//j2
    return n*(n**(k-1)-1)-c+j
def A332468(n): return A344527_T(n,n) # Chai Wah Wu, Nov 02 2023

Formula

a(n) ~ n^n. - Vaclav Kotesovec, May 28 2021