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

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

Links

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

Index entries for sequences related to lcm's

Example

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

Mathematica

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

Prog

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

Crossrefs

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

Sequence in context: A355456 A097558 A124385 * A328575 A106478 A115069

Adjacent sequences: A317621 A317622 A317623 * A317625 A317626 A317627

Keyword

nonn

Author

Gus Wiseman, Aug 01 2018

Status

approved