%I #81 Jun 17 2024 15:31:56
%S 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 18,19,19,20,20,20,21,21,21,22,23,23,24,25,26,27,28,29,30,31,31,31,31,
%U 32,33,34,34,34,35,36,37,38,39,40,41,42,42,42,43,44,45,46,46,47,47,48,49,49,50
%N Cardinality of the largest subset of {1,...,n} such that no three distinct elements of this subset multiply to a square.
%C a(n) >= A373114(n).
%C a(n) ~ n (Erdős-Sárközy-Sós).
%C a(n+1)-a(n) is either 0 or 1 for any n.
%C 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 P. Erdős, A. Sárközy, and V. 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 David A. Corneth, <a href="/A372306/a372306.gp.txt">PARI program</a>
%F From _David A. Corneth_, May 29 2024: (Start)
%F a(k^2) = a(k^2-1) for k >= 3.
%F a(p) = a(p - 1) + 1 for prime p.
%F a(s*k^2) = a(s*k^2-1) + a(3^2 * s) - a(3^2 * s-1) where s is squarefree, k >= 3 and the 3 is from the size of subset that cannot multiply to a square. (End)
%e 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 (Python)
%o from math import isqrt
%o def is_square(n):
%o return isqrt(n) ** 2 == n
%o def valid_subset(A):
%o length = len(A)
%o for i in range(length):
%o for j in range(i + 1, length):
%o for k in range(j + 1, length):
%o if is_square(A[i] * A[j] * A[k]):
%o return False
%o return True
%o def largest_subset_size(N):
%o from itertools import combinations
%o max_size = 0
%o for size in range(1, N + 1):
%o for subset in combinations(range(1, N + 1), size):
%o if valid_subset(subset):
%o max_size = max(max_size, size)
%o return max_size
%o for N in range(1, 11):
%o print(largest_subset_size(N))
%o (Python)
%o from math import prod
%o from functools import lru_cache
%o from itertools import combinations
%o from sympy.ntheory.primetest import is_square
%o @lru_cache(maxsize=None)
%o def A372306(n):
%o if n==1: return 1
%o i = A372306(n-1)+1
%o if sum(1 for p in combinations(range(1,n),2) if is_square(n*prod(p))) > 0:
%o a = [set(p) for p in combinations(range(1,n+1),3) if is_square(prod(p))]
%o for q in combinations(range(1,n),i-1):
%o t = set(q)|{n}
%o if not any(s<=t for s in a):
%o return i
%o else:
%o return i-1
%o else:
%o return i # _Chai Wah Wu_, May 30 2024
%o (PARI) \\ See PARI link
%Y Cf. A373114, A013928, A028391.
%K nonn,more
%O 1,2
%A _Terence Tao_, May 25 2024
%E a(18)-a(36) from _Michael S. Branicky_, May 25 2024
%E a(37)-a(38) from _Michael S. Branicky_, May 26 2024
%E a(39)-a(63) from _Martin Ehrenstein_, May 26 2024
%E a(64)-a(75) from _David A. Corneth_, May 29 2024, May 30 2024