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

%I #41 May 31 2024 05:52:42

%S 1,2,3,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,12,12,13,13,13,13,13,

%T 13,14,14,15,15,15,15,16,16,17,17,17,17,18,18,19,19,19,19,20,20,20,20,

%U 20,20,21,21,22,22,22,22,23,23,24,24,24

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

%C a(n) >= A000720(n).

%C a(n) ~ n/log n (Erdős-Sárközy-Sós). Best bounds currently are due to Pach-Vizer.

%C a(n+1)-a(n) is either 0 or 1 for any n. (Is equal to 1 when n+1 is prime.)

%C If "four" is replaced by "one", "two", "three", "five", or "any odd", one obtains A028391, A013928, A372306, A373178, and A373114 respectively.

%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 P. Pach and M. Vizer, <a href="https://doi.org/10.37236/11477">Improved Lower Bounds for Multiplicative Square-Free Sequences</a>, The Electronic Journal of Combinatorics, Volume 30, Issue 4 (2023), P4.31.

%e a(7)=6, because the set {1,2,3,4,5,7} has no four distinct elements multiplying to a square, but {1,2,3,4,5,6,7} has 1*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 for l in range(k + 1, length):

%o if is_square(A[i] * A[j] * A[k] * A[l]):

%o return False

%o return True

%o def largest_subset_size(N):

%o from itertools import combinations

%o for size in reversed(range(1, N + 1)):

%o for subset in combinations(range(1, N + 1), size):

%o if valid_subset(subset):

%o return size

%o for N in range(1, 23):

%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 A373119(n):

%o if n==1: return 1

%o i = A373119(n-1)+1

%o if sum(1 for p in combinations(range(1,n),3) if is_square(n*prod(p))) > 0:

%o a = [set(p) for p in combinations(range(1,n+1),4) 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

%Y Similar to A028391, A013928, A372306, A373178, A373114. Lower bounded by A000720.

%K nonn,more

%O 1,2

%A _Terence Tao_, May 26 2024

%E a(22)-a(37) from _Michael S. Branicky_, May 26 2024

%E a(38)-a(63) from _Martin Ehrenstein_, May 27 2024