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.

%I A373114 #79 Sep 04 2025 09:30:54
%S A373114 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,
%T A373114 19,19,20,20,20,21,21,21,22,23,23,24,25,26,27,28,29,30,31,31,31,31,32,
%U A373114 33,34,34,34,35,36,37,38,39,40,41,42,42,42,43,44,45,46,46,47
%N A373114 Cardinality of the largest subset of {1,...,n} such that no odd number of terms from this subset multiply to a square.
%H A373114 Martin Ehrenstein, <a href="/A373114/b373114.txt">Table of n, a(n) for n = 1..550</a> (terms 72..181 calculated from A360659)
%H A373114 Thomas Bloom, <a href="https://www.erdosproblems.com/121">Problem 121</a>, Erdős Problems.
%H A373114 Andrew Granville and K. Soundararajan, <a href="https://doi.org/10.2307/2661346">The spectrum of multiplicative functions</a>, Ann. Math. 153 (2001), 407-470; <a href="https://arxiv.org/abs/math/9909190">preprint</a>, arXiv:math/9909190 [math.NT], 1999.
%H A373114 Terence Tao, <a href="https://arxiv.org/abs/2405.11610">On product representations of squares</a>, arXiv:2405.11610 [math.NT], May 2024.
%H A373114 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see no. 121.
%F A373114 n-2*a(n) = A360659(n) (see Footnote 2 of the linked paper of Tao).
%F A373114 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).
%F A373114 a(n+1)-a(n) is either 0 or 1 for any n.
%F A373114 a(n) >= A055038(n).
%e A373114 For n=6, {2,3,5} is the largest set without an odd product being a square, so a(6)=3.
%o A373114 (Python)
%o A373114 import itertools
%o A373114 import sympy
%o A373114 def generate_all_completely_multiplicative_functions(primes):
%o A373114     combinations = list(itertools.product([-1, 1], repeat=len(primes)))
%o A373114     functions = []
%o A373114     for combination in combinations:
%o A373114         func = dict(zip(primes, combination))
%o A373114         functions.append(func)
%o A373114     return functions
%o A373114 def evaluate_function(f, n):
%o A373114     if n == 1:
%o A373114         return 1
%o A373114     factors = sympy.factorint(n)
%o A373114     value = 1
%o A373114     for prime, exp in factors.items():
%o A373114         value *= f[prime] ** exp
%o A373114     return value
%o A373114 def compute_minimum_sum(N: int):
%o A373114     primes = list(sympy.primerange(1, N + 1))
%o A373114     functions = generate_all_completely_multiplicative_functions(primes)
%o A373114     min_sum = float("inf")
%o A373114     for func in functions:
%o A373114         total_sum = 0
%o A373114         for n in range(1, N + 1):
%o A373114             total_sum += evaluate_function(func, n)
%o A373114         if total_sum < min_sum:
%o A373114             min_sum = total_sum
%o A373114     return min_sum
%o A373114 results = [(N - compute_minimum_sum(N)) // 2 for N in range(1, 12)]
%o A373114 print(", ".join(map(str, results)))
%o A373114 (Python)
%o A373114 from itertools import product
%o A373114 from sympy import primerange, primepi, factorint
%o A373114 def A373114(n):
%o A373114     a = dict(zip(primerange(n+1),range(c:=primepi(n))))
%o A373114     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
%o A373114 (PARI)
%o A373114 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]))}
%o A373114 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
%Y A373114 Closely related to A360659, A372306, A373119, A373178, A373195.
%Y A373114 Cf. A055038, A246849.
%K A373114 nonn,changed
%O A373114 1,3
%A A373114 _Terence Tao_, May 25 2024
%E A373114 More terms from _David A. Corneth_, May 25 2024 using b-file from A360659 and formula n-2*a(n) = A360659(n)