VOOZH about

URL: https://oeis.org/A098743

⇱ A098743 - OEIS

login
A098743
Number of partitions of n into aliquant parts (i.e., parts that do not divide n).
31
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
# Alternative:
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
See also A057562 (relatively prime parts).
Sequence in context: A147610 A238313 A163270 * A283484 A355567 A130560
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