A159929 INVERT transform of phi(n), A000010.

1, 1, 2, 5, 11, 26, 57, 131, 296, 669, 1515, 3430, 7765, 17577, 39790, 90069, 203897, 461562, 1044847, 2365239, 5354224, 12120455, 27437267, 62110208, 140599921, 318278385, 720492104, 1630990029, 3692099407, 8357867190, 18919843773, 42829166807, 96953101328, 219474357191, 496827773575

Offset

0,3

Comments

Number of compositions of n into parts where there are phi(k) sorts of part k. - Joerg Arndt, Sep 30 2012

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Formula

INVERT transform of A000010.

G.f.: 1/( 1 - Sum_{k>=1} phi(k) * x^k ) where phi = A000010. Joerg Arndt, Sep 30 2012

a(n) ~ c * d^n, where d = 2.26371672715382105671101924573765243871241560288177676216035633730282369149... is the root of the equation Sum_{k>=1} phi(k)/d^k = 1 and c = 0.42880036544961338799475947921442516792321060146527623589359809145075482942... - Vaclav Kotesovec, Aug 18 2021

Example

a(6) = 57 = (1, 1, 2, 2, 4, 2) dot (26, 11, 5, 2, 1, 1) = (26 + 11 + 10 + 4 + 4 + 2).

Maple

a:= proc(n) option remember; `if`(n=0, 1,
      add(a(n-i)*numtheory[phi](i), i=1..n))
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 22 2017

Mathematica

a[n_] := a[n] = If[n == 0, 1, Sum[a[n-i] EulerPhi[i], {i, 1, n}]];
a /@ Range[0, 35] (* Jean-François Alcover, Oct 31 2020, after Maple *)

Prog

(PARI)
N=66;  x='x+O('x^N);
Vec( 1/( 1 - sum(k=1, N, eulerphi(k)*x^k ) ) - 1 )
/* Joerg Arndt, Sep 30 2012 */

Crossrefs

Cf. A000010.

Row sums of A340995.

Sequence in context: A371662 A005469 A218575 * A362740 A291233 A026787

Adjacent sequences: A159926 A159927 A159928 * A159930 A159931 A159932

Keyword

nonn

Author

Gary W. Adamson, Apr 26 2009

Extensions

a(0)=1 prepended by Alois P. Heinz, Sep 22 2017

Status

approved