The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A317624 Number of integer partitions of n where all parts are > 1 and whose LCM is n. 6
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,13 LINKS Antti Karttunen, Table of n, a(n) for n = 0..359 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: A061680 A097558 A124385 * A328575 A106478 A115069 Adjacent sequences:  A317621 A317622 A317623 * A317625 A317626 A317627 KEYWORD nonn AUTHOR Gus Wiseman, Aug 01 2018 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 16 23:53 EDT 2021. Contains 347477 sequences. (Running on oeis4.)