A390394 a(n) is the maximum size of a subset A of {1,...,n} such that there are no solutions to 1/a = 1/b_1 + ... + 1/b_k with distinct a, b_1, ..., b_k in A.

1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 10, 11, 12, 12, 13, 14, 15, 16, 16, 17, 18, 19, 19, 20, 21, 22, 22, 23, 23, 24, 25, 26, 27, 27, 27, 28, 29

Offset

1,2

Comments

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

Links

Table of n, a(n) for n=1..38.

Thomas Bloom, Problem 301, 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 = 6, A cannot contain the set {2,3,6} as 1/2 = 1/3 + 1/6 or {1,2,3,6} as 1/1 = 1/2 + 1/3 + 1/6.

Prog

(Python)
from math import prod
from itertools import combinations
def A390394(n):
    s, t = [], set()
    for l in range(2, n):
        for p in combinations(range(1, n+1), r=l):
            m = prod(p)
            a, r = divmod(m, sum(m//d for d in p))
            if not r:
                s.append(c:=set([a]+list(p)))
                t |= 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 23 2025

Crossrefs

Cf. A390393, A390395.

Sequence in context: A331268 A391592 A384927 * A053757 A256562 A228297

Adjacent sequences: A390391 A390392 A390393 * A390395 A390396 A390397

Keyword

nonn,hard,more

Author

Husnain Raza, Nov 04 2025

Extensions

a(1)-a(5) corrected by and a(30)-a(33) from Chai Wah Wu, Nov 23 2025

a(34)-a(38) from Chai Wah Wu, Dec 07 2025

Status

approved