A390395 a(n) is the maximum size of a subset S of {1,...,n} such that there are no solutions to 1/a = 1/b + 1/c for distinct a,b,c in S.

1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25, 26, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 35, 36, 36, 37, 38, 39, 40, 41, 41, 42, 43, 44, 45, 46, 47, 48, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 57, 58, 59

Offset

1,2

Comments

Erdős has conjectured that a(n) = (1/2 + o(1))*n.

Further estimates can be found on the Erdős Problems site.

Links

Sharvil Kesarwani, Table of n, a(n) for n = 1..731 (first 658 terms from Chai Wah Wu)

Thomas Bloom, Problem 302, Erdős Problems.

P. Erdős and R. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique (1980).

Erdős problems database contributors, Issue #152 linking Erdős problems to the OEIS.

Husnain Raza, Python program.

Example

For n = 12, the largest subset of {1,...,12} not containing the subsets {2, 3, 6}, {3, 4, 12}, {4, 12, 6} has size 10.

Prog

(Python)
from itertools import combinations
def A390395(n):
    s, t = [], set()
    for b in range(1, n+1):
        for c in range(b+1, n+1):
            a, r = divmod(b*c, b+c)
            if not r:
                s.append({a, b, c})
                t |= {a, b, c}
    l = len(t)
    for i in range(l, -1, -1):
        for d in combinations(t, i):
            if not any(x.issubset(d) for x in s):
                return n-l+i # Chai Wah Wu, Nov 19 2025
(Python)
from pysat.examples.hitman import Hitman
def A390395(n):
    h = Hitman(solver='g42')
    for b in range(1, n+1):
        for c in range(b+1, n+1):
            a, r = divmod(b*c, b+c)
            if not r:
                h.hit([a, b, c])
    return n-len(h.get()) # Chai Wah Wu, Nov 21 2025

Crossrefs

Sequence in context: A228297 A303788 A366871 * A319288 A106744 A332613

Adjacent sequences: A390392 A390393 A390394 * A390396 A390397 A390398

Keyword

nonn

Author

Husnain Raza, Nov 04 2025

Extensions

a(40)-a(68) from Chai Wah Wu, Nov 19 2025

Status

approved