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

Author

Terence Tao, May 25 2024

Keywords

• nonn
• changed

Examples

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

Links

• 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.

Crossrefs

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

Cf. A055038, A246849.

Programs

PARI

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

Python

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

Python

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

Formula

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

Extensions

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