A358392 Number of nonempty subsets of {1, 2, ..., n} with GCD equal to 1 and containing the sum of any two elements whenever it is at most n.

1, 1, 2, 3, 7, 9, 19, 27, 46, 63, 113, 148, 253, 345, 539, 734, 1198, 1580, 2540, 3417, 5233, 7095, 11190, 14720, 22988, 31057, 47168, 63331, 98233, 129836, 200689, 269165, 406504, 546700, 838766, 1108583, 1700025, 2281517, 3437422, 4597833, 7023543, 9308824, 14198257, 18982014, 28556962

Offset

1,3

Comments

Also, the number of distinct numerical semigroups that are generated by some subset of {1, 2, ..., n} and have a finite complement in the positive integers.

Links

Max Alekseyev, Table of n, a(n) for n = 1..100

Marcel K. Goh et al., Counting numerical semigroups by largest element of minimal generating set, MathOverflow, 2022.

Formula

a(n) = Sum_{k=1..n} moebius(k) * A103580(floor(n/k)).

Crossrefs

Inverse Moebius transform of A103580.

Cf. A007865, A050291, A051026, A085489, A139384, A151897, A308546, A326020, A326076, A326080, A326083, A326114.

Sequence in context: A327779 A291740 A204520 * A007649 A218909 A225202

Adjacent sequences: A358389 A358390 A358391 * A358393 A358394 A358395

Keyword

nonn

Author

Max Alekseyev, Nov 13 2022

Status

approved