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

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, 147, 206, 77, 846, 35, 1237, 166, 649, 634, 1078, 60, 3659, 1244, 1850, 236, 7244, 299, 10086, 1228, 1858, 4421, 19195, 243, 17660, 3244, 12268, 4039, 48341, 1819, 27675

Offset: 0

Author

Reinhard Zumkeller, Oct 01 2004

Keywords

• nonn

Comments

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

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

Examples

			7 = 2 + 2 + 3 = 2 + 5 = 3 + 4, so a(7) = 3.
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).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 300 terms from N. J. A. Sloane, next 200 terms from Reinhard Zumkeller)

Crossrefs

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

See also A057562 (relatively prime parts).

Programs

Haskell

a098743 n = p [nd | nd <- [1..n], mod n nd /= 0] n where
   p _  0 = 1
   p [] _ = 0
   p ks'@(k:ks) m | m < k = 0 | otherwise = p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Nov 22 2011

Haskell

-- with memoization
import Data.MemoCombinators (memo3, integral)
a098743 n = a098743_list !! n
a098743_list = map (\x -> pMemo x 1 x) [0..] where
   pMemo = memo3 integral integral integral p
   p   0 = 1
   p x k m | m < k        = 0
           | mod x k == 0 = pMemo x (k + 1) m
           | otherwise    = pMemo x k (m - k) + pMemo x (k + 1) m
-- Reinhard Zumkeller, Aug 08 2015

Maple

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
# second Maple program:
a:= proc(m) option remember; local b; b:= proc(n, i)
      option remember; `if`(n=0, 1, `if`(i<2, 0, b(n, i-1)+
      `if`(irem(m, i)=0, 0, b(n-i, min(i, n-i))))) end; b(m$2)
    end:
seq(a(n), n=0..60);  # Alois P. Heinz, Mar 11 2018

Mathematica

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]];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Apr 30 2018, after Alois P. Heinz *)

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

Extensions

a(0) added and offset changed by Reinhard Zumkeller, Nov 22 2011

New wording for definition suggested by Marc LeBrun, Aug 07 2015