A345182 - OEIS

A345182

a(1) = 1, a(2) = 0; a(n) = Sum_{d|n, d < n} a(d).

1, 0, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 2, 3, 4, 1, 6, 1, 5, 3, 2, 1, 12, 2, 2, 4, 5, 1, 10, 1, 8, 3, 2, 3, 18, 1, 2, 3, 12, 1, 10, 1, 5, 8, 2, 1, 28, 2, 6, 3, 5, 1, 16, 3, 12, 3, 2, 1, 31, 1, 2, 8, 16, 3, 10, 1, 5, 3, 10, 1, 50, 1, 2, 8, 5, 3, 10, 1, 28, 8, 2, 1, 31, 3, 2, 3, 12, 1, 36

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

From Antti Karttunen, Nov 25 2024: (Start)

a(n) is the number of strict chains of divisors from n to 1 that do not end with 2/1. For example, the a(n) such chains for n = 1, 2, 4, 6, 8, 12, 30 are:

1 (none) 4/1 6/1 8/1 12/1 30/1

6/3/1 8/4/1 12/3/1 30/3/1

12/4/1 30/5/1

12/6/1 30/6/1

12/6/3/1 30/10/1

30/15/1

30/6/3/1

30/10/5/1

30/15/3/1

30/15/5/1

leaving 1, 0, 1, 2, 2, 5, 10 chains out of the 1, 1, 2, 3, 4, 8, 13 chains depicted in the illustration of A074206.

Equally, a(n) is the number of strict chains of divisors from n to 1 where n is not followed by n/2 as the second divisor in the chain, which explains nicely the formula a(n) = A074206(n) - A074206(n/2) when n is even.

(End)

LINKS

Antti Karttunen, Table of n, a(n) for n = 1..20000

FORMULA

G.f. A(x) satisfies: A(x) = x - x^2 + A(x^2) + A(x^3) + A(x^4) + ...

a(n) = A074206(n) if n is odd, otherwise a(n) = A074206(n) - A074206(n/2).

MATHEMATICA

a[1] = 1; a[2] = 0; a[n_] := a[n] = Sum[If[d < n, a[d], 0], {d, Divisors[n]}]; Table[a[n], {n, 1, 90}]

nmax = 90; A[_] = 0; Do[A[x_] = x - x^2 + Sum[A[x^k], {k, 2, nmax}] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] // Rest

PROG

(PARI)

memoA345182 = Map();

A345182(n) = if(n<=2, n%2, my(v); if(mapisdefined(memoA345182, n, &v), v, v = sumdiv(n, d, if(d<n, A345182(d), 0)); mapput(memoA345182, n, v); (v))); \\ Antti Karttunen, Nov 22 2024

(PARI)

up_to = 20000;

A345182list(up_to_n) = { my(v=vector(up_to_n)); v[1] = 1; v[2] = 0; for(n=3, up_to_n, v[n] = sumdiv(n, d, (d<n)*v[d])); (v); };

v345182 = A345182list(up_to);

A345182(n) = v345182[n]; \\ Antti Karttunen, Nov 25 2024

(Python)

from functools import lru_cache

from sympy import divisors

@lru_cache(maxsize=None)

def A345182(n): return sum(A345182(d) for d in divisors(n, generator=True, proper=True)) if n>2 else 2-n # Chai Wah Wu, Mar 28 2026

CROSSREFS

Cf. A022825 (partial sums), A074206, A167865, A320224, A345138, A345141, A378218 (Dirichlet inverse), A378223 (inverse Möbius transform).