A225245 -id:A225245 - cp's OEIS frontend

A033630 Number of partitions of n into distinct divisors of n.

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 6, 1, 1, 1, 2, 1, 4, 1, 1, 1, 1, 1, 8, 1, 1, 1, 4, 1, 3, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 4, 1, 3, 1, 1, 1, 35, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 32, 1, 1, 1, 1, 1, 2, 1, 7, 1, 1, 1, 26, 1, 1, 1, 2, 1, 24, 1, 1, 1, 1, 1, 22, 1, 1, 1, 3

Offset: 0

Marc LeBrun

nonn

			a(12) = 3 because we have the partitions [12], [6, 4, 2], and [6, 3, 2, 1].

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (1000 terms from T. D. Noe)
Noah Lebowitz-Lockard and Joseph Vandehey, On the number of partitions of a number into distinct divisors, arXiv:2402.08119 [math.NT], 2024. See p. 2.

Cf. A018818, A065205.
Cf. A083206. - Reinhard Zumkeller, Jul 19 2010
Cf. A000009, A005153.
Cf. A211111, A027750.
Cf. A225245.
Cf. A000396, A005100, A005835, A006037.

a033630 0 = 1
a033630 n = p (a027750_row n) n where
   p _  0 = 1
   p [] _ = 0
   p (d:ds) m = if d > m then 0 else p ds (m - d) + p ds m
-- Reinhard Zumkeller, Feb 23 2014, Apr 04 2012, Oct 27 2011

with(numtheory): a:=proc(n) local div, g, gser: div:=divisors(n): g:=product(1+x^div[j],j=1..tau(n)): gser:=series(g,x=0,105): coeff(gser,x^n): end: seq(a(n),n=1..100); # Emeric Deutsch, Mar 30 2006
# second Maple program:
with(numtheory):
a:= proc(n) local b, l; l:= sort([(divisors(n))[]]):
      b:= proc(m, i) option remember; `if`(m=0, 1, `if`(i<1, 0,
             b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i-1))))
          end; forget(b):
      b(n, nops(l))
    end:
seq(a(n), n=0..100); # Alois P. Heinz, Feb 05 2014

A033630 = Table[SeriesCoefficient[Series[Times@@((1 + z^#) & /@ Divisors[n]), {z, 0, n}], n ], {n, 512}] (* Wouter Meeussen *)
A033630[n_] := f[n, n, 1]; f[n_, m_, k_] := f[n, m, k] = If[k <= m, f[n, m, k + 1] + f[n, m - k, k + 1] * Boole[Mod[n, k] == 0], Boole[m == 0]]; Array[A033630, 101, 0] (* Jean-François Alcover, Jul 29 2015, after Reinhard Zumkeller *)

a(n) = A065205(n) + 1.
a(A005100(n)) = 1; a(A005835(n)) > 1. - Reinhard Zumkeller, Mar 02 2007
a(n) = f(n, n, 1) with f(n, m, k) = if k <= m then f(n, m, k + 1) + f(n, m - k, k + 1)*0^(n mod k) else 0^m. - Reinhard Zumkeller, Dec 11 2009
a(n) = [x^n] Product_{d|n} (1 + x^d). - Ilya Gutkovskiy, Jul 26 2017
a(n) = 1 if n is deficient (A005100) or weird (A006037). a(n) = 2 if n is perfect (A000396). - Alonso del Arte, Sep 24 2017

More terms from Reinhard Zumkeller, Apr 21 2003

A087188 Number of partitions of n into distinct squarefree parts.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 3, 3, 4, 4, 5, 6, 6, 8, 9, 10, 13, 14, 16, 18, 20, 24, 27, 30, 35, 37, 42, 47, 51, 59, 64, 72, 81, 88, 98, 109, 120, 134, 147, 163, 179, 195, 216, 236, 258, 284, 310, 339, 371, 403, 441, 480, 523, 572, 621, 675, 734, 796, 865, 937, 1014, 1100, 1189

Offset: 0

Reinhard Zumkeller, Aug 24 2003

nonn

			n=9: 5+3+1 = 6+2+1 = 6+3 = 7+2: a(9)=4;
n=10: 5+3+2 = 6+3+1 = 7+2+1 = 7+3 = 10: a(10)=5.

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A073576, A000009, A005117, A008966, A225245, A256012.

a087188 = p a005117_list where
   p _      0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jun 01 2015

with(numtheory):
b:= proc(n, i) option remember;
      `if`(i*(i+1)/2 b(n$2):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 02 2015

b[n_, i_] := b[n, i] = If[i*(i+1)/2 < n, 0, If[n == 0, 1, b[n, i-1] + If[i <= n && SquareFreeQ[i], b[n-i, i-1], 0]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 24 2015, after Alois P. Heinz *)
nmax = 100; CoefficientList[Series[Exp[Sum[(-1)^(j + 1)/j * Sum[Abs[MoebiusMu[k]] * x^(j*k), {k, 1, Floor[nmax/j] + 1}], {j, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Mar 31 2018 *)

ok(v)=for(i=2,#v, if(v[i]==v[i-1] || !issquarefree(v[i]), return(0))); #v==0 || issquarefree(v[1])
a(n)=my(s,u); forpart(v=n, if(ok(v), s++)); s \\ Charles R Greathouse IV, Nov 05 2017

O.g.f.: product_{i=1,2,...infinity} [1+x^A005117(i)]. - R. J. Mathar, May 16 2008

a(n) ~ exp(sqrt(2*n)) / (2^(1/4) * sqrt(Pi) * n^(3/4)). - Vaclav Kotesovec, Mar 24 2018

Offset changed and a(0)=1 prepended by Reinhard Zumkeller, Jun 01 2015

A225244 Number of partitions of n into squarefree divisors of n.

Original entry on oeis.org

1, 1, 2, 2, 3, 2, 8, 2, 5, 4, 11, 2, 27, 2, 14, 14, 9, 2, 64, 2, 40, 18, 20, 2, 125, 6, 23, 10, 53, 2, 742, 2, 17, 26, 29, 26, 343, 2, 32, 30, 195, 2, 1654, 2, 79, 136, 38, 2, 729, 8, 341, 38, 92, 2, 1000, 38, 265, 42, 47, 2, 14188, 2, 50, 184, 33, 44, 5257, 2

Offset: 0

Reinhard Zumkeller, May 05 2013

nonn

a(n) <= A018818(n);
a(n) = A018818(n) iff n is squarefree: a(A005117(n)) = A018818(A005117(n));
a(A000040(n)) = 2.

			a(8) = #{2+2+2+2, 2+2+2+1+1, 2+2+1+1+1+1, 2+6x1, 8x1} = 5;
a(9) = #{3+3+3, 3+3+1+1+1, 3+1+1+1+1+1+1, 9x1} = 4;
a(10) = #{10, 5+5, 5+2+2+1, 5+2+1+1+1, 5+5x1, 2+2+2+2+2, 2+2+2+2+1+1, 2+2+2+1+1+1+1, 2+2+6x1, 2+8x1, 10x1} = 11;
a(11) = #{11, 1+1+1+1+1+1+1+1+1+1+1} = 2;
a(12) = #{6+6, 6+3+3, 6+3+2+1, 6+3+1+1+1, 6+2+2+2, 6+2+2+1+1, 6+2+1+1+1+1, 6+6x1, 3+3+3+3, 3+3+3+2+1, 3+3+3+1+1+1, 3+3+2+2+2, 3+3+2+2+1+1, 3+3+2+4x1, 3+3+6x1, 3+2+2+2+2+1, 3+2+2+2+1+1+1, 3+2+2+5x1, 3+2+7x1, 3+8x1, 2+2+2+2+2+2, 2+2+2+2+2+1+1, 2+2+2+2+1+1+1+1, 2+2+2+6x1, 2+2+8x1, 2+10x1, 12x1} = 27;
a(13) = #{11, 1+1+1+1+1+1+1+1+1+1+1+1+1} = 2;
a(14) = #{14, 7+7, 7+2+2+2+1, 7+2+2+1+1+1, 7+2+5x1, 7+7x1, 7x2, 6x2+1+1, 5x2+1+1+1+1, 4x2+6x1, 2+2+2+8x1, 2+2+10x1, 2+12x1, 14x1} = 14;
a(15) = #{15, 5+5+5, 5+5+3+1+1, 5+5+5x1, 5+3+3+3+1, 5+3+3+1+1+1+1, 5+3+7x1, 5+10x1, 3+3+3+3+3, 3+3+3+3+1+1+1, 3+3+3+6x1, 3+3+9x1, 3+12x1, 15x1} = 14.

Alois P. Heinz, Table of n, a(n) for n = 0..10000 (300 terms from Reinhard Zumkeller)

Cf. A206778, A005117, A008966, A225245, A073576.

a225244 n = p (a206778_row n) n where
   p _          0 = 1
   p []         _ = 0
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

with(numtheory):
a:= proc(n) local b, l; l:= sort([select(issqrfree, divisors(n))[]]):
      b:= proc(m, i) option remember; `if`(m=0 or i=1, 1,
            `if`(i<1, 0, b(m, i-1)+`if`(l[i]>m, 0, b(m-l[i], i))))
          end; forget(b):
      b(n, nops(l))
    end:
seq(a(n), n=0..100); # Alois P. Heinz, Feb 05 2014

a[0] = 1; a[n_] := Module[{b, l}, l = Select[Divisors[n], SquareFreeQ]; b[m_, i_] := b[m, i] = If[m == 0 || i == 1, 1, If[i < 1, 0, b[m, i - 1] + If[l[[i]] > m, 0, b[m - l[[i]], i]]]]; b[n, Length[l]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 27 2015, after Alois P. Heinz *)

a(n) = [x^n] Product_{d|n, mu(d) != 0} 1/(1 - x^d), where mu() is the Moebius function (A008683). - Ilya Gutkovskiy, Jul 26 2017

A225354 Numbers that can be written as sum of distinct squarefree divisors.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 60, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 77, 78, 79, 82, 83, 84, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102

Offset: 1

Reinhard Zumkeller, May 05 2013

nonn

A225245(a(n)) > 0.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A225353 (complement).

import Data.List (findIndices)
a225354 n = a225354_list !! (n-1)
a225354_list = map (+ 1) $ findIndices (> 0) a225245_list

f[n_] := f[n] = Coefficient[Product[If[MoebiusMu[d] != 0, 1 + x^d, 1], {d, Divisors[n]}], x, n];
ParallelTable[If[f[k] > 0, k, Nothing], {k, 1, 1000}] (* Jean-François Alcover, May 04 2024, after Ilya Gutkovskiy in A225245 *)

A225353 Numbers having no partition into distinct squarefree divisors.

Original entry on oeis.org

4, 8, 9, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 63, 64, 68, 72, 75, 76, 80, 81, 88, 90, 92, 96, 98, 99, 100, 104, 108, 112, 116, 117, 120, 121, 124, 125, 126, 128, 135, 136, 140, 144, 147, 148, 150, 152, 153, 160, 162, 164

Offset: 1

Reinhard Zumkeller, May 05 2013

nonn

A225245(a(n)) = 0.
Verified up to a(366) = 1000, a(n) is also the order of a finite group G for which |Out(G)|>|G| for at least one group of order a(n), Out(G) being the outer automorphism group of G. - Miles Englezou, Apr 19 2024
By definition, a(n) is nonsquarefree for every n, since every squarefree number m has a trivial partition into distinct squarefree divisors m = m. - Miles Englezou, Apr 20 2024
If k is a term then so is k*m where m|k. - David A. Corneth, Apr 27 2024

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A013929, A225245, A225354 (complement).

import Data.List (elemIndices)
a225353 n = a225353_list !! (n-1)
a225353_list = map (+ 1) $ elemIndices 0 a225245_list

f[n_] := Coefficient[Product[If[MoebiusMu[d] != 0, 1 + x^d, 1], {d, Divisors[n]}], x, n];
Select[Range[200], f[#] == 0&] (* Jean-François Alcover, May 04 2024, after Ilya Gutkovskiy in A225245 *)

A284464 Number of compositions (ordered partitions) of n into squarefree divisors of n.

Original entry on oeis.org

1, 1, 2, 2, 5, 2, 25, 2, 34, 19, 129, 2, 1046, 2, 742, 450, 1597, 2, 44254, 2, 27517, 3321, 29967, 2, 1872757, 571, 200390, 18560, 854850, 2, 154004511, 2, 3524578, 226020, 9262157, 51886, 3353855285, 2, 63346598, 2044895, 1255304727, 2, 185493291001, 2, 1282451595, 345852035, 2972038875, 2, 6006303471178

Offset: 0

Ilya Gutkovskiy, Mar 27 2017

nonn

			a(4) = 5 because 4 has 3 divisors {1, 2, 4} among which 2 are squarefree {1, 2} therefore we have [2, 2], [2, 1, 1], [1, 2, 1], [1, 2, 2] and [1, 1, 1, 1].

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Eric Weisstein's World of Mathematics, Squarefree
Index entries for sequences related to compositions

Cf. A005117, A008683, A100346, A225244, A225245, A280194.

with(numtheory):
a:= proc(n) option remember; local b, l;
      l, b:= select(issqrfree, divisors(n)),
      proc(m) option remember; `if`(m=0, 1,
         add(`if`(j>m, 0, b(m-j)), j=l))
      end; b(n)
    end:
seq(a(n), n=0..50);   # Alois P. Heinz, Mar 30 2017

Table[d = Divisors[n]; Coefficient[Series[1/(1 - Sum[MoebiusMu[d[[k]]]^2 x^d[[k]], {k, Length[d]}]), {x, 0, n}], x, n], {n, 0, 48}]

from sympy import divisors
from sympy.ntheory.factor_ import core
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if core(x)==x]
    @cacheit
    def b(m): return 1 if m==0 else sum(b(m - j) for j in l if j <= m)
    return b(n)
print([a(n) for n in range(51)]) # Indranil Ghosh, Aug 01 2017, after Maple code

a(n) = [x^n] 1/(1 - Sum_{d|n, |mu(d)| = 1} x^d), where mu(d) is the Moebius function (A008683).

a(n) = 2 if n is a prime.

A300586 Number of partitions of n into distinct squarefree parts that do not divide n.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 2, 1, 4, 2, 2, 4, 6, 2, 8, 4, 6, 6, 15, 4, 11, 10, 12, 8, 30, 3, 38, 24, 17, 24, 23, 14, 70, 36, 37, 23, 102, 8, 122, 49, 39, 80, 177, 38, 136, 54, 113, 101, 297, 60, 152, 102, 192, 226, 485, 28, 571, 312, 200, 390, 338, 84, 908, 393, 507, 104, 1229, 241, 1421

Offset: 0

Ilya Gutkovskiy, Mar 09 2018

nonn

			a(14) = 2 because we have [11, 3] and [6, 5, 3].

Index entries for sequences related to partitions

Cf. A005117, A087188, A200745, A209402, A225245, A300584, A300585.

Table[SeriesCoefficient[Product[(1 + Boole[Mod[n, k] != 0 && SquareFreeQ[k]] x^k), {k, 1, n}], {x, 0, n}], {n, 0, 73}]

A327641 Number of partitions of n into divisors d of n such that n/d is squarefree.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 8, 2, 2, 2, 11, 2, 8, 2, 14, 14, 2, 2, 8, 2, 11, 18, 20, 2, 8, 2, 23, 2, 14, 2, 742, 2, 2, 26, 29, 26, 8, 2, 32, 30, 11, 2, 1654, 2, 20, 14, 38, 2, 8, 2, 11, 38, 23, 2, 8, 38, 14, 42, 47, 2, 742, 2, 50, 18, 2, 44, 5257, 2, 29, 50, 5066, 2, 8, 2, 59, 14

Offset: 0

Ilya Gutkovskiy, Sep 20 2019

nonn

Antti Karttunen, Table of n, a(n) for n = 0..20000

Cf. A008683, A018818, A225244, A225245, A246655 (positions of 2's).

[1] cat [#RestrictedPartitions(n,{d:d in Divisors(n)|IsSquarefree(n div d)}):n in [1..75]]; // Marius A. Burtea, Sep 20 2019

a[n_] := SeriesCoefficient[Product[1/(1 - MoebiusMu[n/d]^2 x^d), {d, Divisors[n]}], {x, 0, n}]; Table[a[n], {n, 0, 75}]

A327641(n) = if(!n, 1, my(p = Ser(1, 'x, 1+n)); fordiv(n, d, if(issquarefree(n/d), p /= (1 - 'x^d))); polcoef(p, n)); \\ Antti Karttunen, Jan 28 2025

a(n) = [x^n] Product_{d|n} 1 / (1 - mu(n/d)^2 * x^d).

A378843 Number of compositions (ordered partitions) of n into distinct squarefree divisors of n.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 7, 1, 0, 0, 1, 1, 24, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 151, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 31, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 864, 1, 1, 0, 0, 1, 127, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 7, 1, 0

Offset: 0

Ilya Gutkovskiy, Dec 09 2024

nonn

From Robert Israel, Dec 15 2024: (Start)
If n is squarefree, a(n) >= 1, as [n] is a composition.
If n = b * c where b and c are coprime and c is squarefree, then a(n) >= a(b), as for any composition C of b into distinct squarefree divisors, multiplying each element of C by c gives a composition of n into distinct squarefree divisors. (End)

			a(6) = 7 because we have [6], [3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2] and [1, 2, 3].
a(12) = 24 because we have [6, 3, 2, 1] and 4! = 24 permutations.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A005117, A087188, A225244, A225245, A284464, A331846, A331927.

ptns:= proc(S,n) option remember;
  # subsets of S with sum n
  local m,s;
  if convert(S,`+`) < n then return {} fi;
  if n = 0 then return {{}} fi;
  s:= max(S);
  if s > n then return procname(select(`<=`,S,n),n) fi;
  map(t -> t union {s}, procname(S minus {s},n-s)) union procname(S minus {s}, n)
  end proc:
sfd:= proc(n) map(convert,combinat:-powerset(numtheory:-factorset(n)),`*`) end proc:
f:= proc(n) local t;
     add((nops(t))!, t = ptns(sfd(n),n))
end proc:
map(f, [$0..100]); # Robert Israel, Dec 15 2024

a[n_] := Module[{d = Select[Divisors[n], SquareFreeQ]}, Total[(Length /@ Select[Subsets[d], Total[#] == n &])!]]; a[0] = 1; Array[a, 100, 0] (* Amiram Eldar, Dec 10 2024 *)

cp's OEIS Frontend

A033630 Number of partitions of n into distinct divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

Extensions

A087188 Number of partitions of n into distinct squarefree parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A225244 Number of partitions of n into squarefree divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A225354 Numbers that can be written as sum of distinct squarefree divisors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A225353 Numbers having no partition into distinct squarefree divisors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

A284464 Number of compositions (ordered partitions) of n into squarefree divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A300586 Number of partitions of n into distinct squarefree parts that do not divide n.

Views

Author

Keywords

Examples

Links

Crossrefs