A066874 -id:A066874 - cp's OEIS frontend

A014652 Number of partitions of n in its prime divisors with at least one part of size 1.

1, 1, 1, 2, 1, 5, 1, 4, 3, 8, 1, 16, 1, 11, 11, 8, 1, 33, 1, 26, 15, 17, 1, 56, 5, 20, 9, 36, 1, 226, 1, 16, 23, 26, 23, 120, 1, 29, 27, 92, 1, 422, 1, 56, 78, 35, 1, 208, 7, 140, 35, 66, 1, 261, 35, 128, 39, 44, 1, 1487, 1, 47, 108, 32, 41, 996, 1, 86, 47, 1062, 1, 456, 1, 56

Offset: 1

Olivier Gérard

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
David A. Corneth, PARI program

Cf. A014648, A014649, A014650, A014651, A066874, A066882, A286852.

\\ This is for computing just a moderate number of terms:
prime_factors_with1_reversed(n) = vecsort(setunion([1],factor(n)[,1]~), , 4);
partitions_into_with_trailing_ones(n,parts,from=1) = if(!n,1, if(#parts<=(from+1), if(#parts == from,1,(1+(n\parts[from]))), my(s=0); for(i=from,#parts,if(parts[i]<=n, s += partitions_into_with_trailing_ones(n-parts[i],parts,i))); (s)));
A014652(n) = partitions_into_with_trailing_ones(n-1,prime_factors_with1_reversed(n)); \\ Antti Karttunen, Sep 10 2018

\\ For an efficient program to compute large numbers of terms, see David A. Corneth's PARI program included in the Links section. - Antti Karttunen, Sep 12 2018

Coefficient of x^(n-1) in expansion of (1/(1-x))*1/Product_{d is prime divisor of n} (1-x^d). - Vladeta Jovovic, Apr 11 2004

A317624 Number of integer partitions of n where all parts are > 1 and whose LCM is n.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 5, 1, 1, 1, 17, 1, 1, 1, 7, 1, 60, 1, 1, 1, 1, 1, 76, 1, 1, 1, 55, 1, 105, 1, 11, 10, 1, 1, 187, 1, 6, 1, 13, 1, 30, 1, 111, 1, 1, 1, 5043, 1, 1, 15, 1, 1, 230, 1, 17, 1, 242, 1, 4173, 1, 1, 12, 19, 1

Offset: 0

Gus Wiseman, Aug 01 2018

nonn

			The a(20) = 5 partitions are (20), (10,4,4,2), (10,4,2,2,2), (5,5,4,4,2), (5,5,4,2,2,2).
The a(45) = 10 partitions:
  (45),
  (15,15,9,3,3), (15,9,9,9,3),
  (15,9,9,3,3,3,3), (15,9,5,5,5,3,3), (9,9,9,5,5,5,3),
  (15,9,3,3,3,3,3,3,3), (9,9,5,5,5,3,3,3,3), (9,5,5,5,5,5,5,3,3),
  (9,5,5,5,3,3,3,3,3,3,3).
From _David A. Corneth_, Sep 08 2018: (Start)
Let sum(t) denote the sum of elements of a tuple t. The tuples t with distinct divisors of 45 that have lcm(t) = 45 and sum(t) <= 45 are {(45) and (3, 9, 15), (3, 5, 9, 15), (3, 5, 9), (5, 9), (9, 15), (5, 9, 15)}. For each such tuple t, find the number of partitions of 45 - s(t) into distinct parts of t.
For the tuple (45), there is 1 partition of 45 - 45 = 0 into parts with 45. That is: {()}.
For the tuple (3, 9, 15), there are 4 partitions of 45 - (3 + 9 + 15) = 18 into parts with 3, 9 and 15. They are {(3, 15), (9, 9), (3, 3, 3, 9), (3, 3, 3, 3, 3, 3)}.
For the tuple (3, 5, 9), there are 4 partitions of 45 - (3 + 5 + 9) = 28 into parts with 3, 5 and 9; they are {(5, 5, 9, 9), (3, 3, 3, 5, 5, 9), (3, 5, 5, 5, 5, 5), (3, 3, 3, 3, 3, 3, 5, 5)}.
For the tuple (3, 5, 9, 15), there is 1 partition of 45 - (3 + 5 + 9 + 15) = 13 into parts with 3, 5, 9 and 15. That is (3, 5, 5).
The other tuples, (5, 9), (9, 15), and (5, 9, 15); they give no extra tuples. That's because there is no solution to the Diophantine equation for 5x + 9y = 45 - (5 + 9), corresponding to the tuple (5, 9) with nonnegative x, y.
That also excludes (9, 15); if there is a solution for that, there would also be a solution for (5, 9). This could whittle down the number of seeds even further. Similarly, (5, 9, 15) gives no solution.
Therefore a(45) = 1 + 4 + 4 + 1 = 10.
(End)
In general, there are A318670(n) (<= A069626(n)) such seed sets of divisors where to start extending the partition from. (See the second PARI program which uses subroutine toplevel_starting_sets.) - _Antti Karttunen_, Sep 08 2018

Antti Karttunen, Table of n, a(n) for n = 0..359
Index entries for sequences related to lcm's

Cf. A000837, A018818, A066874, A067538, A069626, A074761, A074971, A143773, A259936, A281116, A285572, A290103, A305566, A316429, A316431, A316432, A316433, A318670.

Table[Length[Select[IntegerPartitions[n],And[Min@@#>=2,LCM@@#==n]&]],{n,30}]

strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);
partitions_into_lcm(orgn,n,parts,from=1,m=1) = if(!n,(m==orgn),my(k = #parts, s=0); for(i=from,k,if(parts[i]<=n, s += partitions_into_lcm(orgn,n-parts[i],parts,i,lcm(m,parts[i])))); (s));
A317624(n) = if(n<=1,0,partitions_into_lcm(n,n,strong_divisors_reversed(n))); \\ Antti Karttunen, Sep 07 2018

strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);
partitions_into(n,parts,from=1) = if(!n,1, if(#parts==from, (0==(n%parts[from])), my(s=0); for(i=from,#parts,if(parts[i]<=n, s += partitions_into(n-parts[i],parts,i))); (s)));
toplevel_starting_sets(orgn,n,parts,from=1,ss=List([])) = { my(k = #parts, s=0, newss); if(lcm(Vec(ss))==orgn,s += partitions_into(n,ss)); for(i=from,k,if(parts[i]<=n, newss = List(ss); listput(newss,parts[i]); s += toplevel_starting_sets(orgn,n-parts[i],parts,i+1,newss))); (s) };
A317624(n) = if(n<=1,0,toplevel_starting_sets(n,n,strong_divisors_reversed(n))); \\ Antti Karttunen, Sep 08-10 2018

A097798 Number of partitions of n into abundant numbers.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 4, 0, 1, 0, 2, 0, 4, 0, 2, 0, 0, 0, 7, 0, 2, 0, 2, 0, 8, 0, 5, 0, 2, 0, 14, 0, 4, 0, 4, 0, 14, 0, 8, 0, 5, 0, 23, 0, 9, 0, 9, 0, 26, 0, 18, 0, 9, 0, 38, 0, 16, 0, 17, 0, 46, 0, 29, 0, 19, 0, 65, 0, 32, 0

Offset: 0

Reinhard Zumkeller, Aug 25 2004

nonn

n = 977 = 945 + 32 is the first prime for which sequence obtains a nonzero value, as a(977) = a(32) = 1. 945 is the first term in A005231. - Antti Karttunen, Sep 06 2018

a(n) = 0 for 496 values of n, the largest of which is 991 (see A283550). - David A. Corneth, Sep 08 2018

David A. Corneth, Table of n, a(n) for n = 0..10000 (a(1) through a(532) by Antti Karttunen)
David A. Corneth, PARI program
Eric Weisstein's World of Mathematics, Abundant Number
Eric Weisstein's World of Mathematics, Partition

Cf. A005101, A005231, A000041, A097800, A097797, A097796, A097795.

Cf. also A066874, A282568, A283550.

v:=[n:n in [1..100]| SumOfDivisors(n) gt 2*n]; [#RestrictedPartitions(n,Set(v)): n in [0..100]]; // Marius A. Burtea, Aug 02 2019

n = 100; d = Select[Range[n], DivisorSigma[1, #] > 2 # &]; CoefficientList[ Series[1/Product[1 - x^d[[i]], {i, 1, Length[d]} ], {x, 0, n}], x] (* Amiram Eldar, Aug 02 2019 *)

abundants_up_to_reversed(n) = { my(s = Set([])); for(k=1,n,if(sigma(k)>(2*k),s = setunion([k],s))); vecsort(s, ,4); };
partitions_into(n,parts,from=1) = if(!n,1,my(k = #parts, s=0); for(i=from,k,if(parts[i]<=n, s += partitions_into(n-parts[i],parts,i))); (s));
A097798(n) = partitions_into(n,abundants_up_to_reversed(n)); \\ Antti Karttunen, Sep 06 2018

PARI
```
\\ see Corneth link
```

a(0) = 1 prepended by David A. Corneth, Sep 08 2018

A014649 Number of partitions of n into its nonprime power divisors with at least one part of size 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 6, 1, 1, 1, 2, 1, 15, 1, 1, 1, 1, 1, 16, 1, 1, 1, 6, 1, 21, 1, 2, 3, 1, 1, 26, 1, 5, 1, 2, 1, 18, 1, 6, 1, 1, 1, 238, 1, 1, 3, 1, 1, 31, 1, 2, 1, 31, 1, 139, 1, 1, 5, 2, 1, 37, 1, 26, 1, 1, 1, 414, 1, 1, 1, 6, 1, 612, 1, 2, 1, 1

Offset: 1

Olivier Gérard

nonn

Antti Karttunen, Table of n, a(n) for n = 1..20000
David A. Corneth & Antti Karttunen, PARI program

Cf. A014648, A014650, A014651, A014652, A066874.

\\ This is for computing a small number of terms:
nonprimepower_divisors_with1_reversed(n) = vecsort(select(d -> ((1==d) || !isprimepower(d)), divisors(n)), , 4);
partitions_into_with_trailing_ones(n, parts, from=1) = if(!n, 1, if(#parts<=(from+1), if(#parts == from, 1, (1+(n\parts[from]))), my(s=0); for(i=from, #parts, if(parts[i]<=n, s += partitions_into_with_trailing_ones(n-parts[i], parts, i))); (s)));
A014649(n) = partitions_into_with_trailing_ones(n-1, nonprimepower_divisors_with1_reversed(n)); \\ Antti Karttunen, Aug 23 2019

\\ For an efficient program to compute large numbers of terms, see PARI program included in the Links-section.

A014650 Number of partitions of n into its divisors that are powers of primes (A000961) with at least one part of size 1.

Original entry on oeis.org

1, 1, 1, 2, 1, 5, 1, 6, 3, 8, 1, 27, 1, 11, 11, 26, 1, 43, 1, 63, 15, 17, 1, 215, 5, 20, 18, 114, 1, 226, 1, 166, 23, 26, 23, 734, 1, 29, 27, 728, 1, 422, 1, 261, 181, 35, 1, 2697, 7, 179, 35, 357, 1, 791, 35, 1729, 39, 44, 1, 6747, 1, 47, 325, 1626, 41, 996, 1, 594, 47, 1062, 1, 20345, 1, 56, 327, 735, 47, 1374, 1, 13485, 216, 62, 1

Offset: 1

Olivier Gérard

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
David A. Corneth, PARI program

Cf. A000961, A014648, A014649, A014651, A014652, A066874.

\\ This is for computing a small number of terms:
primepower_divisors_with1_reversed(n) = vecsort(select(d -> ((1==d) || isprimepower(d)), divisors(n)), , 4);
partitions_into_with_trailing_ones(n,parts,from=1) = if(!n,1, if(#parts<=(from+1), if(#parts == from,1,(1+(n\parts[from]))), my(s=0); for(i=from,#parts,if(parts[i]<=n, s += partitions_into_with_trailing_ones(n-parts[i],parts,i))); (s)));
A014650(n) = partitions_into_with_trailing_ones(n-1,primepower_divisors_with1_reversed(n)); \\ Antti Karttunen, Sep 10 2018

\\ For an efficient program to compute large numbers of terms, see David A. Corneth's PARI program included in the Links-section. - Antti Karttunen, Sep 12 2018

More terms from and the name clarified by Antti Karttunen, Sep 10 2018

A286852 Number of partitions of n into unitary prime divisors of n.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 1, 0, 2, 0, 1, 1, 21, 1, 0, 2, 2, 2, 0, 1, 2, 2, 1, 1, 28, 1, 1, 1, 2, 1, 1, 0, 1, 2, 1, 1, 1, 2, 1, 2, 2, 1, 5, 1, 2, 1, 0, 2, 42, 1, 1, 2, 43, 1, 0, 1, 2, 1, 1, 2, 49, 1, 1, 0, 2, 1, 5, 2, 2, 2, 1, 1, 10, 2, 1, 2, 2, 2

Offset: 0

Ilya Gutkovskiy, Aug 01 2017

nonn

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

Antti Karttunen, Table of n, a(n) for n = 0..2309
Eric Weisstein's World of Mathematics, Unitary Divisor
Index entries for related partition-counting sequences

Cf. A018818, A055231, A056169, A066874, A066882, A225244, A284289.

Join[{1}, Table[d = Divisors[n]; Coefficient[Series[Product[1/(1 - Boole[GCD[n/d[[k]], d[[k]]] == 1 && PrimeQ[d[[k]]]] x^d[[k]]), {k, Length[d]}], {x, 0, n}], x, n], {n, 1, 95}]]

A055231(n) = {my(f=factor(n)); for (k=1, #f~, if (f[k, 2] > 1, f[k, 2] = 0); ); factorback(f); } \\ From A055231
unitary_prime_factors(n) = { my(ufs = factor(A055231(n))); ufs[,1]~; };
partitions_into(n,parts,from=1) = if(!n,1,my(k = #parts, s=0); for(i=from,k,if(parts[i]<=n, s += partitions_into(n-parts[i],parts,i))); (s));
A286852(n) = if(n<2,1-n,partitions_into(n,vecsort(unitary_prime_factors(n), , 4))); \\ Antti Karttunen, Jul 02 2018

a(n) = [x^n] Product_{p|n, p prime, gcd(p, n/p) = 1} 1/(1 - x^p).

a(n) = 0 if n is a powerful number (A001694).

A286851 Number of compositions (ordered partitions) of n into unitary divisors of n.

Original entry on oeis.org

1, 1, 2, 2, 2, 2, 25, 2, 2, 2, 129, 2, 170, 2, 742, 450, 2, 2, 4603, 2, 1503, 3321, 29967, 2, 9278, 2, 200390, 2, 13460, 2, 154004511, 2, 2, 226020, 9262157, 51886, 127654, 2, 63346598, 2044895, 170354, 2, 185493291001, 2, 1304512, 567124, 2972038875, 2, 59489916, 2, 20367343494, 184947044, 14324735, 2

Offset: 0

Ilya Gutkovskiy, Aug 01 2017

nonn

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

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

Cf. A066874, A100346, A246655, A284463, A284464, A284465, A284466.

a:= proc(n) option remember; local b, l; l, b:=
      select(x-> igcd(x, n/x)=1, numtheory[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..60);  # Alois P. Heinz, Aug 01 2017

Join[{1}, Table[d = Divisors[n]; Coefficient[Series[1/(1 - Sum[Boole[GCD[n/d[[k]], d[[k]]] == 1] x^d[[k]], {k, Length[d]}]), {x, 0, n}], x, n], {n, 1, 53}]]

from sympy import divisors, gcd
from sympy.core.cache import cacheit
@cacheit
def a(n):
    l=[x for x in divisors(n) if gcd(x, n//x)==1]
    @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(61)]) # Indranil Ghosh, Aug 01 2017, after Maple code

a(n) = [x^n] 1/(1 - Sum_{d|n, gcd(d, n/d) = 1} x^d).

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

A349542 Number of partitions of n into distinct unitary divisors of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2

Offset: 0

Ilya Gutkovskiy, Nov 21 2021

nonn

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

Cf. A033630, A066874, A077610, A286851, A293188.

a[n_] := SeriesCoefficient[Product[(1 + Boole[GCD[n/d, d] == 1] x^d), {d, Divisors[n]}], {x, 0, n}]; Table[a[n], {n, 0, 114}]

A349542(n) = if(!n, 1, my(p=1); fordiv(n,d, if(1==gcd(d,n/d), p *= (1 + 'x^d))); polcoeff(p,n)); \\ Antti Karttunen, Nov 22 2021

a(n) = [x^n] Product_{d|n, gcd(d,n/d) = 1} (1 + x^d).

cp's OEIS Frontend

A014652 Number of partitions of n in its prime divisors with at least one part of size 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A317624 Number of integer partitions of n where all parts are > 1 and whose LCM is n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A097798 Number of partitions of n into abundant numbers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Extensions

A014649 Number of partitions of n into its nonprime power divisors with at least one part of size 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

A014650 Number of partitions of n into its divisors that are powers of primes (A000961) with at least one part of size 1.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Extensions

A286852 Number of partitions of n into unitary prime divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A286851 Number of compositions (ordered partitions) of n into unitary divisors of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A349542 Number of partitions of n into distinct unitary divisors of n.

Views

Author