A108700 Number of compositions of n into odd and relatively prime parts.

1, 1, 1, 3, 4, 7, 12, 21, 32, 54, 88, 141, 232, 376, 604, 987, 1596, 2576, 4180, 6762, 10932, 17710, 28656, 46347, 75020, 121392, 196384, 317808, 514228, 831978, 1346268, 2178309, 3524488, 5702886, 9227448, 14930208, 24157816, 39088168

Offset: 1

Author

Vladeta Jovovic, Jun 19 2005

Keywords

• easy
• nonn

Links

• Amiram Eldar, Table of n, a(n) for n = 1..4786

Crossrefs

Cf. A000740, A007436, A000045, A008683.

Programs

Maple

with(numtheory): seq(-add(mobius(2*d)*combinat[fibonacci](n/d), d in divisors(n)), n=1..80); # Ridouane Oudra, Apr 12 2025

Mathematica

a[n_] := a[n] = Module[{d = Divisors[n]}, m = Plus @@ (MoebiusMu /@ (n/d)*Fibonacci /@ d); If[ OddQ[n], m, a[n/2] + m]]; Table[ a[n], {n, 38}] (* Robert G. Wilson v, Jun 21 2005 *)

Formula

a(n) = A007436(n) if n is odd, else a(n) = a(n/2) + A007436(n).

a(n) = - Sum_{d|n} mu(2*d)*Fibonacci(n/d). - Ridouane Oudra, Apr 12 2025

Extensions

More terms from Robert G. Wilson v, Jun 21 2005