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

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, 15, 16, 16, 17, 17, 17, 18, 18, 18, 19, 20, 20, 20, 21, 21, 22, 22, 22, 23, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 26, 27, 27, 28, 29, 29, 29, 29, 29, 30, 30, 30

Offset: 1

Author

Terence Tao, May 27 2024

Keywords

• nonn

Comments

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

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

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

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

Examples

			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.
		

Links

• P. Erdős, A. Sárközy, and V. T. Sós, On Product Representations of Powers, I, Europ. J. Combinatorics 16 (1995), 567-588.
• P. Pach and M. Vizer, Improved Lower Bounds for Multiplicative Square-Free Sequences, The Electronic Journal of Combinatorics, Volume 30, Issue 4 (2023), P4.31.
• Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.

Crossrefs

Similar to A013928, A028391, A372306, A373114, A373119, A373178.

Cf. A000720.

Programs

Python

from math import isqrt
def is_square(n):
    return isqrt(n) ** 2 == n
def precompute_tuples(N):
    tuples = []
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            for k in range(j + 1, N + 1):
                for l in range(k + 1, N + 1):
                    for m in range(l + 1, N + 1):
                        for n in range(m + 1, N + 1):
                            if is_square(i * j * k * l * m * n):
                                tuples.append((i, j, k, l, m, n))
    return tuples
def valid_subset(A, tuples):
    set_A = set(A)
    for i, j, k, l, m, n in tuples:
        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:
            return False
    return True
def largest_subset_size(N, tuples):
    from itertools import combinations
    for size in reversed(range(1, N + 1)):
        for subset in combinations(range(1, N + 1), size):
            if valid_subset(subset, tuples):
                return size
for N in range(1, 26):
    print(largest_subset_size(N, precompute_tuples(N)))

Python

from math import prod
from itertools import combinations
from functools import lru_cache
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A373195(n):
    if n==1: return 1
    i = A373195(n-1)+1
    if sum(1 for p in combinations(range(1,n),5) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),6) if is_square(prod(p))]
        for q in combinations(range(1,n),i-1):
            t = set(q)|{n}
            if not any(s<=t for s in a):
                return i
        else:
            return i-1
    else:
        return i # Chai Wah Wu, May 30 2024

Formula

From David A. Corneth, May 29 2024: (Start)

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

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

Extensions

a(26)-a(27) from Paul Muljadi, May 28 2024

a(28)-a(35) from Michael S. Branicky, May 29 2024

a(36)-a(37) from David A. Corneth, May 29 2024

a(38)-a(69) from Jinyuan Wang, Dec 30 2024