A372306 -id:A372306 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

Terence Tao, May 26 2024

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.

			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.

Thomas Bloom, Problem 121, Erdős Problems.
Terence Tao, On product representations of squares, arXiv:2405.11610 [math.NT], May 2024.
Terence Tao, Erdős problem database, see no. 121.

Similar to A028391, A013928, A372306, A373119. Lower bounded by A373114.

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

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

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

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

Original entry on oeis.org

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

Offset: 1

Terence Tao, May 27 2024

nonn

a(n) >= A000720(n) + A000720(n/2).
a(n) ~ 3n/2log 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 "six" is replaced by "one", "two", "three", "four", "five", or "any odd", one obtains A028391, A013928, A372306, A373119, A373178, and A373114 respectively.

			a(9)=8, because {1,2,3,4,5,7,8,9} does not contain six distinct elements that multiply to a square, but {1,2,3,4,5,6,7,8,9} has 1*2*3*4*6*9 = 36^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.

Similar to A013928, A028391, A372306, A373114, A373119, A373178.

Cf. A000720.

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):
                        for n in range(m + 1, N + 1):
                            if is_square(i * j * k * l * m * n):
                                tuples.append((i, j, k, l, m, n))
    return tuples
def valid_subset(A, tuples):
    set_A = set(A)
    for i, j, k, l, m, n 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 and n 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)))

from math import prod
from itertools import combinations
from functools import lru_cache
from sympy.ntheory.primetest import is_square
@lru_cache(maxsize=None)
def A373195(n):
    if n==1: return 1
    i = A373195(n-1)+1
    if sum(1 for p in combinations(range(1,n),5) if is_square(n*prod(p))) > 0:
        a = [set(p) for p in combinations(range(1,n+1),6) 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(p) = a(p-1) + 1 for prime p.
a(k^2) = a(k^2 - 1) for k >= 3. (End)

a(26)-a(27) from Paul Muljadi, May 28 2024
a(28)-a(35) from Michael S. Branicky, May 29 2024
a(36)-a(37) from David A. Corneth, May 29 2024
a(38)-a(69) from Jinyuan Wang, Dec 30 2024

A373042 a(n) is the number of 3-element subsets {x,y,z} of {1,...,n} such that xyz is a square.

Original entry on oeis.org

0, 0, 0, 1, 1, 4, 6, 8, 8, 13, 13, 15, 18, 23, 23, 35, 35, 44, 47, 50, 50, 62, 74, 77, 96, 107, 107, 117, 117, 145, 150, 154, 160, 182, 182, 186, 191, 211, 211, 223, 223, 236, 263, 267, 267, 304, 338, 390, 396, 412, 412, 457, 466, 492, 499, 504, 504, 536, 536, 541, 575

Offset: 3

Hugo Pfoertner, May 25 2024

nonn

			a(6) = a(7) = 1: 2*3*6 = 36.
a(8) = 4: 1*2*8 = 16, 2*3*6 = 36, 2*4*8 = 64, 3*6*8 = 144.

Hugo Pfoertner, Table of n, a(n) for n = 3..2000

Cf. A372306, A373043.

a(n) = my(k=0); forsubset([n,3], s, if(issquare(vecprod(Vec(s))), k++)); k

from math import prod
from itertools import combinations
from sympy.ntheory.primetest import is_square
def A373042(n): return sum(1 for p in combinations(range(1,n+1),3) if is_square(prod(p))) # Chai Wah Wu, May 30 2024

A373043 a(n) is the number of products P = jkn, 1 < j < k < n, such that P is a square.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 2, 0, 4, 0, 2, 3, 3, 0, 10, 0, 8, 3, 3, 0, 11, 9, 3, 17, 10, 0, 10, 0, 25, 5, 4, 6, 18, 0, 4, 5, 19, 0, 12, 0, 12, 25, 4, 0, 34, 29, 48, 6, 15, 0, 43, 9, 25, 7, 5, 0, 31, 0, 5, 32, 45, 10, 16, 0, 16, 7, 20, 0, 74, 0, 6, 68, 18, 11, 18, 0, 55, 65, 6, 0

Offset: 4

Hugo Pfoertner, May 27 2024

nonn

			a(6) = 1: 2*3*6 = 6^2;
a(8) = 2: 2*4*8 = 8^2, 3*6*8 = 12^2;
a(9) = 1: 2*8*9 = 12^2;
a(10) = 2: 2*5*10 = 10^2, 5*8*10 = 20^2.

David A. Corneth, Table of n, a(n) for n = 4..10000 (terms to n = 2000 from Hugo Pfoertner)

Cf. A007913, A372306, A373042.

Cf. A057918 (see 1st comment there).

a(n) = my(s=0); for(j=2, n-2, for(k=j+1, n-1, if(issquare(j*k*n), s++))); s

a(n) = {
	my(f = factor(n), c = core(f), res = (issquare(n) && n > 1), u, s);
	u = sqrtint((n-1)\c);
	for(i = 1, u, 	
		res+=(numdiv(c*i^2)\2);
	);
	res-=u;
	for(i = u+1, sqrtint((n^2 - 1)\c),
		d = divisors(c*i^2);
		s = select(x->x>=n, d);
		res+=((#d - 2*#s)>>1)
	);
	res
} \\ David A. Corneth, May 27 2024

from sympy.ntheory.primetest import is_square
def A373043(n): return sum(1 for k in range(3,n) for j in range(2,k) if is_square(j*k*n)) # Chai Wah Wu, May 31 2024

a(n) = 0 for prime n. a(n) > 0 for composite n > 4. Proof: If n is square, then m = i*j*n = 2*8*n = 16*n is square and a(n) > 0. If n is a nonsquare composite, then we can write it as n = j*k where 1 < j < k < n and so j*k*n = j*k*j*k = (j*k)^2 is a square and a(n) > 0 as well. - David A. Corneth, May 27 2024

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Python

Formula

Extensions

A373042 a(n) is the number of 3-element subsets {x,y,z} of {1,...,n} such that x*y*z is a square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

A373043 a(n) is the number of products P = j*k*n, 1 < j < k < n, such that P is a square.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Python

Formula

A373042 a(n) is the number of 3-element subsets {x,y,z} of {1,...,n} such that xyz is a square.

A373043 a(n) is the number of products P = jkn, 1 < j < k < n, such that P is a square.