OFFSET
0,13
LINKS
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
KEYWORD
nonn
AUTHOR
Gus Wiseman, Aug 01 2018
STATUS
approved