A286518 Number of finite connected sets of positive integers greater than one with least common multiple n.

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

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.

a(n) depends only on prime signature of n (cf. A025487). - Antti Karttunen, Feb 17 2024

Links

Antti Karttunen, Table of n, a(n) for n = 1..719

Index entries for sequences computed from exponents in factorization of n

Formula

From Antti Karttunen, Feb 17 2024: (Start)

a(n) <= A069626(n).

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) };
A286518(n) = if(1==n, n, A286518aux(n, divisors(n))); \\ Antti Karttunen, Feb 17 2024

Crossrefs

Cf. A048143, A054921, A069626, A076078, A259936, A281116, A285572, A285573, A286520, A305193, A318670.

Sequence in context: A216864 A337175 A263432 * A029205 A229340 A322968

Adjacent sequences: A286515 A286516 A286517 * A286519 A286520 A286521

Keyword

nonn

Author

Gus Wiseman, Jul 24 2017

Extensions

Term a(1)=1 prepended and more terms added by Antti Karttunen, Feb 17 2024

Status

approved