A395489 - OEIS

%I #18 Apr 27 2026 05:20:17

%S 1,2,4,7,13,22,38,67,121,208,346,663,1067,2084,3650,5621,10187,20228,

%T 33960,67673,106919,167302,316644,632549,988585,1672754,3243116,

%U 5502723,9032101,18060326,26876518,53747047,97409341,162001788,320354230,488138971,761529731

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

%C 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.

%C From _David A. Corneth_, Apr 26 2026: (Start)

%C 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.

%C 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.

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

%C 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}.

%C 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}.

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

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

%H S. Beslin and S. Ligh, <a href="https://doi.org/10.1017/S0004972700017457">Another generalisation of Smith's determinant</a>, Bull. Austral. Math. Soc. 40 (1989), 413-415.

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

%e 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.

%o (Python)

%o from math import gcd

%o from itertools import count, islice

%o def agen(): # generator of terms

%o     G = [0]

%o     for n in count(1):

%o         yield len(G)

%o         newG, maskn = [], 1<<n

%o         for g in G:

%o             i, passes = n-1, True

%o             while i:

%o                 if (1<<i)&g:

%o                     if not (1<<gcd(i, n))&g:

%o                         passes = False

%o                         break

%o                 i -= 1

%o             if passes:

%o                 newG.append(maskn|g)

%o         G += newG

%o print(list(islice(agen(), 25))) # _Michael S. Branicky_, Apr 25 2026

%K nonn

%O 0,2

%A _Jeffrey Shallit_, Apr 25 2026

%E a(33)-a(36) from _Michael S. Branicky_, Apr 25 2026