cp's OEIS Frontend

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

%I A051613 #31 Oct 02 2017 10:54:59
%S A051613 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 A051613 17,21,23,23,25,29,31,31,31,37,40,42,44,48,49,54,55,64,67,68,70,77,84,
%U A051613 90,92,99,102,108,115,127,133,135,138,150,165,171,183,186,198,201,220
%N A051613 a(n) = partitions of n into powers of distinct primes (1 not considered a power).
%H A051613 T. D. Noe, <a href="/A051613/b051613.txt">Table of n, a(n) for n = 0..1000</a>
%H A051613 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 A051613 a(n) = number of m such that A008475(m) = n.
%F A051613 G.f.: Product_{p prime} (1 + Sum_{k >= 1} x^(p^k)).
%e A051613 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 A051613 b:= proc(n,i) option remember; local p;
%p A051613       p:= `if`(i<1, 1, ithprime(i));
%p A051613       `if`(n=0, 1, `if`(i<1, 0, b(n,i-1)+
%p A051613       add(b(n-p^j, i-1), j=1..ilog[p](n))))
%p A051613     end:
%p A051613 a:= n-> b(n, numtheory[pi](n)):
%p A051613 seq(a(n), n=0..100);  # _Alois P. Heinz_, Feb 15 2013
%t A051613 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 A051613 (Haskell)
%o A051613 import Data.MemoCombinators (memo3, integral)
%o A051613 a051613' = p 1 2 where
%o A051613    p x _ 0 = 1
%o A051613    p x k m | m < qq       = 0
%o A051613            | mod x q == 0 = p x (k + 1) m
%o A051613            | otherwise    = p (q * x) (k + 1) (m - qq) + p x (k + 1) m
%o A051613            where q = a025473 k; qq = a000961 k
%o A051613 -- _Reinhard Zumkeller_, Nov 23 2015
%o A051613 (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 A051613 Cf. A023894, A009490, A054685, A008475, A106245, A000961, A025473, A106244.
%K A051613 nonn,nice,easy
%O A051613 0,6
%A A051613 _Vladeta Jovovic_
%E A051613 Better description from _David W. Wilson_, Apr 19 2000