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

Author

Gary W. Adamson, Apr 26 2009

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A000010.

Row sums of A340995.

Programs

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 *)

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 */

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

Extensions

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