OFFSET
1,1
COMMENTS
The divisibility poset on {1, ..., n} is ordered by divisibility: a <= b iff a divides b. A subset S is order-convex if whenever a, b in S with a|c|b (a divides c and c divides b), then c in S.
a(n) = 2 * a(n-1) if and only if n is prime. Every prime exactly doubles the count; every composite gives a ratio strictly less than 2. This provides a combinatorial characterization of the primes via convex subsets of the divisibility lattice.
Proof: A prime p <= n has no proper divisors in {2, ..., n} other than multiples of p exceeding p. Including or excluding p from any convex subset is independent of all other elements, so the count exactly doubles. For composite n with a proper divisor d where 1 < d < n, including both n and 1 in a convex subset forces d to be included (since 1|d|n), constraining the count below 2 * a(n-1).
The deficit 2 - a(n)/a(n-1) at composite n correlates with Omega(n) (number of prime factors with multiplicity) at r = 0.857.
The growth rate satisfies log(a(n))/n -> c where c is approximately 0.63.
LINKS
Thomas DiFiore, Lean 4 formal verification.
Thomas DiFiore, Causal-Algebraic Geometry, Zenodo.
FORMULA
a(n) = 2 * a(n-1) if and only if n is prime.
a(n) < 2 * a(n-1) if and only if n is composite, n >= 4.
a(n) = 2^pi(n) * C(n) where pi(n) is the prime-counting function and C(n) changes only at composite values of n.
EXAMPLE
a(1) = 2: the empty set and {1}.
a(2) = 4 = 2*a(1): 2 is prime, so the count doubles. The subsets are {}, {1}, {2}, {1,2}.
a(3) = 8 = 2*a(2): 3 is prime, so the count doubles.
a(4) = 14 < 2*a(3) = 16: 4 is composite (4 = 2^2). Including {1,4} forces inclusion of 2 (since 1|2|4), reducing freedom.
a(5) = 28 = 2*a(4): 5 is prime, so the count doubles.
PROG
(Python)
from itertools import combinations
def a(n):
elements = list(range(1, n+1))
count = 0
for r in range(n+1):
for S in combinations(elements, r):
S_set = set(S)
convex = True
for x in S_set:
for y in S_set:
if x < y and y % x == 0:
for z in elements:
if z not in S_set and z % x == 0 and y % z == 0:
convex = False
break
if not convex: break
if not convex: break
if convex: count += 1
return count
print([a(n) for n in range(1, 11)]) # [2, 4, 8, 14, 28, 48, 96, 156, 296, 550]
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Thomas DiFiore, Mar 28 2026
EXTENSIONS
a(25)-a(31) from Sean A. Irvine, Apr 13 2026
STATUS
approved