cp's OEIS Frontend

A178830 Number of distinct partitions of {1,...,n} into two nonempty sets P and S with the product of the elements of P equal to the sum of elements in S.

%I A178830 #48 Nov 03 2023 15:55:19
%S A178830 0,0,1,0,1,1,1,1,1,3,1,2,1,3,3,3,3,1,4,4,3,2,2,4,3,5,3,2,4,5,4,5,6,1,
%T A178830 4,2,5,4,7,4,4,3,3,6,14,3,4,10,6,3,6,4,4,4,8,7,6,8,7,10,5,11,8,5,11,4,
%U A178830 7,7,5,8,12,5,6,9,8,11,8,5,8,9,8,10,8,12,7,11,8,7,7,8,6,7,8,11,8,16,9,12,13,8
%N A178830 Number of distinct partitions of {1,...,n} into two nonempty sets P and S with the product of the elements of P equal to the sum of elements in S.
%C A178830 That the terms are nonzero for n>4 is shown by the fact that for n odd, P={1,(n-1)/2,n-1} works, and for n even, P={1,(n-2)/2,n} works.
%C A178830 a(A207852(n)) = n and a(m) <> n for m < A207852(n). - _Reinhard Zumkeller_, Feb 21 2012
%D A178830 Problem 2826, Crux Mathematicorum, May 2004, 178-179
%H A178830 Alois P. Heinz, <a href="/A178830/b178830.txt">Table of n, a(n) for n = 1..1800</a>, (first 300 terms from Reinhard Zumkeller)
%e A178830 {1,2,3} can be partitioned into P={3} and S={1,2} with 3=1+2.  This is the only such partition, so a(3)=1.
%e A178830 {1,2,3,4,5} can be partitioned into P={1,2,4} and S={3,5} with 1*2*4=3+5.  This is the only such partition, so a(5)=1.
%e A178830 {1,...,10} can be partitioned into subsets P={1,2,3,7} and S={4,5,6,8,9,10} since 1*2*3*7=4+5+6+8+9+10. P can also be taken as P={6,7} or P={1,4,10}, and so there are 3 distinct ways to partition {1,...,10}, and so a(10)=3.
%p A178830 b:= proc(n, s, p)
%p A178830       `if`(s=p, 1, `if`(n<1, 0, b(n-1, s, p)+
%p A178830       `if`(s-n<p*n, 0, b(n-1, s-n, p*n))))
%p A178830     end:
%p A178830 a:= n-> `if`(n=1, 0, b(n, n*(n+1)/2, 1)):
%p A178830 seq(a(n), n=1..100);  # _Alois P. Heinz_, Jun 07 2012
%t A178830 b[_, s_, s_] = 1; b[n_ /; n < 1, _, _] = 0; b[n_, s_, p_] := b[n, s, p] = b[n-1, s, p] + If[s-n < p*n, 0, b[n-1, s-n, p*n]]; a[1] = 0; a[n_] := a[n] = b[n, n*(n+1)/2, 1]; Table[Print[a[n]]; a[n], {n, 1, 100}] (* _Jean-François Alcover_, Aug 16 2013, after _Alois P. Heinz_ *)
%o A178830 (PARI) maxprodset(n)=ii=1;while(ii!+ii*(ii+1)/2<n*(n+1)/2,ii=ii+1);return(ii-1);
%o A178830 {for(jj=2,100,
%o A178830    countK=0;
%o A178830    S=vector(jj,ii,ii);
%o A178830    for(subsize=1,maxprodset(jj),
%o A178830       forvec(v=vector(subsize,k,[1,#S]),
%o A178830          vs=vecextract(S,v);
%o A178830          summ=jj*(jj+1)/2-sum(jk=1,#vs,vs[jk]);
%o A178830          prodd=prod(jk=1,#vs,vs[jk]);
%o A178830          if(summ==prodd,countK=countK+1),
%o A178830       2));
%o A178830    print1(countK,",");
%o A178830 )
%o A178830 }
%o A178830 (Haskell)
%o A178830 a178830 1 = 0
%o A178830 a178830 n = z [1..n] (n * (n + 1) `div` 2) 1 where
%o A178830    z []     s p             = fromEnum (s == p)
%o A178830    z (x:xs) s p | s > p     = z xs (s - x) (p * x) + z xs s p
%o A178830                 | otherwise = fromEnum (s == p)
%o A178830 -- _Reinhard Zumkeller_, Feb 21 2012
%K A178830 nonn,nice
%O A178830 1,10
%A A178830 _Matthew Conroy_, Dec 31 2010