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

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, 17, 21, 23, 23, 25, 29, 31, 31, 31, 37, 40, 42, 44, 48, 49, 54, 55, 64, 67, 68, 70, 77, 84, 90, 92, 99, 102, 108, 115, 127, 133, 135, 138, 150, 165, 171, 183, 186, 198, 201, 220

Offset: 0

Author

Vladeta Jovovic

Keywords

• nonn
• nice
• easy

Examples

			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.
		

Links

• T. D. Noe, Table of n, a(n) for n = 0..1000
• J. Bamberg, G. Cairns and D. Kilminster, The crystallographic restriction, permutations and Goldbach's conjecture, Amer. Math. Monthly, 110 (March 2003), 202-209.

Crossrefs

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

Programs

Haskell

import Data.MemoCombinators (memo3, integral)
a051613' = p 1 2 where
   p x _ 0 = 1
   p x k m | m < qq       = 0
           | mod x q == 0 = p x (k + 1) m
           | otherwise    = p (q * x) (k + 1) (m - qq) + p x (k + 1) m
           where q = a025473 k; qq = a000961 k
-- Reinhard Zumkeller, Nov 23 2015

Maple

b:= proc(n,i) option remember; local p;
      p:= `if`(i<1, 1, ithprime(i));
      `if`(n=0, 1, `if`(i<1, 0, b(n,i-1)+
      add(b(n-p^j, i-1), j=1..ilog[p](n))))
    end:
a:= n-> b(n, numtheory[pi](n)):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 15 2013

Mathematica

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

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

Formula

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

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

Extensions

Better description from David W. Wilson, Apr 19 2000