cp's OEIS Frontend

A055941 a(n) = Sum_{j=0..k-1} (i(j) - j) where n = Sum_{j=0..k-1} 2^i(j).

%I A055941 #67 Dec 13 2023 14:45:35
%S A055941 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,
%T A055941 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,
%U A055941 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
%N A055941 a(n) = Sum_{j=0..k-1} (i(j) - j) where n = Sum_{j=0..k-1} 2^i(j).
%C A055941 Used to calculate number of subspaces of Zp^n where Zp is field of integers mod p.
%C A055941 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.
%C A055941 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.
%C A055941 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
%C A055941 From _Rakesh Khanna A_, Aug 06 2021: (Start)
%C A055941 a(n) is also the area under the curve formed from the binary representation of n where each 0-bit corresponds to an increase of one unit along the x-axis and each 1-bit corresponds to an increase of one unit along the y-axis.
%C A055941 E.g., n = 20 = 10100_2 and the area under the curve shown below is a(n) = 5.
%C A055941   1   0  1   0    0
%C A055941    \   \  \   \    \  |
%C A055941     \   \  \+----+----+
%C A055941      \   \  |         |
%C A055941       \+----+         +
%C A055941        |              |
%C A055941    ----+----+----+----+
%C A055941 (End)
%D A055941 A. Siegel, Linear Aspects of Boolean Functions, 1999 (unpublished).
%H A055941 Chai Wah Wu, <a href="/A055941/b055941.txt">Table of n, a(n) for n = 0..10000</a>
%H A055941 Philip Lafrance, Narad Rampersad and Randy Yee, <a href="http://arxiv.org/abs/1408.2277">Some properties of a Rudin-Shapiro-like sequence</a>, arXiv:1408.2277 [math.CO], 2014 (see page 2).
%F A055941 a(n) = Sum (total number of 0-bits to the right of 1-bit) over all 1-bits of n.
%F A055941 a(n) = A161511(n) - A000120(n) = A161920(n+1) - 1 - A029837(n+1).
%F A055941 a(n) = 0 if A241816(n) = n; 1 + a(A241816(n)) otherwise. - _Philippe Beaudoin_, Aug 19 2014
%e A055941 20 = 2^4 + 2^2, thus a(20) = (2-0) + (4-1) = 5.
%t A055941 b[n_] := b[n] = If[n == 0, 0, If[EvenQ[n], b[n/2] + DigitCount[n/2, 2, 1], b[(n - 1)/2] + 1]];
%t A055941 a[n_] := b[n] - DigitCount[n, 2, 1];
%t A055941 Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Sep 23 2018 *)
%o A055941 (MIT/GNU 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))))))
%o A055941 ;; _Antti Karttunen_, Oct 12 2009
%o A055941 (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
%o A055941 (Python)
%o A055941 def A055941(n):
%o A055941     s = bin(n)[2:]
%o A055941     return sum(s[i:].count('0') for i,d in enumerate(s,start=1) if d == '1')
%o A055941 # _Chai Wah Wu_, Sep 07 2014
%Y A055941 Cf. A000120, A029837, A161511, A161920, A126441.
%K A055941 nonn,base
%O A055941 0,5
%A A055941 Anno Siegel (siegel(AT)zrz.tu-berlin.de), Jul 18 2000
%E A055941 Edited and extended by _Antti Karttunen_, Oct 12 2009