login
Number of partitions of n into distinct prime powers (1 not considered a power).
23

%I #26 Nov 02 2023 12:30:04

%S 1,0,1,1,1,2,1,3,2,4,3,5,5,6,7,7,10,9,12,12,15,15,18,19,22,24,26,30,

%T 32,36,39,43,48,51,57,61,68,73,79,87,93,103,108,121,127,140,148,162,

%U 173,187,200,215,232,247,266,283,306,324,348,371,397,423,450,480,512,543,579,614

%N Number of partitions of n into distinct prime powers (1 not considered a power).

%H Reinhard Zumkeller, <a href="/A054685/b054685.txt">Table of n, a(n) for n = 0..10000</a> (first 1000 terms from T. D. Noe)

%F G.f.: Product_{p prime} Product_{k >= 1} (1 + x^(p^k)).

%t CoefficientList[Series[Product[Product[1 +x^(Prime[n]^k), {k, 1, 9}], {n, 1, 25}], {x, 0, 100}], x] (* _G. C. Greubel_, May 09 2019 *)

%o (Haskell)

%o import Data.MemoCombinators (memo2, integral)

%o a054685 n = a054685_list !! n

%o a054685_list = map (p' 2) [0..] where

%o p' = memo2 integral integral p

%o p _ 0 = 1

%o p k m = if m < pp then 0 else p' (k + 1) (m - pp) + p' (k + 1) m

%o where pp = a000961 k

%o -- _Reinhard Zumkeller_, Nov 23 2015

%Y Cf. A051613.

%Y Cf. A106244.

%Y Cf. A000961.

%K nonn

%O 0,6

%A _David W. Wilson_, Apr 19 2000