OFFSET
1,2
COMMENTS
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.
Erdős problems database contributors, Erdős problem database, see no. 121.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 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)
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
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(76) from David A. Corneth, May 29 2024, May 30 2024
STATUS
approved
