login
Cardinality of the largest subset of {1,...,n} such that no three distinct elements of this subset multiply to a square.
7

%I #81 Jun 17 2024 15:31:56

%S 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,

%T 18,19,19,20,20,20,21,21,21,22,23,23,24,25,26,27,28,29,30,31,31,31,31,

%U 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

%N Cardinality of the largest subset of {1,...,n} such that no three distinct elements of this subset multiply to a square.

%C a(n) >= A373114(n).

%C a(n) ~ n (Erdős-Sárközy-Sós).

%C a(n+1)-a(n) is either 0 or 1 for any n.

%C 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.

%H P. Erdős, A. Sárközy, and V. T. Sós, <a href="https://doi.org/10.1016/0195-6698(95)90039-X">On Product Representations of Powers, I</a>, Europ. J. Combinatorics 16 (1995), 567--588.

%H David A. Corneth, <a href="/A372306/a372306.gp.txt">PARI program</a>

%F From _David A. Corneth_, May 29 2024: (Start)

%F a(k^2) = a(k^2-1) for k >= 3.

%F a(p) = a(p - 1) + 1 for prime p.

%F 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)

%e 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.

%o (Python)

%o from math import isqrt

%o def is_square(n):

%o return isqrt(n) ** 2 == n

%o def valid_subset(A):

%o length = len(A)

%o for i in range(length):

%o for j in range(i + 1, length):

%o for k in range(j + 1, length):

%o if is_square(A[i] * A[j] * A[k]):

%o return False

%o return True

%o def largest_subset_size(N):

%o from itertools import combinations

%o max_size = 0

%o for size in range(1, N + 1):

%o for subset in combinations(range(1, N + 1), size):

%o if valid_subset(subset):

%o max_size = max(max_size, size)

%o return max_size

%o for N in range(1, 11):

%o print(largest_subset_size(N))

%o (Python)

%o from math import prod

%o from functools import lru_cache

%o from itertools import combinations

%o from sympy.ntheory.primetest import is_square

%o @lru_cache(maxsize=None)

%o def A372306(n):

%o if n==1: return 1

%o i = A372306(n-1)+1

%o if sum(1 for p in combinations(range(1,n),2) if is_square(n*prod(p))) > 0:

%o a = [set(p) for p in combinations(range(1,n+1),3) if is_square(prod(p))]

%o for q in combinations(range(1,n),i-1):

%o t = set(q)|{n}

%o if not any(s<=t for s in a):

%o return i

%o else:

%o return i-1

%o else:

%o return i # _Chai Wah Wu_, May 30 2024

%o (PARI) \\ See PARI link

%Y Cf. A373114, A013928, A028391.

%K nonn,more

%O 1,2

%A _Terence Tao_, May 25 2024

%E a(18)-a(36) from _Michael S. Branicky_, May 25 2024

%E a(37)-a(38) from _Michael S. Branicky_, May 26 2024

%E a(39)-a(63) from _Martin Ehrenstein_, May 26 2024

%E a(64)-a(75) from _David A. Corneth_, May 29 2024, May 30 2024