A022825 a(n) = a([ n/2 ]) + a([ n/3 ]) + . . . + a([ n/n ]) for n > 1, a(1) = 1.

1, 1, 2, 3, 4, 6, 7, 9, 11, 13, 14, 19, 20, 22, 25, 29, 30, 36, 37, 42, 45, 47, 48, 60, 62, 64, 68, 73, 74, 84, 85, 93, 96, 98, 101, 119, 120, 122, 125, 137, 138, 148, 149, 154, 162, 164, 165, 193, 195, 201, 204, 209, 210, 226, 229, 241, 244, 246, 247, 278, 279

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Links

• Ivan Neretin, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A025523, A078346, A345182.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 1,
      add(a(iquo(n,j)), j=2..n))
    end:
seq(a(n), n=1..63);  # Alois P. Heinz, Mar 31 2021

Mathematica

Fold[Append[#1, Total[#1[[Quotient[#2, Range[2, #2]]]]]] &, {1}, Range[2, 60]] (* Ivan Neretin, Aug 24 2016 *)

Python

from functools import lru_cache
@lru_cache(maxsize=None)
def A022825(n):
    if n <= 1:
        return n
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A022825(k1)
        j, k1 = j2, n//j2
    return c+n+1-j # Chai Wah Wu, Mar 31 2021

Formula

G.f. A(x) satisfies: A(x) = x + (1/(1 - x)) * Sum_{k>=2} (1 - x^k) * A(x^k). - Ilya Gutkovskiy, Feb 21 2022

Extensions

Offset corrected by Alois P. Heinz, Mar 31 2021