A396253 Sum of Sum_{k=1..n} S(k) over all completely multiplicative sign sequences S of length n.

1, 2, 4, 8, 16, 16, 32, 32, 48, 48, 96, 96, 192, 192, 192, 256, 512, 512, 1024, 1024, 1024, 1024, 2048, 2048, 2560, 2560, 2560, 2560, 5120, 5120, 10240, 10240, 10240, 10240, 10240, 12288, 24576, 24576, 24576, 24576, 49152, 49152, 98304, 98304, 98304, 98304, 196608, 196608, 229376, 229376, 229376, 229376

Offset

1,2

Comments

A completely multiplicative sign sequence is a sequence S with values in {-1,+1} satisfying S(j*k) = S(j)*S(k).

Such a sequence S is completely determined by its values at the primes. Hence S(k^2) = +1 for every k, and the number of completely multiplicative sign sequences of length n is 2^A000720(n).

For fixed k, the sum of S(k) over all choices of S is 0 unless k is a square. Indeed, if k is not a square, then some prime occurs with an odd exponent in k, and changing the sign assigned to that prime pairs the choices of S with opposite values of S(k). If k is a square, then S(k) = 1 for every S. Hence a(n) = A000196(n)*2^A000720(n).

Links

Table of n, a(n) for n=1..52.

Formula

a(n) = Sum_{S} Sum_{k=1..n} S(k), where S ranges over all completely multiplicative sign sequences of length n.

a(n) = A000196(n) * 2^A000720(n).

a(n) = A000196(n) * A048656(n).

Example

For n = 5 there are 2^primepi(5) = 8 completely multiplicative sign sequences, namely +--+-, +--++, +-++-, ++-+-, +-+++, ++-++, ++++- and +++++. Hence a(5) = (-1) + 1 + 1 + 1 + 3 + 3 + 3 + 5 = 16.
On the other hand, we have A000720(5) = 3, so by the formula a(n) = A000196(n)*2^A000720(n) we get a(5) = A000196(5)*2^3 = 2*2^3 = 16.

Mathematica

a[n_Integer?NonNegative] := Floor[Sqrt[n]]*2^PrimePi[n]; Table[a[n], {n, 52}]

Crossrefs

Cf. A000196, A000720, A002819, A008836, A048656, A360659.

Sequence in context: A316749 A008381 A385285 * A083780 A368056 A309529

Adjacent sequences: A396249 A396250 A396251 * A396254 A396255 A396256

Keyword

nonn,easy

Author

Bartlomiej Pawlik, May 20 2026

Status

approved