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

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, -5, -6, -7, -8, -9, -8, -9, -8, -7, -8, -7, -6, -7, -8, -7, -8, -9, -10, -11, -12, -13, -14, -15, -14, -13, -12, -13, -14, -15, -14, -13, -14, -15, -16, -17, -18, -19

Offset: 0

Author

Bartlomiej Pawlik, Feb 15 2023

Keywords

• sign

Comments

A completely multiplicative sign sequence is a sequence S of numbers -1 and +1 such that S(a*b) = S(a)*S(b).

Directly from the definition, the first term of every multiplicative sign sequence is +1.

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.

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.

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.

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

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

From David A. Corneth, May 28 2024: (Start)

One might ease the search by setting values with prime indices in (n/2, n] to -1 in the multiplicative function.

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)

Examples

			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.
		

Links

• David A. Corneth, Table of n, a(n) for n = 0..181 (terms to n = 99 from Bartlomiej Pawlik)

Crossrefs

Cf. A000720, A002819, A007913, A008836.

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)))); m} \\ Andrew Howroyd, Feb 16 2023

Python

from itertools import product
from sympy import primerange, primepi, factorint
def A360659(n):
    a = dict(zip(primerange(n+1),range(c:=primepi(n))))
    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

Formula

a(n) <= A002819(n).

Conjecture: a(n) < A002819(n) for n > 20.

|a(n) - a(n-1)| = 1 for n > 0. - Andrew Howroyd, Feb 16 2023

From David A. Corneth, May 28 2024: (Start)

a(k^2) = a(k^2-1) + 1 for k >= 1.

a(p) = a(p-1) - 1 for prime p. (End)