cp's OEIS Frontend

A372306 Cardinality of the largest subset of {1,...,n} such that no three distinct elements of this subset multiply to a square.

%I A372306 #91 Sep 04 2025 09:31:12
%S A372306 1,2,3,4,5,5,6,6,6,7,8,8,9,10,10,10,11,11,12,12,13,13,14,15,15,16,17,
%T A372306 18,19,19,20,20,20,21,21,21,22,23,23,24,25,26,27,28,29,30,31,31,31,31,
%U A372306 32,33,34,34,34,35,36,37,38,39,40,41,42,42,42,43,44,45,46
%N A372306 Cardinality of the largest subset of {1,...,n} such that no three distinct elements of this subset multiply to a square.
%C A372306 a(n) >= A373114(n).
%C A372306 a(n) ~ n (Erdős-Sárközy-Sós).
%C A372306 a(n+1)-a(n) is either 0 or 1 for any n.
%C A372306 If "three" is replaced by "two" one obtains A013928. If "three" is replaced by "one", one obtains A028391. If "three" is replaced by "any odd", one obtains A373114.
%H A372306 Jinyuan Wang, <a href="/A372306/b372306.txt">Table of n, a(n) for n = 1..200</a>
%H A372306 Thomas Bloom, <a href="https://www.erdosproblems.com/121">Problem 121</a>, Erdős Problems.
%H A372306 David A. Corneth, <a href="/A372306/a372306.gp.txt">PARI program</a>
%H A372306 Paul Erdős, Andràs Sárközy, and Vera T. Sós, <a href="https://doi.org/10.1016/0195-6698(95)90039-X">On Product Representations of Powers, I</a>, Europ. J. Combinatorics 16 (1995), 567--588.
%H A372306 Terence Tao, <a href="https://arxiv.org/abs/2405.11610">On product representations of squares</a>, arXiv:2405.11610 [math.NT], May 2024.
%H A372306 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see no. 121.
%F A372306 From _David A. Corneth_, May 29 2024: (Start)
%F A372306 a(k^2) = a(k^2 - 1) for k >= 3.
%F A372306 a(p) = a(p - 1) + 1 for prime p. (End)
%e A372306 a(7)=6, because the set {1,2,3,4,5,7} has no three distinct elements multiplying to a square, but {1,2,3,4,5,6,7} has 2*3*6 = 6^2.
%o A372306 (Python)
%o A372306 from math import isqrt
%o A372306 def is_square(n):
%o A372306     return isqrt(n) ** 2 == n
%o A372306 def valid_subset(A):
%o A372306     length = len(A)
%o A372306     for i in range(length):
%o A372306         for j in range(i + 1, length):
%o A372306             for k in range(j + 1, length):
%o A372306                 if is_square(A[i] * A[j] * A[k]):
%o A372306                     return False
%o A372306     return True
%o A372306 def largest_subset_size(N):
%o A372306     from itertools import combinations
%o A372306     max_size = 0
%o A372306     for size in range(1, N + 1):
%o A372306         for subset in combinations(range(1, N + 1), size):
%o A372306             if valid_subset(subset):
%o A372306                 max_size = max(max_size, size)
%o A372306     return max_size
%o A372306 for N in range(1, 11):
%o A372306     print(largest_subset_size(N))
%o A372306 (Python)
%o A372306 from math import prod
%o A372306 from functools import lru_cache
%o A372306 from itertools import combinations
%o A372306 from sympy.ntheory.primetest import is_square
%o A372306 @lru_cache(maxsize=None)
%o A372306 def A372306(n):
%o A372306     if n==1: return 1
%o A372306     i = A372306(n-1)+1
%o A372306     if sum(1 for p in combinations(range(1,n),2) if is_square(n*prod(p))) > 0:
%o A372306         a = [set(p) for p in combinations(range(1,n+1),3) if is_square(prod(p))]
%o A372306         for q in combinations(range(1,n),i-1):
%o A372306             t = set(q)|{n}
%o A372306             if not any(s<=t for s in a):
%o A372306                 return i
%o A372306         else:
%o A372306             return i-1
%o A372306     else:
%o A372306         return i # _Chai Wah Wu_, May 30 2024
%o A372306 (PARI) \\ See PARI link
%Y A372306 Cf. A013928, A028391, A373114, A373119, A373178, A373195.
%K A372306 nonn,changed
%O A372306 1,2
%A A372306 _Terence Tao_, May 25 2024
%E A372306 a(18)-a(36) from _Michael S. Branicky_, May 25 2024
%E A372306 a(37)-a(38) from _Michael S. Branicky_, May 26 2024
%E A372306 a(39)-a(63) from _Martin Ehrenstein_, May 26 2024
%E A372306 a(64)-a(76) from _David A. Corneth_, May 29 2024, May 30 2024