cp's OEIS Frontend

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

%I A098743 #40 Aug 29 2018 02:52:20
%S A098743 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 A098743 147,206,77,846,35,1237,166,649,634,1078,60,3659,1244,1850,236,7244,
%U A098743 299,10086,1228,1858,4421,19195,243,17660,3244,12268,4039,48341,1819,27675
%N A098743 Number of partitions of n into aliquant parts (i.e., parts that do not divide n).
%C A098743 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 A098743 a(A000040(n)) = A002865(n) - 1.
%H A098743 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 A098743 7 = 2 + 2 + 3 = 2 + 5 = 3 + 4, so a(7) = 3.
%e A098743 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 A098743 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 A098743 # second Maple program:
%p A098743 a:= proc(m) option remember; local b; b:= proc(n, i)
%p A098743       option remember; `if`(n=0, 1, `if`(i<2, 0, b(n, i-1)+
%p A098743       `if`(irem(m, i)=0, 0, b(n-i, min(i, n-i))))) end; b(m$2)
%p A098743     end:
%p A098743 seq(a(n), n=0..60);  # _Alois P. Heinz_, Mar 11 2018
%t A098743 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 A098743 Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Apr 30 2018, after _Alois P. Heinz_ *)
%o A098743 (Haskell)
%o A098743 a098743 n = p [nd | nd <- [1..n], mod n nd /= 0] n where
%o A098743    p _  0 = 1
%o A098743    p [] _ = 0
%o A098743    p ks'@(k:ks) m | m < k = 0 | otherwise = p ks' (m - k) + p ks m
%o A098743 -- _Reinhard Zumkeller_, Nov 22 2011
%o A098743 (Haskell)  -- with memoization
%o A098743 import Data.MemoCombinators (memo3, integral)
%o A098743 a098743 n = a098743_list !! n
%o A098743 a098743_list = map (\x -> pMemo x 1 x) [0..] where
%o A098743    pMemo = memo3 integral integral integral p
%o A098743    p _ _ 0 = 1
%o A098743    p x k m | m < k        = 0
%o A098743            | mod x k == 0 = pMemo x (k + 1) m
%o A098743            | otherwise    = pMemo x k (m - k) + pMemo x (k + 1) m
%o A098743 -- _Reinhard Zumkeller_, Aug 08 2015
%o A098743 (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 A098743 Cf. A000040, A000041, A002865, A018818, A200745, A260797, A260798.
%Y A098743 See also A057562 (relatively prime parts).
%K A098743 nonn
%O A098743 0,8
%A A098743 _Reinhard Zumkeller_, Oct 01 2004
%E A098743 a(0) added and offset changed by _Reinhard Zumkeller_, Nov 22 2011
%E A098743 New wording for definition suggested by _Marc LeBrun_, Aug 07 2015