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, 46, 47, 47, 48, 49, 49, 50

Offset

1,2

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.

Links

Table of n, a(n) for n=1..76.

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.

David A. Corneth, PARI program

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.

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)

Example

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.

Prog

(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
(PARI) \\ See PARI link

Crossrefs

Cf. A373114, A013928, A028391.

Sequence in context: A293771 A005245 A061373 * A327705 A104135 A354535

Adjacent sequences: A372303 A372304 A372305 * A372307 A372308 A372309

Keyword

nonn,more,changed

Author

Terence Tao, May 25 2024

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(75) from David A. Corneth, May 29 2024, May 30 2024

Status

approved