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
Keywords
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
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
Comments