cp's OEIS Frontend

A066323 Number of one bits in binary representation of base i-1 expansion of n (where i = sqrt(-1)).

%I A066323 #32 Mar 22 2021 05:47:23
%S A066323 0,1,2,3,4,5,6,7,3,4,5,6,2,3,4,5,1,2,3,4,5,6,7,8,4,5,6,7,3,4,5,6,2,3,
%T A066323 4,5,6,7,8,9,5,6,7,8,4,5,6,7,3,4,5,6,7,8,9,10,6,7,8,9,5,6,7,8,4,5,6,7,
%U A066323 8,9,10,11,7,8,9,10,6,7,8,9,5,6,7,8,9,10,11,12,8,9,10,11,7,8,9,10,6,7,8,9
%N A066323 Number of one bits in binary representation of base i-1 expansion of n (where i = sqrt(-1)).
%C A066323 First differences are usually +1, occasionally -4 (because in base i-1 [3]+[7]=(+i)+(-i)=0) hence often a(i+j)=a(i)+a(j). Differences terms given here are period-16, but for full sequence is actually period-256 at least.
%C A066323 a(n) is the sum of the digits of n when written in base -4 using digits 0 to 3 (A007608).  This is since in Penney's digit substitution for A066321, the base -4 digits 0 to 3 become bit strings of exactly 0 to 3 many 1-bits each respectively. - _Kevin Ryde_, Sep 09 2019
%D A066323 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1969, Vol. 2, p. 172. (Also exercise 16, p. 177, answer, p. 494.)
%H A066323 David A. Corneth, <a href="/A066323/b066323.txt">Table of n, a(n) for n = 0..9999</a>
%H A066323 Walter Penney, <a href="https://www.nsa.gov/Portals/70/documents/news-features/declassified-documents/tech-journals/a-binary-system.pdf">A Binary System for Complex Numbers</a>, NSA Technical Journal, 1965.
%H A066323 Walter Penney, <a href="https://doi.org/10.1145/321264.321274">A Binary System for Complex Numbers</a>, Journal of the Association for Computing Machinery (JACM), volume 12, number 2, April 1965, pages 247-248.
%F A066323 a(n) = A000120(A066321(n)) = A007953(A007608(n)). - _Kevin Ryde_, Sep 09 2019
%e A066323 A066321(4) = 464 = 111010000 (binary) so a(4) = 4.  Or A007608(4) == 130 in base -4 and sum of digits is a(4) = 1+3+0 = 4.
%t A066323 a[n_] := Plus @@ Mod[NestWhileList[(# - Mod[#, 4])/-4 &, n, # != 0 &], 4]; Array[a, 100, 0] (* _Amiram Eldar_, Mar 22 2021 *)
%o A066323 (PARI) a(n) = my(ret=0); while(n, ret+=n%4; n\=-4); ret; \\ _Kevin Ryde_, Sep 09 2019
%Y A066323 Cf. A066321, A000120, A007608, A342728.
%K A066323 nonn,easy,base
%O A066323 0,3
%A A066323 _Marc LeBrun_, Dec 14 2001