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

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, 18, 19, 19, 20, 20, 20, 21, 21, 21, 22, 23, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 32, 33, 34, 34, 34, 35, 36, 37, 38, 39, 40, 41, 42, 42, 42, 43, 44, 45, 46

Offset: 1

Author

Terence Tao, May 25 2024

Keywords

• nonn
• changed

Comments

a(n) >= A373114(n).

a(n) ~ n (Erdős-Sárközy-Sós).

a(n+1)-a(n) is either 0 or 1 for any n.

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.

Examples

			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.
		

Links

• Jinyuan Wang, Table of n, a(n) for n = 1..200
• Thomas Bloom, Problem 121, Erdős Problems.
• David A. Corneth, PARI program
• Paul Erdős, Andràs Sárközy, and Vera T. Sós, On Product Representations of Powers, I, Europ. J. Combinatorics 16 (1995), 567--588.
• Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
• Terence Tao, Erdős problem database, see no. 121.

Crossrefs

Cf. A013928, A028391, A373114, A373119, A373178, A373195.

Programs

PARI

\\ See PARI link

Python

from math import isqrt
def is_square(n):
    return isqrt(n) ** 2 == n
def valid_subset(A):
    length = len(A)
    for i in range(length):
        for j in range(i + 1, length):
            for k in range(j + 1, length):
                if is_square(A[i] * A[j] * A[k]):
                    return False
    return True
def largest_subset_size(N):
    from itertools import combinations
    max_size = 0
    for size in range(1, N + 1):
        for subset in combinations(range(1, N + 1), size):
            if valid_subset(subset):
                max_size = max(max_size, size)
    return max_size
for N in range(1, 11):
    print(largest_subset_size(N))

Python

from math import prod
from functools import lru_cache
from itertools import combinations
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A372306(n):
    if n==1: return 1
    i = A372306(n-1)+1
    if sum(1 for p in combinations(range(1,n),2) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),3) 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(k^2) = a(k^2 - 1) for k >= 3.

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

Extensions

a(18)-a(36) from Michael S. Branicky, May 25 2024

a(37)-a(38) from Michael S. Branicky, May 26 2024

a(39)-a(63) from Martin Ehrenstein, May 26 2024

a(64)-a(76) from David A. Corneth, May 29 2024, May 30 2024