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

%I #32 Mar 22 2021 05:47:23

%S 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 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 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 Number of one bits in binary representation of base i-1 expansion of n (where i = sqrt(-1)).

%C 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 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 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 David A. Corneth, <a href="/A066323/b066323.txt">Table of n, a(n) for n = 0..9999</a>

%H 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 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 a(n) = A000120(A066321(n)) = A007953(A007608(n)). - _Kevin Ryde_, Sep 09 2019

%e 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 a[n_] := Plus @@ Mod[NestWhileList[(# - Mod[#, 4])/-4 &, n, # != 0 &], 4]; Array[a, 100, 0] (* _Amiram Eldar_, Mar 22 2021 *)

%o (PARI) a(n) = my(ret=0); while(n, ret+=n%4; n\=-4); ret; \\ _Kevin Ryde_, Sep 09 2019

%Y Cf. A066321, A000120, A007608, A342728.

%K nonn,easy,base

%O 0,3

%A _Marc LeBrun_, Dec 14 2001