A208614 Number of partitions of n into distinct primes where all of the prime factors of n are represented in the partition.

1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 3, 1, 4, 2, 1, 1, 1, 3, 2, 1, 1, 3, 1, 1, 2, 3, 1, 2, 1, 3, 4, 2, 1, 5, 9, 6, 5, 4, 1, 6, 6, 7, 4, 3, 1, 4, 1, 4, 9, 20, 7, 3, 1, 7, 8, 6, 1, 15, 1, 5, 19, 11, 13, 9, 1, 21, 52, 7, 1

Offset

0,26

Comments

Inspired by web-based discussion started by Rajesh Bhowmick.

Links

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

Rajesh Bhowmick, A bit different from Goldbach's conjecture (February 27-28, 2012)

Example

a(p) = 1 for any prime p.
a(n) = 0 for 1, 4, 6, 8, 9, 22.
a(25) = 3 because 25 = 3 + 5 + 17 = 5 + 7 + 13 = 2 + 5 + 7 + 11.

Maple

with (numtheory):
a:= proc(n) local b, l, f;
      b:= proc(h, j) option remember;
            `if`(h=0, 1, `if`(j<1, 0,
            `if`(l[j]>h, 0, b(h-l[j], j-1)) +b(h, j-1)))
          end; forget (b);
      f:= factorset(n);
      l:= sort([({seq (ithprime(i), i=1..pi(n))} minus f)[]]);
      b(n-add(i, i=f), nops(l))
    end:
seq (a(n), n=0..300); # Alois P. Heinz, Mar 20 2012

Mathematica

restrictedIntegerPartition[ n_Integer, list_List ] := 1 /; n == 0
restrictedIntegerPartition[ n_Integer, list_List ] := 0 /; n < 0 || Total[list] < n || n < Min[list]
restrictedIntegerPartition[ n_Integer, list_List ] := restrictedIntegerPartition[n - First[list], Rest[list]] + restrictedIntegerPartition[n, Rest[list]]
distinctPrimeFactors[ n_Integer ] := distinctPrimeFactors[n] = Map[First, FactorInteger[n]]
oeisA076694[ n_Integer ] := oeisA076694[n] = n - Total[distinctPrimeFactors[n]]
oeisA208614[ n_Integer ] := restrictedIntegerPartition[oeisA076694[n], Sort[Complement[Prime @ Range @ PrimePi @ oeisA076694 @ n, distinctPrimeFactors[n]] , Greater ]]
Table[oeisA208614[n], {n, 1, 100}]

Prog

(* maxima *)
countRestrictedIntegerPartitions(n, L) := if ( n = 0 ) then 1 else if ( ( n < 0 ) or ( lsum(k, k, L) < n ) or ( n < lmin( L ) ) ) then 0 else block( [ m, R ], m : first(L), R : rest(L), countRestrictedIntegerPartitions(n, R) + countRestrictedIntegerPartitions(n - m, R));
distinctPrimeFactors(n) := map(first, ifactors(n));
oeisA076694(n) := n - lsum(k, k, distinctPrimeFactors(n));
listOfPrimesLessThanOrEqualTo (n) := block( [ list : [] , i], for i : 2 step 0 while i <= n do ( list : cons(i, list) , i : next_prime(i) ) , list );
oeisA208614(n) := block([ m, list ], m : oeisA076694(n), list : sort(listify(setdifference(setify(listOfPrimesLessThanOrEqualTo(m)), setify(distinctPrimeFactors(n)))), ordergreatp), countRestrictedIntegerPartitions(m, list));
makelist(oeisA208614(j), j, 1, 100);

Crossrefs

Cf. A000586 (upper bound). A000586(A076694(n)) is a stricter upper bound.

Sequence in context: A190445 A141648 A118874 * A020851 A190457 A179833

Adjacent sequences: A208611 A208612 A208613 * A208615 A208616 A208617

Keyword

nonn

Author

Richard Penner, Feb 29 2012

Status

approved