login
Number of partitions of n into aliquant parts (i.e., parts that do not divide n).
31

%I #40 Aug 29 2018 02:52:20

%S 1,0,0,0,0,1,0,3,1,3,3,13,1,23,10,11,9,65,8,104,14,56,66,252,10,245,

%T 147,206,77,846,35,1237,166,649,634,1078,60,3659,1244,1850,236,7244,

%U 299,10086,1228,1858,4421,19195,243,17660,3244,12268,4039,48341,1819,27675

%N Number of partitions of n into aliquant parts (i.e., parts that do not divide n).

%C It seems very plausible that the low and high water marks occur when n is a factorial number or a prime: see A260797, A260798.

%C a(A000040(n)) = A002865(n) - 1.

%H Alois P. Heinz, <a href="/A098743/b098743.txt">Table of n, a(n) for n = 0..1000</a> (first 300 terms from N. J. A. Sloane, next 200 terms from Reinhard Zumkeller)

%e 7 = 2 + 2 + 3 = 2 + 5 = 3 + 4, so a(7) = 3.

%e a(10) = #{7+3,6+4,4+3+3} = 3, all other partitions of 10 contain at least one divisor (10, 5, 2, or 1).

%p a := [1,0,0,0,0]; M:=300; for n from 5 to M do t1:={seq(i,i=1..n)}; t3 := t1 minus divisors(n); t4 := mul(1/(1-x^i), i in t3); t5 := series(t4,x,n+2); a:=[op(a), coeff(t5,x,n)]; od: a; # _N. J. A. Sloane_, Aug 08 2015

%p # second Maple program:

%p a:= proc(m) option remember; local b; b:= proc(n, i)

%p option remember; `if`(n=0, 1, `if`(i<2, 0, b(n, i-1)+

%p `if`(irem(m, i)=0, 0, b(n-i, min(i, n-i))))) end; b(m$2)

%p end:

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Mar 11 2018

%t a[m_] := a[m] = Module[{b}, b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 2, 0, b[n, i-1] + If[Mod[m, i] == 0, 0, b[n-i, Min[i, n-i]]]]]; b[m, m]];

%t Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Apr 30 2018, after _Alois P. Heinz_ *)

%o (Haskell)

%o a098743 n = p [nd | nd <- [1..n], mod n nd /= 0] n where

%o p _ 0 = 1

%o p [] _ = 0

%o p ks'@(k:ks) m | m < k = 0 | otherwise = p ks' (m - k) + p ks m

%o -- _Reinhard Zumkeller_, Nov 22 2011

%o (Haskell) -- with memoization

%o import Data.MemoCombinators (memo3, integral)

%o a098743 n = a098743_list !! n

%o a098743_list = map (\x -> pMemo x 1 x) [0..] where

%o pMemo = memo3 integral integral integral p

%o p _ _ 0 = 1

%o p x k m | m < k = 0

%o | mod x k == 0 = pMemo x (k + 1) m

%o | otherwise = pMemo x k (m - k) + pMemo x (k + 1) m

%o -- _Reinhard Zumkeller_, Aug 08 2015

%o (PARI) a(n)={polcoef(1/prod(k=1, n, if(n%k, 1 - x^k, 1) + O(x*x^n)), n)} \\ _Andrew Howroyd_, Aug 29 2018

%Y Cf. A000040, A000041, A002865, A018818, A200745, A260797, A260798.

%Y See also A057562 (relatively prime parts).

%K nonn

%O 0,8

%A _Reinhard Zumkeller_, Oct 01 2004

%E a(0) added and offset changed by _Reinhard Zumkeller_, Nov 22 2011

%E New wording for definition suggested by _Marc LeBrun_, Aug 07 2015