|
%I #34 Feb 16 2022 07:41:18
%S 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,
%T 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,
%U 5043,1,1,15,1,1,230,1,17,1,242,1,4173,1,1,12,19,1
%N Number of integer partitions of n where all parts are > 1 and whose LCM is n.
%H Antti Karttunen, <a href="/A317624/b317624.txt">Table of n, a(n) for n = 0..359</a>
%H <a href="/index/Lc#lcm">Index entries for sequences related to lcm's</a>
%e 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).
%e The a(45) = 10 partitions:
%e (45),
%e (15,15,9,3,3), (15,9,9,9,3),
%e (15,9,9,3,3,3,3), (15,9,5,5,5,3,3), (9,9,9,5,5,5,3),
%e (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),
%e (9,5,5,5,3,3,3,3,3,3,3).
%e From _David A. Corneth_, Sep 08 2018: (Start)
%e 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.
%e For the tuple (45), there is 1 partition of 45 - 45 = 0 into parts with 45. That is: {()}.
%e 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)}.
%e 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)}.
%e 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).
%e 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.
%e 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.
%e Therefore a(45) = 1 + 4 + 4 + 1 = 10.
%e (End)
%e 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
%t Table[Length[Select[IntegerPartitions[n],And[Min@@#>=2,LCM@@#==n]&]],{n,30}]
%o (PARI)
%o strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);
%o 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));
%o A317624(n) = if(n<=1,0,partitions_into_lcm(n,n,strong_divisors_reversed(n))); \\ _Antti Karttunen_, Sep 07 2018
%o (PARI)
%o strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);
%o 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)));
%o 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) };
%o A317624(n) = if(n<=1,0,toplevel_starting_sets(n,n,strong_divisors_reversed(n))); \\ _Antti Karttunen_, Sep 08-10 2018
%Y Cf. A000837, A018818, A066874, A067538, A069626, A074761, A074971, A143773, A259936, A281116, A285572, A290103, A305566, A316429, A316431, A316432, A316433, A318670.
%K nonn
%O 0,13
%A _Gus Wiseman_, Aug 01 2018
|
