cp's OEIS Frontend

A027615 Number of 1's when n is written in base -2.

%I A027615 #42 Feb 16 2025 08:32:35
%S A027615 0,1,2,3,1,2,3,4,2,3,4,5,3,4,2,3,1,2,3,4,2,3,4,5,3,4,5,6,4,5,3,4,2,3,
%T A027615 4,5,3,4,5,6,4,5,6,7,5,6,4,5,3,4,5,6,4,5,3,4,2,3,4,5,3,4,2,3,1,2,3,4,
%U A027615 2,3,4,5,3,4,5,6,4,5,3,4,2
%N A027615 Number of 1's when n is written in base -2.
%C A027615 Base -2 is also called "negabinary".
%C A027615 From _Jianing Song_, Oct 18 2018: (Start)
%C A027615 Define f(n) as: f(0) = 0, f(-2*n) = f(n), f(-2*n+1) = f(n) + 1, then a(n) = f(n), n >= 0. See A320642 for the other half of f.
%C A027615 For k > 0, the earliest occurrence of k is n = A305750(k).
%C A027615 Conjecture: a(n) != A053737(n) if and only if there exists even k >= 4 such that n mod 2^k >= (5*2^(k+1) + 2)/3. If this holds, then the probability of a random chosen number n to satisfy a(n) != A053737(n) is 1/6. (End)
%D A027615 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 164.
%H A027615 Jianing Song, <a href="/A027615/b027615.txt">Table of n, a(n) for n = 0..10000</a>
%H A027615 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Negabinary.html">Negabinary</a>.
%H A027615 Wikipedia, <a href="http://en.wikipedia.org/wiki/Negative_base">Negative base</a>.
%F A027615 a(n) = 3*A072894(n+1) - 2*n - 3. Proof by Nikolaus Meyberg, following a conjecture by _Ralf Stephan_. - _R. J. Mathar_, Jan 11 2013
%F A027615 a(n) == n (mod 3). - _Jianing Song_, Oct 18 2018
%F A027615 a(n) = A000120(A005351(n)). - _Michel Marcus_, Oct 23 2018
%e A027615 A039724(7) = 11011 which has four 1's, so a(7) = 4.
%t A027615 a[n_] := a[n] = a[Quotient[n - 1, -2]] + Mod[n, 2]; a[0] = 0; Array[a, 100, 0] (* _Amiram Eldar_, Jul 23 2023 *)
%o A027615 (PARI) a(n) = if(n==0, 0, a(n\(-2))+n%2) /* _Jianing Song_, Oct 18 2018 */
%Y A027615 Cf. A000120, A005351, A039724, A053737, A072894, A305750, A320642.
%K A027615 nonn,base
%O A027615 0,3
%A A027615 _Pontus von Brömssen_, Nov 14 1997