login
a(n) = partitions of n into powers of distinct primes (1 not considered a power).
12

%I #31 Oct 02 2017 10:54:59

%S 1,0,1,1,1,2,0,3,2,3,2,4,3,4,4,4,8,4,8,6,9,8,10,10,13,12,13,16,16,19,

%T 17,21,23,23,25,29,31,31,31,37,40,42,44,48,49,54,55,64,67,68,70,77,84,

%U 90,92,99,102,108,115,127,133,135,138,150,165,171,183,186,198,201,220

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

%H T. D. Noe, <a href="/A051613/b051613.txt">Table of n, a(n) for n = 0..1000</a>

%H J. Bamberg, G. Cairns and D. Kilminster, <a href="http://www.jstor.org/stable/3647934">The crystallographic restriction, permutations and Goldbach's conjecture</a>, Amer. Math. Monthly, 110 (March 2003), 202-209.

%F a(n) = number of m such that A008475(m) = n.

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

%e a(16) = 8 because we can write 16 = 2^4 = 3+13 = 5+11 = 3^2+7 = 2+3+11 = 2+3^2+5 = 2^3+3+5 = 2^2+5+7.

%p b:= proc(n,i) option remember; local p;

%p p:= `if`(i<1, 1, ithprime(i));

%p `if`(n=0, 1, `if`(i<1, 0, b(n,i-1)+

%p add(b(n-p^j, i-1), j=1..ilog[p](n))))

%p end:

%p a:= n-> b(n, numtheory[pi](n)):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Feb 15 2013

%t max = 70; f[x_] := Product[ 1 + Sum[x^(Prime[n]^k), {k, 1, If[n > 4, 1, 6]}], {n, 1, PrimePi[max]}]; CoefficientList[ Series[f[x], {x, 0, max}] , x](* _Jean-François Alcover_, Sep 12 2012 *)

%o (Haskell)

%o import Data.MemoCombinators (memo3, integral)

%o a051613' = p 1 2 where

%o p x _ 0 = 1

%o p x k m | m < qq = 0

%o | mod x q == 0 = p x (k + 1) m

%o | otherwise = p (q * x) (k + 1) (m - qq) + p x (k + 1) m

%o where q = a025473 k; qq = a000961 k

%o -- _Reinhard Zumkeller_, Nov 23 2015

%o (PARI) first(n)=my(x='x,pr=O(x^(n+1))+1); forprime(p=sqrtint(n)+1,n, pr*=1+x^p); forprime(p=2,sqrtint(n), pr*=1+sum(e=1,logint(n,2), x^p^e)); Vec(pr) \\ _Charles R Greathouse IV_, Jun 25 2017

%Y Cf. A023894, A009490, A054685, A008475, A106245, A000961, A025473, A106244.

%K nonn,nice,easy

%O 0,6

%A _Vladeta Jovovic_

%E Better description from _David W. Wilson_, Apr 19 2000