cp's OEIS Frontend

A360659 a(n) is the minimum sum of a completely multiplicative sign sequence of length n.

%I A360659 #72 Jun 17 2024 15:31:33
%S A360659 0,1,0,-1,0,-1,0,-1,-2,-1,0,-1,-2,-3,-4,-3,-2,-3,-4,-5,-4,-5,-4,-5,-6,
%T A360659 -5,-6,-7,-8,-9,-8,-9,-8,-7,-8,-7,-6,-7,-8,-7,-8,-9,-10,-11,-12,-13,
%U A360659 -14,-15,-14,-13,-12,-13,-14,-15,-14,-13,-14,-15,-16,-17,-18,-19
%N A360659 a(n) is the minimum sum of a completely multiplicative sign sequence of length n.
%C A360659 A completely multiplicative sign sequence is a sequence S of numbers -1 and +1 such that S(a*b) = S(a)*S(b).
%C A360659 Directly from the definition, the first term of every multiplicative sign sequence is +1.
%C A360659 The number of completely multiplicative sign sequences of length n is 2^A000720(n), since every multiplicative sign sequence S is uniquely determined by the values of S on prime indexes.
%C A360659 Liouville's function A002819(n) gives the sum of the multiplicative sign sequence of length n in which every prime is assigned the value of -1. This is, therefore, an upper bound on a(n). The first difference occurs at n = 14.
%C A360659 Conjecture: For every n >= 22 there exists completely multiplicative sign sequence of length n with the minimal sum, which have +1's on initial primes and -1's on the remaining primes, i.e., its subsequence on primes is ++...+--...- for some number of +1's.
%C A360659 First differences are either 1 or -1. This is because optimum sequences for n cannot have a sum less than one less than those for n-1 and similarly optimum sequences for n cannot have a sum greater than one more than those for n-1. A zero difference is not possible because terms alternate between even and odd. - _Andrew Howroyd_, Feb 16 2023
%C A360659 Liouville's function (A002819) is unbounded below, hence this sequence is also unbounded below and every negative number occurs in the sequence. - _Rémy Sigrist_, Feb 17 2023
%C A360659 From _David A. Corneth_, May 28 2024: (Start)
%C A360659 One might ease the search by setting values with prime indices in (n/2, n] to -1 in the multiplicative function.
%C A360659 Furthermore one can use the squarefree part of n to evaluate the value of composites in the sequence. For example the value of index 60 has the same value as the one at index 15. (End)
%H A360659 David A. Corneth, <a href="/A360659/b360659.txt">Table of n, a(n) for n = 0..181</a> (terms to n = 99 from Bartlomiej Pawlik)
%F A360659 a(n) <= A002819(n).
%F A360659 Conjecture: a(n) < A002819(n) for n > 20.
%F A360659 |a(n) - a(n-1)| = 1 for n > 0. - _Andrew Howroyd_, Feb 16 2023
%F A360659 From _David A. Corneth_, May 28 2024: (Start)
%F A360659 a(k^2) = a(k^2-1) + 1 for k >= 1.
%F A360659 a(p) = a(p-1) - 1 for prime p. (End)
%e A360659 There are eight completely multiplicative sign sequences of length 5: +--+-, +--++, +-++-, +-+++, ++-+-, ++-++, ++++- and +++++. The sums of those sequences are, respectively, -1, 1, 1, 3, 1, 3, 3 and 5. Hence, the minimum sum is equal to -1 and so a(5) = -1.
%o A360659 (PARI)
%o A360659 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 A360659 a(n)={my(m=oo); for(b=0, 2^primepi(n)-1, m=min(m, vecsum(F(n,b)))); m} \\ _Andrew Howroyd_, Feb 16 2023
%o A360659 (Python)
%o A360659 from itertools import product
%o A360659 from sympy import primerange, primepi, factorint
%o A360659 def A360659(n):
%o A360659     a = dict(zip(primerange(n+1),range(c:=primepi(n))))
%o A360659     return (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))<<1)-n # _Chai Wah Wu_, May 31 2024
%Y A360659 Cf. A000720, A002819, A007913, A008836.
%K A360659 sign
%O A360659 0,9
%A A360659 _Bartlomiej Pawlik_, Feb 15 2023