OFFSET
1,2
COMMENTS
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.
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
KEYWORD
nonn,more
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