cp's OEIS Frontend

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

%I A373178 #28 Sep 05 2025 01:01:14
%S A373178 1,2,3,4,5,5,6,7,7,7,8,8,9,10,10,10,11,11,12,12,13,13,14,15,15,16,17,
%T A373178 18,19,19,20,20,20,21,21,21,22,23,23,24,25,26,27,28,29,30,31,31,31,31,
%U A373178 32,33,34,34,34,35,36,37,38,39,40,41,42,42,42,43,44,45,46,46
%N A373178 Cardinality of the largest subset of {1,...,n} such that no five distinct elements of this subset multiply to a square.
%C A373178 a(n) >= A373114(n).
%C A373178 The limiting value of a(n)/n is unknown, but (if it exists), it is strictly less than 1, and at least A246849 ~ 0.828499... (see cited paper of Tao).
%C A373178 a(n+1)-a(n) is either 0 or 1 for any n.
%C A373178 If "five" is replaced by "one", "two", "three", "four", or "odd number of", one obtains A028391, A013928, A372306, A373119, A373114 respectively.
%H A373178 Thomas Bloom, <a href="https://www.erdosproblems.com/121">Problem 121</a>, Erdős Problems.
%H A373178 Terence Tao, <a href="https://arxiv.org/abs/2405.11610">On product representations of squares</a>, arXiv:2405.11610 [math.NT], May 2024.
%H A373178 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see no. 121.
%e A373178 a(8)=7, because the set {1,2,3,4,5,7,8} has no five distinct elements multiplying to a square, but {1,2,3,4,5,6,7,8} has 1*2*3*4*6 = 12^2.
%o A373178 (Python)
%o A373178 from math import isqrt
%o A373178 def is_square(n):
%o A373178     return isqrt(n) ** 2 == n
%o A373178 def precompute_tuples(N):
%o A373178     tuples = []
%o A373178     for i in range(1, N + 1):
%o A373178         for j in range(i + 1, N + 1):
%o A373178             for k in range(j + 1, N + 1):
%o A373178                 for l in range(k + 1, N + 1):
%o A373178                     for m in range(l + 1, N + 1):
%o A373178                         if is_square(i * j * k * l * m):
%o A373178                             tuples.append((i, j, k, l, m))
%o A373178     return tuples
%o A373178 def valid_subset(A, tuples):
%o A373178     set_A = set(A)
%o A373178     for i, j, k, l, m in tuples:
%o A373178         if i in set_A and j in set_A and k in set_A and l in set_A and m in set_A:
%o A373178             return False
%o A373178     return True
%o A373178 def largest_subset_size(N, tuples):
%o A373178     from itertools import combinations
%o A373178     for size in reversed(range(1, N + 1)):
%o A373178         for subset in combinations(range(1, N + 1), size):
%o A373178             if valid_subset(subset, tuples):
%o A373178                 return size
%o A373178 for N in range(1, 26):
%o A373178     print(largest_subset_size(N, precompute_tuples(N)))
%o A373178 (Python)
%o A373178 from math import prod
%o A373178 from functools import lru_cache
%o A373178 from itertools import combinations
%o A373178 from sympy.ntheory.primetest import is_square
%o A373178 @lru_cache(maxsize=None)
%o A373178 def A373178(n):
%o A373178     if n==1: return 1
%o A373178     i = A373178(n-1)+1
%o A373178     if sum(1 for p in combinations(range(1,n),4) if is_square(n*prod(p))) > 0:
%o A373178         a = [set(p) for p in combinations(range(1,n+1),5) if is_square(prod(p))]
%o A373178         for q in combinations(range(1,n),i-1):
%o A373178             t = set(q)|{n}
%o A373178             if not any(s<=t for s in a):
%o A373178                 return i
%o A373178         else:
%o A373178             return i-1
%o A373178     else:
%o A373178         return i # _Chai Wah Wu_, May 30 2024
%Y A373178 Similar to A028391, A013928, A372306, A373119.  Lower bounded by A373114.
%K A373178 nonn,changed
%O A373178 1,2
%A A373178 _Terence Tao_, May 26 2024
%E A373178 a(26)-a(38) from _Michael S. Branicky_, May 27 2024
%E A373178 a(39)-a(47) from _Michael S. Branicky_, May 30 2024
%E A373178 a(48)-a(70) from _Martin Ehrenstein_, May 31 2024