login
A373178
Cardinality of the largest subset of {1,...,n} such that no five distinct elements of this subset multiply to a square.
4
1, 2, 3, 4, 5, 5, 6, 7, 7, 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
OFFSET
1,2
COMMENTS
a(n) >= A373114(n).
The limiting value of a(n)/n is unknown, but (if it exists), it is strictly less than 1, and at least A246849 ~ 0.828499... (see cited paper of Tao).
a(n+1)-a(n) is either 0 or 1 for any n.
If "five" is replaced by "one", "two", "three", "four", or "odd number of", one obtains A028391, A013928, A372306, A373119, A373114 respectively.
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
Similar to A028391, A013928, A372306, A373119. Lower bounded by A373114.
Sequence in context: A125051 A064067 A202306 * A275579 A198292 A020892
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