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,8

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.

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)

Example

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).

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 *)

Prog

(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
(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

Crossrefs

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

See also A057562 (relatively prime parts).

Sequence in context: A147610 A238313 A163270 * A283484 A355567 A130560

Adjacent sequences: A098740 A098741 A098742 * A098744 A098745 A098746

Keyword

nonn

Author

Reinhard Zumkeller, Oct 01 2004

Extensions

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

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

Status

approved