OFFSET
1,2
COMMENTS
LINKS
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
EXAMPLE
a(8)=7, because the set {1,2,3,4,5,7,8} has no five distinct elements multiplying to a square, but {1,2,3,4,5,6,7,8} has 1*2*3*4*6 = 12^2.
PROG
(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):
if is_square(i * j * k * l * m):
tuples.append((i, j, k, l, m))
return tuples
def valid_subset(A, tuples):
set_A = set(A)
for i, j, k, l, m 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:
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 functools import lru_cache
from itertools import combinations
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A373178(n):
if n==1: return 1
i = A373178(n-1)+1
if sum(1 for p in combinations(range(1, n), 4) if is_square(n*prod(p))) > 0:
a = [set(p) for p in combinations(range(1, n+1), 5) 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
CROSSREFS
KEYWORD
nonn
AUTHOR
Terence Tao, May 26 2024
EXTENSIONS
a(26)-a(38) from Michael S. Branicky, May 27 2024
a(39)-a(47) from Michael S. Branicky, May 30 2024
a(48)-a(70) from Martin Ehrenstein, May 31 2024
STATUS
approved