A392164 - OEIS

%I #17 Jan 08 2026 09:28:17

%S 1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,

%T 4,4,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,

%U 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8

%N a(n) is the size of the largest subset S of {1,...,N} such that every element of S+S is squarefree.

%H Thomas Bloom, <a href="https://www.erdosproblems.com/1109">Problem #1109</a>, Erdős Problems.

%H Paul Erdős and András Sárközy, <a href="https://renyi.hu/~p_erdos/1987-13.pdf">On divisibility properties of integers of the form a+a'</a>, Acta Math. Hungar. (1987), 117--122.

%H Sergei Konyagin, <a href="https://doi.org/10.4213/im486">Problems of the set of squarefree numbers</a>, Izv. Ross. Akad. Nauk Ser. Mat. (2004), 63--90.

%F a(n) >> log(n) (Erdős and Sárközy).

%F a(n) << n^(3/4)*log(n) (Erdős and Sárközy).

%F a(n) >> log(log(n))*(log(n))^2 (Konyagin).

%F a(n) << n^(11/15+o(1)) (Konyagin).

%t a[n_]:=Length[FindClique[RelationGraph[SquareFreeQ[#1+#2]&&#1!=#2&,Select[Range[n],SquareFreeQ[2*#]&]]][[1]]]

%o (Python)

%o from itertools import combinations

%o from networkx import empty_graph, find_cliques

%o from sympy import factorint

%o def A392164(n):

%o     def is_squarefree(n): return max(factorint(n).values(),default=1)<2

%o     v = [e for e in list(range(1,n+1)) if is_squarefree(2*e)]

%o     G = empty_graph(v)

%o     G.add_edges_from((a,b) for a, b in combinations(v,2) if is_squarefree(a+b))

%o     return max(len(c) for c in find_cliques(G)) # _Chai Wah Wu_, Jan 07 2026

%Y Cf. A392165 (records).

%K nonn

%O 1,5

%A _Elijah Beregovsky_, Jan 02 2026