A373195 - OEIS

%I #31 Jan 13 2025 09:36:53

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

%T 15,16,16,17,17,17,18,18,18,19,20,20,20,21,21,22,22,22,23,24,24,24,24,

%U 24,24,25,25,25,25,25,26,27,27,28,29,29,29,29,29,30,30,30

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

%C a(n) >= A000720(n) + A000720(n/2).

%C a(n) ~ 3n/2log 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 "six" is replaced by "one", "two", "three", "four", "five", or "any odd", one obtains A028391, A013928, A372306, A373119, 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.

%H Terence Tao, <a href="https://arxiv.org/abs/2405.11610">On product representations of squares</a>, arXiv:2405.11610 [math.NT], May 2024.

%F From _David A. Corneth_, May 29 2024: (Start)

%F a(p) = a(p-1) + 1 for prime p.

%F a(k^2) = a(k^2 - 1) for k >= 3. (End)

%e a(9)=8, because {1,2,3,4,5,7,8,9} does not contain six distinct elements that multiply to a square, but {1,2,3,4,5,6,7,8,9} has 1*2*3*4*6*9 = 36^2.

%o (Python)

%o from math import isqrt

%o def is_square(n):

%o     return isqrt(n) ** 2 == n

%o def precompute_tuples(N):

%o     tuples = []

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

%o         for j in range(i + 1, N + 1):

%o             for k in range(j + 1, N + 1):

%o                 for l in range(k + 1, N + 1):

%o                     for m in range(l + 1, N + 1):

%o                         for n in range(m + 1, N + 1):

%o                             if is_square(i * j * k * l * m * n):

%o                                 tuples.append((i, j, k, l, m, n))

%o     return tuples

%o def valid_subset(A, tuples):

%o     set_A = set(A)

%o     for i, j, k, l, m, n in tuples:

%o         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 and n in set_A:

%o             return False

%o     return True

%o def largest_subset_size(N, tuples):

%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, tuples):

%o                 return size

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

%o     print(largest_subset_size(N, precompute_tuples(N)))

%o (Python)

%o from math import prod

%o from itertools import combinations

%o from functools import lru_cache

%o from sympy.ntheory.primetest import is_square

%o @lru_cache(maxsize=None)

%o def A373195(n):

%o     if n==1: return 1

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

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

%o         a = [set(p) for p in combinations(range(1,n+1),6) 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 A013928, A028391, A372306, A373114, A373119, A373178.

%Y Cf. A000720.

%K nonn

%O 1,2

%A _Terence Tao_, May 27 2024

%E a(26)-a(27) from _Paul Muljadi_, May 28 2024

%E a(28)-a(35) from _Michael S. Branicky_, May 29 2024

%E a(36)-a(37) from _David A. Corneth_, May 29 2024

%E a(38)-a(69) from _Jinyuan Wang_, Dec 30 2024