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