login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A055941 a(n) = Sum_{j=0..k-1} (i(j) - j) where n = Sum_{j=0..k-1} 2^i(j). 8
0, 0, 1, 0, 2, 1, 2, 0, 3, 2, 3, 1, 4, 2, 3, 0, 4, 3, 4, 2, 5, 3, 4, 1, 6, 4, 5, 2, 6, 3, 4, 0, 5, 4, 5, 3, 6, 4, 5, 2, 7, 5, 6, 3, 7, 4, 5, 1, 8, 6, 7, 4, 8, 5, 6, 2, 9, 6, 7, 3, 8, 4, 5, 0, 6, 5, 6, 4, 7, 5, 6, 3, 8, 6, 7, 4, 8, 5, 6, 2, 9, 7, 8, 5, 9, 6, 7, 3, 10, 7, 8, 4, 9, 5, 6, 1, 10, 8, 9, 6, 10, 7, 8, 4 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Used to calculate number of subspaces of Zp^n where Zp is field of integers mod p.

Consider a square matrix A and call it special if (0) A is an upper triangular matrix, (1) a nonzero column of A has a 1 on the main diagonal and (2) if a row has a 1 on the main diagonal then this is the only nonzero element in that row.

If the diagonal of a special matrix is given (it can only contain 0's and 1's), many of the fields of A are determined by (0), (1) and (2). The number of fields that can be freely chosen while still satisfying (0), (1) and (2) is a(n), where n is the diagonal, read as a binary number with least significant bit at upper left.

a(n) is also the minimum number of adjacent bit swap operations required to pack all the ones of n to the right. - Philippe Beaudoin, Aug 19 2014

REFERENCES

A. Siegel, Linear Aspects of Boolean Functions, 1999 (unpublished).

LINKS

Chai Wah Wu, Table of n, a(n) for n = 0..10000

Philip Lafrance, Narad Rampersad, Randy Yee, Some properties of a Rudin-Shapiro-like sequence, arXiv:1408.2277 [math.CO] 2014 (see page 2).

FORMULA

a(n) = Sum (total number of zero-bits to the right of 1-bit) over all 1-bits of n.

a(n) = A161511(n) - A000120(n) = A161920(n+1) - 1 - A029837(n+1).

a(n) = 0 if A241816(n) = n; 1 + a(A241816(n)) otherwise. - Philippe Beaudoin, Aug 19 2014

EXAMPLE

20 = 2^4 + 2^2, thus a(20) = (2-0) + (4-1) = 5.

MATHEMATICA

b[n_] := b[n] = If[n == 0, 0, If[EvenQ[n], b[n/2] + DigitCount[n/2, 2, 1], b[(n - 1)/2] + 1]];

a[n_] := b[n] - DigitCount[n, 2, 1];

Table[a[n], {n, 0, 100}] (* Jean-Fran├žois Alcover, Sep 23 2018 *)

PROG

(GNU/MIT Scheme:) (define (A055941 n) (let loop ((n n) (ze 0) (s 0)) (cond ((zero? n) s) ((even? n) (loop (/ n 2) (1+ ze) s)) (else (loop (/ (-1+ n) 2) ze (+ s ze))))))

-- Antti Karttunen, Oct 12 2009

(PARI) a(n) = {my(b=binary(n)); nb = 0; for (i=1, #b-1, if (b[i], nb += sum(j=i+1, #b, !b[j])); ); nb; } \\ Michel Marcus, Aug 12 2014

(Python)

def A055941(n):

    s = bin(n)[2:]

    return sum(s[i:].count('0') for i, d in enumerate(s, start=1) if d == '1')

# Chai Wah Wu, Sep 07 2014

CROSSREFS

Cf. A000120, A029837, A161511, A161920, A126441.

Sequence in context: A337835 A119387 A335905 * A290537 A272569 A068076

Adjacent sequences:  A055938 A055939 A055940 * A055942 A055943 A055944

KEYWORD

nonn,base

AUTHOR

Anno Siegel (siegel(AT)zrz.tu-berlin.de), Jul 18 2000

EXTENSIONS

Edited and extended by Antti Karttunen, Oct 12 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 21 13:34 EDT 2021. Contains 343153 sequences. (Running on oeis4.)