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

Links

Martin Ehrenstein, Table of n, a(n) for n = 1..550 (terms 72..181 calculated from A360659)

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

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

Example

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

Prog

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

Crossrefs

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

Cf. A055038, A246849.

Sequence in context: A238884 A066683 A055038 * A276796 A309093 A085268

Adjacent sequences: A373111 A373112 A373113 * A373115 A373116 A373117

Keyword

nonn

Author

Terence Tao, May 25 2024

Extensions

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

Status

approved