cp's OEIS Frontend

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

%I A208614 #31 May 23 2024 15:07:28
%S A208614 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,
%T A208614 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,
%U A208614 7,8,6,1,15,1,5,19,11,13,9,1,21,52,7,1
%N A208614 Number of partitions of n into distinct primes where all of the prime factors of n are represented in the partition.
%C A208614 Inspired by web-based discussion started by Rajesh Bhowmick.
%H A208614 Alois P. Heinz, <a href="/A208614/b208614.txt">Table of n, a(n) for n = 0..5000</a>
%H A208614 Rajesh Bhowmick, <a href="http://sciforums.com/showthread.php?t=112659">A bit different from Goldbach's conjecture</a> (February 27-28, 2012)
%e A208614 a(p) = 1 for any prime p.
%e A208614 a(n) = 0 for 1, 4, 6, 8, 9, 22.
%e A208614 a(25) = 3 because 25 = 3 + 5 + 17 = 5 + 7 + 13 = 2 + 5 + 7 + 11.
%p A208614 with(numtheory):
%p A208614 a:= proc(n) local b, l, f;
%p A208614       b:= proc(h, j) option remember;
%p A208614             `if`(h=0, 1, `if`(j<1, 0,
%p A208614             `if`(l[j]>h, 0, b(h-l[j], j-1)) +b(h, j-1)))
%p A208614           end; forget(b);
%p A208614       f:= factorset(n);
%p A208614       l:= sort([({seq(ithprime(i), i=1..pi(n))} minus f)[]]);
%p A208614       b(n-add(i, i=f), nops(l))
%p A208614     end:
%p A208614 seq(a(n), n=0..300);  # _Alois P. Heinz_, Mar 20 2012
%t A208614 restrictedIntegerPartition[ n_Integer, list_List ] := 1 /; n == 0
%t A208614 restrictedIntegerPartition[ n_Integer, list_List ] := 0 /; n < 0 || Total[list] < n || n < Min[list]
%t A208614 restrictedIntegerPartition[ n_Integer, list_List ] := restrictedIntegerPartition[n - First[list], Rest[list]] + restrictedIntegerPartition[n, Rest[list]]
%t A208614 distinctPrimeFactors[ n_Integer ] := distinctPrimeFactors[n] = Map[First, FactorInteger[n]]
%t A208614 oeisA076694[ n_Integer ] := oeisA076694[n] = n - Total[distinctPrimeFactors[n]]
%t A208614 oeisA208614[ n_Integer ] := restrictedIntegerPartition[oeisA076694[n], Sort[Complement[Prime @ Range @ PrimePi @ oeisA076694 @ n, distinctPrimeFactors[n]] , Greater ]]
%t A208614 Table[oeisA208614[n], {n,1,100}]
%o A208614 (Maxima)
%o A208614 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));
%o A208614 distinctPrimeFactors(n) := map(first,ifactors(n));
%o A208614 oeisA076694(n) := n - lsum(k,k,distinctPrimeFactors(n));
%o A208614 listOfPrimesLessThanOrEqualTo (n) := block( [ list : [] , i], for i : 2 step 0 while i <= n do ( list : cons(i, list) , i : next_prime(i) ) , list );
%o A208614 oeisA208614(n) := block([ m, list ], m : oeisA076694(n), list : sort(listify(setdifference(setify(listOfPrimesLessThanOrEqualTo(m)), setify(distinctPrimeFactors(n)))), ordergreatp), countRestrictedIntegerPartitions(m, list));
%o A208614 makelist(oeisA208614(j), j, 1, 100);
%Y A208614 Cf. A000586 (upper bound). A000586(A076694(n)) is a stricter upper bound.
%K A208614 nonn
%O A208614 0,26
%A A208614 _Richard Penner_, Feb 29 2012