A395489 Number of gcd-closed subsets of {1,2,...,n}.

1, 2, 4, 7, 13, 22, 38, 67, 121, 208, 346, 663, 1067, 2084, 3650, 5621, 10187, 20228, 33960, 67673, 106919, 167302, 316644, 632549, 988585, 1672754, 3243116, 5502723, 9032101, 18060326, 26876518, 53747047, 97409341, 162001788, 320354230, 488138971, 761529731

Offset

0,2

Comments

A set S is gcd-closed if i, j in S always implies that gcd(i,j) in S. This concept was introduced by Beslin and Ligh (see Links), but it appears no one up to now studied the number of such sets.

From David A. Corneth, Apr 26 2026: (Start)

Some branch and cutting can be used to calculate terms for this sequence. Let's introduce some notation for presence of numbers in [1..n]. Let "X" denote the number at this position is not present. Let a number denote that that number is most definitely present. Let ? denote the number at this position may or may not be present.

So [X, 2, 3, ?, ?] denotes: in a set, 1 is most definitely not present, 2 and 3 are present and 4 and 5 may not be present.

From this information we can find that any such set is not gcd-closed. gcd(2, 3) = 1 and 1 is not present.

Up to 4 there is 1 position "?". This means that 2^1 = 2 subsets of {1..n} are not gcd-closed, which is found from [X, 2, 3]. These subsets are {2, 3} and {2, 3, 4}.

Similar, up to 5 there are two positions with ? which means 2^2 = 4 subset of [1..n] are not gcd-closed from [X, 2, 3]. These subsets are {2, 3}, {2, 3, 4}, {2, 3, 5}, {2, 3, 4, 5}.

After finding the number Q of subsets that are not gcd-closed we have a(n) = 2^n - Q. (End)

References

J. Shallit, The number of gcd-closed subsets of {1,2,...,n}, in preparation (2026).

Links

Table of n, a(n) for n=0..36.

S. Beslin and S. Ligh, Another generalisation of Smith's determinant, Bull. Austral. Math. Soc. 40 (1989), 413-415.

Formula

Limit_{n->infinity} (log_2 a(n))/n exists and is approximately 0.82, but it seems difficult to estimate the limit precisely.

Example

For n = 4 the three omitted subsets of {1,2,3,4} are {2,3}, {3,4}, and {2,3,4}, so a(4) = 2^4 - 3 = 13.

Prog

(Python)
from math import gcd
from itertools import count, islice
def agen(): # generator of terms
    G = [0]
    for n in count(1):
        yield len(G)
        newG, maskn = [], 1<<n
        for g in G:
            i, passes = n-1, True
            while i:
                if (1<<i)&g:
                    if not (1<<gcd(i, n))&g:
                        passes = False
                        break
                i -= 1
            if passes:
                newG.append(maskn|g)
        G += newG
print(list(islice(agen(), 25))) # Michael S. Branicky, Apr 25 2026

Crossrefs

Sequence in context: A281362 A319111 A128768 * A391682 A235607 A254007

Adjacent sequences: A395486 A395487 A395488 * A395490 A395491 A395492

Keyword

nonn

Author

Jeffrey Shallit, Apr 25 2026

Extensions

a(33)-a(36) from Michael S. Branicky, Apr 25 2026

Status

approved