A363069 Size of the largest subset of {1,2,...,n} such that no two elements sum to a perfect square.

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

Offset

1,4

Links

Chai Wah Wu, Table of n, a(n) for n = 1..126

Zachary DeStefano, Maximum Sized Sets With Sums That Avoid Squares

Formula

The set: {k | k <= n, k == 1 (mod 3)} provides a lower bound: a(n) >= floor((n+2)/3).

Example

The first few examples where a(n) increases are {1}, {1,4}, {1,4,6}, and {1,4,6,7}.

Prog

(Python)
from networkx import empty_graph, find_cliques
from itertools import combinations
from sympy.ntheory.primetest import is_square
def A363069(n):
    if n == 0: return 0
    v = [d for d in range(1, n+1) if not is_square(d<<1)]
    G = empty_graph(v)
    G.add_edges_from((a, b) for a, b in combinations(v, 2) if not is_square(a+b))
    return max(len(c) for c in find_cliques(G)) # Chai Wah Wu, Jan 09 2026

Crossrefs

Cf. A100719, A210380.

Sequence in context: A297995 A081228 A270826 * A003002 A087180 A029121

Adjacent sequences: A363066 A363067 A363068 * A363070 A363071 A363072

Keyword

nonn

Author

Zachary DeStefano, May 16 2023

Status

approved