A373195 -id:A373195 - cp's OEIS frontend

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

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

Offset: 1

Terence Tao, May 25 2024

a(n) >= A373114(n).
a(n) ~ n (Erdős-Sárközy-Sós).
a(n+1)-a(n) is either 0 or 1 for any n.
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.

			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.

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.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
Terence Tao, Erdős problem database, see no. 121.

Cf. A013928, A028391, A373114, A373119, A373178, A373195.

PARI
```
\\ See PARI link
```

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

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

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)

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

A373114 Cardinality of the largest subset of {1,...,n} such that no odd number of terms from this subset multiply to a square.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9, 10, 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, 47

Offset: 1

Terence Tao, May 25 2024

			For n=6, {2,3,5} is the largest set without an odd product being a square, so a(6)=3.

Martin Ehrenstein, Table of n, a(n) for n = 1..550 (terms 72..181 calculated from A360659)
Thomas Bloom, Problem 121, Erdős Problems.
Andrew Granville and K. Soundararajan, The spectrum of multiplicative functions, Ann. Math. 153 (2001), 407-470; preprint, arXiv:math/9909190 [math.NT], 1999.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
Terence Tao, Erdős problem database, see no. 121.

Closely related to A360659, A372306, A373119, A373178, A373195.

Cf. A055038, A246849.

F(n, b)={vector(n, k, my(f=factor(k)); prod(i=1, #f~, if(bittest(b, primepi(f[i, 1])-1), 1, -1)^f[i, 2]))}
a(n)={my(m=oo); for(b=0, 2^primepi(n)-1, m=min(m, vecsum(F(n, b)))); (n-m)/2} \\ adapted from Andrew Howroyd, Feb 16 2023 at A360659 by David A. Corneth, May 25 2024

import itertools
import sympy
def generate_all_completely_multiplicative_functions(primes):
    combinations = list(itertools.product([-1, 1], repeat=len(primes)))
    functions = []
    for combination in combinations:
        func = dict(zip(primes, combination))
        functions.append(func)
    return functions
def evaluate_function(f, n):
    if n == 1:
        return 1
    factors = sympy.factorint(n)
    value = 1
    for prime, exp in factors.items():
        value *= f[prime] ** exp
    return value
def compute_minimum_sum(N: int):
    primes = list(sympy.primerange(1, N + 1))
    functions = generate_all_completely_multiplicative_functions(primes)
    min_sum = float("inf")
    for func in functions:
        total_sum = 0
        for n in range(1, N + 1):
            total_sum += evaluate_function(func, n)
        if total_sum < min_sum:
            min_sum = total_sum
    return min_sum
results = [(N - compute_minimum_sum(N)) // 2 for N in range(1, 12)]
print(", ".join(map(str, results)))

from itertools import product
from sympy import primerange, primepi, factorint
def A373114(n):
    a = dict(zip(primerange(n+1),range(c:=primepi(n))))
    return n-min(sum(sum(e for p,e in factorint(m).items() if b[a[p]])&1^1 for m in range(1,n+1)) for b in product((0,1),repeat=c)) # Chai Wah Wu, May 31 2024

n-2*a(n) = A360659(n) (see Footnote 2 of the linked paper of Tao).
Asymptotically, a(n)/n converges to log(1+sqrt(e)) - 2*Integral_{t=1..sqrt(e)} log(t)/(t+1) dt = A246849 ~ 0.828499... (essentially due to Granville and Soundararajan).
a(n+1)-a(n) is either 0 or 1 for any n.
a(n) >= A055038(n).

More terms from David A. Corneth, May 25 2024 using b-file from A360659 and formula n-2*a(n) = A360659(n)

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

Original entry on oeis.org

1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 15, 16, 16, 17, 17, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 26, 26, 26

Offset: 1

Terence Tao, May 26 2024

nonn

a(n) >= A000720(n).
a(n) ~ n/log n (Erdős-Sárközy-Sós). Best bounds currently are due to Pach-Vizer.
a(n+1)-a(n) is either 0 or 1 for any n. (Is equal to 1 when n+1 is prime.)
If "four" is replaced by "one", "two", "three", "five", or "any odd", one obtains A028391, A013928, A372306, A373178, and A373114 respectively.

			a(7)=6, because the set {1,2,3,4,5,7} has no four distinct elements multiplying to a square, but {1,2,3,4,5,6,7} has 1*2*3*6 = 6^2.

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.
P. Pach and M. Vizer, Improved Lower Bounds for Multiplicative Square-Free Sequences, The Electronic Journal of Combinatorics, Volume 30, Issue 4 (2023), P4.31.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.

Cf. A028391, A013928, A372306, A373114, A373178, A373195.

Lower bounded by A000720.

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):
                for l in range(k + 1, length):
                    if is_square(A[i] * A[j] * A[k] * A[l]):
                        return False
    return True
def largest_subset_size(N):
    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):
                return size
for N in range(1, 23):
    print(largest_subset_size(N))

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 A373119(n):
    if n==1: return 1
    i = A373119(n-1)+1
    if sum(1 for p in combinations(range(1,n),3) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),4) 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

a(22)-a(37) from Michael S. Branicky, May 26 2024
a(38)-a(63) from Martin Ehrenstein, May 27 2024
a(64)-a(69) from Jinyuan Wang, Dec 30 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Python

Formula

Extensions

A373114 Cardinality of the largest subset of {1,...,n} such that no odd number of terms from this subset multiply to a square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Extensions