login
Number of 1's in 2's complement representation of -n.
17

%I #65 Jul 19 2024 19:11:38

%S 0,1,1,2,1,3,2,2,1,4,3,3,2,3,2,2,1,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,6,

%T 5,5,4,5,4,4,3,5,4,4,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1,7,6,6,

%U 5,6,5,5,4,6,5,5,4,5,4,4,3,6,5,5,4,5,4,4,3,5,4,4,3,4,3,3

%N Number of 1's in 2's complement representation of -n.

%C a(A127904(n)) = n and a(m) < n for m < A127904(n). - _Reinhard Zumkeller_, Feb 05 2007

%C a(n) = A000120(A010078(n)), n>0; a(n) = A023416(A004754(n-1)), n>1. - _Reinhard Zumkeller_, Dec 04 2015

%C Conjecture: a(n)+1 is the length of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - _Andrey Zabolotskiy_, Apr 17 2020

%C Terms a(n); n >= 2 can be generated recursively, as follows. Let S(0) = {1}, then for k >=1, let S(k) = {S(k-1)+1, S(k-1)}, where +1 means +1 on every term of S(k-1); see Example. Each step of the recursion gives the next 2^k terms of the sequence. - _David James Sycamore_, Jul 15 2024

%H Reinhard Zumkeller, <a href="/A008687/b008687.txt">Table of n, a(n) for n = 0..10000</a>

%H Michael Gilleland, <a href="/selfsimilar.html">Some Self-Similar Integer Sequences</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Two&#39;s_complement">Two's complement</a>

%F a(n) = A023416(n-1) + 1.

%F a(n) = if n<=1 then n else (n mod 2) + a((n mod 2) + floor(n/2)). - _Reinhard Zumkeller_, Feb 05 2007

%F a(n) = if n<2 then n else a(ceiling(n/2)) + n mod 2. - _Reinhard Zumkeller_, Jul 25 2006

%F Min{m: a(m)=n} = if n>0 then A083318(n-1) else 0. - _Reinhard Zumkeller_, Jul 25 2006

%e Using the above recursion for a(n); n >= 2, we have:

%e S(0) = {1} so a(2) = 1;

%e S(1) = {2,1} so a(3,4) = 2,1;

%e S(2) = {3,2,2,1}, so a(5,6,7,8) = 3,2,2,1;

%e As irregular table the sequence for n >= 2 begins:

%e 1;

%e 2,1;

%e 3,2,2,1;

%e 4,3,3,2,3,2,2,1;

%e 5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1;

%e 6,5,5,4,5,4,4,3,5,4,3,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1;

%e and so on (the k-th row contains 2^k terms; k>=0). - _David James Sycamore_, Jul 15 2024

%t a[0] = 0; a[1] = 1; a[n_] := a[n] = Mod[n,2] + a[Mod[n,2] + Floor[n/2]]; Array[a, 96, 0] (* _Jean-François Alcover_, Aug 12 2017, after _Reinhard Zumkeller_ *)

%o (Haskell)

%o a008687 n = a008687_list !! n

%o a008687_list = 0 : 1 : c [1] where c (e:es) = e : c (es ++ [e+1,e])

%o -- _Reinhard Zumkeller_, Mar 07 2011

%o (PARI) a(n) = if(n<2,n, n--; logint(n,2) - hammingweight(n) + 2); \\ _Kevin Ryde_, Apr 14 2021

%Y This is Guy Steele's sequence GS(4, 3) (see A135416).

%Y Cf. A000120, A004754, A010078, A023416, A290251.

%Y Cf. A007305, A007306, A061313, A088696.

%K nonn,base

%O 0,4

%A _R. H. Hardin_