Search: a318670 -id:a318670
|
| |
|
|
A286518
|
|
Number of finite connected sets of positive integers greater than one with least common multiple n.
|
|
+10
40
|
|
|
|
1, 1, 1, 2, 1, 4, 1, 4, 2, 4, 1, 20, 1, 4, 4, 8, 1, 20, 1, 20, 4, 4, 1, 88, 2, 4, 4, 20, 1, 96, 1, 16, 4, 4, 4, 196, 1, 4, 4, 88, 1, 96, 1, 20, 20, 4, 1, 368, 2, 20, 4, 20, 1, 88, 4, 88, 4, 4, 1, 1824, 1, 4, 20, 32, 4, 96, 1, 20, 4, 96, 1, 1688, 1, 4, 20, 20, 4, 96, 1, 368, 8, 4, 1, 1824, 4, 4, 4, 88, 1, 1824, 4, 20
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Given a finite set S of positive integers greater than one, let G(S) be the simple labeled graph with vertex set S and edges between any two vertices that are not relatively prime. For example, G({6,14,15,35}) is a 4-cycle. A set S is said to be connected if G(S) is a connected graph.
|
|
|
LINKS
|
|
|
|
FORMULA
|
It seems that a(n) >= A318670(n), for all n > 1.
(End)
|
|
|
EXAMPLE
|
The a(6)=4 sets are: {6}, {2,6}, {3,6}, {2,3,6}.
|
|
|
MATHEMATICA
|
zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[Less@@#, GCD@@s[[#]]]>1&]}, If[c==={}, s, zsm[Union[Append[Delete[s, List/@c[[1]]], LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Rest[Divisors[n]]], zsm[#]==={n}&]], {n, 2, 20}]
|
|
|
PROG
|
(PARI)
isconnected(facs) = { my(siz=length(facs)); if(1==siz, 1, my(m=matrix(siz, siz, i, j, (gcd(facs[i], facs[j])!=1))^siz); for(n=1, siz, if(0==vecmin(m[n, ]), return(0))); (1)); };
A286518aux(n, parts, from=1, ss=List([])) = { my(k = #parts, s=0, newss); if(lcm(Vec(ss))==n && isconnected(ss), s++); for(i=from, k, newss = List(ss); listput(newss, parts[i]); s += A286518aux(n, parts, i+1, newss)); (s) };
|
|
|
CROSSREFS
|
Cf. A048143, A054921, A069626, A076078, A259936, A281116, A285572, A285573, A286520, A305193, A318670.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A069626
|
|
Number of sets of integers larger than one whose least common multiple is n.
|
|
+10
6
|
|
|
|
1, 1, 1, 2, 1, 5, 1, 4, 2, 5, 1, 22, 1, 5, 5, 8, 1, 22, 1, 22, 5, 5, 1, 92, 2, 5, 4, 22, 1, 109, 1, 16, 5, 5, 5, 200, 1, 5, 5, 92, 1, 109, 1, 22, 22, 5, 1, 376, 2, 22, 5, 22, 1, 92, 5, 92, 5, 5, 1, 1874, 1, 5, 22, 32, 5, 109, 1, 22, 5, 109, 1, 1696, 1, 5, 22, 22, 5, 109, 1, 376, 8, 5, 1, 1874, 5, 5, 5, 92, 1, 1874, 5, 22
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
a(p) = 1, a(p*q) = 5, a(p^2*q) = 13, a(p^3) = 4, a(p^4) = 8 etc. where p and q are primes. It can be shown that a(p^k) = 2^(k-1). Problem: find an expression for a(N) when N = p^a*q^b*r^c*..., p,q,r are primes.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = Sum_{ d divides n } mu(n/d)*2^(tau(d)-1). - Vladeta Jovovic, Jul 07 2003
|
|
|
EXAMPLE
|
a(6) = 5 as there are five such sets of natural numbers larger than one whose least common multiple is six: {6}, {2, 6}, {3, 6}, {2, 3} and {2, 3, 6}.
a(12) = 22 from {12}, {4,3}, {2,4,3}, {4,6}, {2,4,6}, {4,3,6}, {2,4,3,6}, {2,12}, {4,12}, {2,4,12}, {3,12}, {2,3,12}, {4,3,12}, {2,4,3,12}, {6,12}, {2,6,12}, {4,6,12}, {2,4,6,12}, {3,6,12}, {2,3,6,12}, {4,3,6,12}, {2,4,3,6,12}.
a(1) = 1 as there is only one set that satisfies the criteria, namely, an empty set {}, whose lcm is 1.
a(2) = 1 as the only set that satisfies the criteria is a singleton set {2}.
(End)
|
|
|
MAPLE
|
with(numtheory): seq(add(mobius(n/d)*2^(tau(d)-1), d in divisors(n)), n=1..80); # Ridouane Oudra, Mar 12 2024
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
a069626 n = sum $
map (\d -> (a008683 (n `div` d)) * 2 ^ (a000005 d - 1)) $ a027750_row n
(APL, Dyalog dialect)
divisors ← {ð←⍵{(0=⍵|⍺)/⍵}⍳⌊⍵*÷2 ⋄ 1=⍵:ð ⋄ ð, (⍵∘÷)¨(⍵=(⌊⍵*÷2)*2)↓⌽ð}
A069626 ← { D←1↓divisors(⍵) ⋄ T←(⍴D)⍴2 ⋄ +/⍵⍷{∧/D/⍨T⊤⍵}¨(-∘1)⍳2*⍴D } ⍝ (quite taxing on memory) - Antti Karttunen, Feb 18 2024
|
|
|
CROSSREFS
|
Cf. also A045778 (number of sets of integers > 1 whose product is n).
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A317624
|
|
Number of integer partitions of n where all parts are > 1 and whose LCM is n.
|
|
+10
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
|
|
|
|
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).
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.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.010 seconds
|
