A120511 -id:A120511 - cp's OEIS frontend

A080791 Number of nonleading 0's in binary expansion of n.

0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0, 6, 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, 5, 4, 4, 3, 4, 3, 3, 2, 4

Offset: 0

Cino Hilliard, Mar 25 2003

In this version we consider the number zero to have no nonleading 0's, thus a(0) = 0. The variant A023416 has a(0) = 1.

Number of steps required to reach 1, starting at n + 1, under the operation: if x is even divide by 2 else add 1. This is the x + 1 problem (as opposed to the 3x + 1 problem).

			a(4) = 2 since 4 in binary is 100, which has two zeros.
a(5) = 1 since 5 in binary is 101, which has only one zero.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A000120, A007814, A023416, A029837, A036987, A080791-A080801, A048881, A054429, A092339, A102364, A120511, A233271, A233272, A233273.

seq(numboccur(0, Bits[Split](n)), n=0..100); # Robert Israel, Oct 26 2017

{0}~Join~Table[Last@ DigitCount[n, 2], {n, 120}] (* Michael De Vlieger, Mar 07 2016 *)
f[n_] := If[OddQ@ n, f[n -1] -1, f[n/2] +1]; f[0] = f[1] = 0; Array[f, 105, 0] (* Robert G. Wilson v, May 21 2017 *)
Join[{0}, Table[Count[IntegerDigits[n, 2], 0], {n, 1, 100}]] (* Vincenzo Librandi, Oct 27 2017 *)

PARI
```
a(n)=if(n,a(n\2)+1-n%2)
```

A080791(n)=if(n,logint(n,2)+1-hammingweight(n)) \\ M. F. Hasler, Oct 26 2017

def a(n): return bin(n)[2:].count("0") if n>0 else 0 # Indranil Ghosh, Apr 10 2017

;; with memoizing definec-macro from Antti Karttunen's IntSeq-library)
(define (A080791 n) (- (A029837 (+ 1 n)) (A000120 n)))
;; Alternative version based on a simple recurrence:
(definec (A080791 n) (if (zero? n) 0 (+ (A080791 (- n 1)) (A007814 n) (A036987 (- n 1)) -1)))
;; from Antti Karttunen, Dec 12 2013

From Antti Karttunen, Dec 12 2013: (Start)
a(n) = A029837(n+1) - A000120(n).
a(0) = 0, and for n > 0, a(n) = (a(n-1) + A007814(n) + A036987(n-1)) - 1.
For all n >= 1, a(A054429(n)) = A048881(n-1) = A000120(n) - 1.
Equally, for all n >= 1, a(n) = A000120(A054429(n)) - 1.
(End)
Recurrence: a(2n) = a(n) + 1 (for n > 0), a(2n + 1) = a(n). - Ralf Stephan from Cino Hilliard's PARI program, Dec 16 2013. Corrected by Alonso del Arte, May 21 2017 after consultation with Chai Wah Wu and Ray Chandler, "n > 0" added by M. F. Hasler, Oct 26 2017
a(n) = A023416(n) for all n > 0. - M. F. Hasler, Oct 26 2017
G.f. g(x) satisfies g(x) = (1+x)*g(x^2) + x^2/(1-x^2). - Robert Israel, Oct 26 2017

A006949 A well-behaved cousin of the Hofstadter sequence: a(n) = a(n - 1 - a(n-1)) + a(n - 2 - a(n-2)) for n > 2 with a(0) = a(1) = a(2) = 1.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, 10, 10, 11, 12, 12, 12, 13, 14, 14, 15, 16, 16, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 20, 21, 22, 22, 23, 24, 24, 24, 24, 25, 26, 26, 27, 28, 28, 28, 29, 30, 30, 31, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 35, 36, 36

Offset: 0

N. J. A. Sloane, Jeffrey Shallit

nonn

Number of different partial sums of 1+[1,2]+[1,4]+[1,8]+[1,16]+... E.g., a(6)=3 because we have 6 = 1+1+1+1+1+1 = 1+1+4 = 1+2+1+1+1. - Jon Perry, Jan 01 2004
Ignoring first term, this is the Meta-Fibonacci sequence for s=1. - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
Comment from N. J. A. Sloane, Jul 03 2014: (Start)
The recurrence a(n) = a(n-1-a(n-1)) + a(n-2-a(n-2)) for n>2 with a(0)=X, a(1)=Y, a(2)=Z gives rise to the following sequences (cf. Higham-Tanny 1993):
  X Y Z
  3 1 0 A244483
  2 1 0 A240808
  2 1 1 A240807
  2 0 2 A244478
  1 0 2 A240808 again
  1 1 1 A006949 (this sequence).
Most other initial values do not produce a nontrivial sequence. (End)
Higham and Tanny (1993) define a family {t_k(n)} (k=0,12,...) of sequences by t_k(n) = floor(n/2) for 0 <= n < k; thereafter t_k(n) = t_k(n-1-t_k(n-1)) + t_k(n-2-t_k(n-2)). The sequence t_4(n) begins 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 8, 9, ..., which is essentially this sequence. - N. J. A. Sloane, Jul 03 2014
The values X=0 Y=1 Z=1 and X=1 Y=1 Z=2 (see above comments) also produce a sequence which is essentially this sequence. - Pablo Hueso Merino, Dec 31 2020

Jeff Higham and Stephen Tanny, More well-behaved meta-Fibonacci sequences. Proceedings of the Twenty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1993). Congr. Numer. 98(1993), 3-17.
Jeff Higham and Stephen Tanny, A tamely chaotic meta-Fibonacci sequence. Twenty-third Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1993). Congr. Numer. 99 (1994), 67-94.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..20000
Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018) Article ID 8517125.
Joseph Callaghan, John J. Chew III, and Stephen M. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM Journal on Discrete Mathematics 18.4 (2005): 794-824. See Eq. (1.4). - _N. J. A. Sloane_, Apr 16 2014
A. Das, A combinatorial approach to the Tanny sequence, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 97-108.
Jonathan H. B. Deane and Guido Gentile, A diluted version of the problem of the existence of the Hofstadter sequence, arXiv:2311.13854 [math.NT], 2023.
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
Nathaniel D. Emerson, A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.8.
Nathan Fox, Connecting Slow Solutions to Nested Recurrences with Linear Recurrent Sequences, arXiv:2203.09340 [math.CO], 2022.
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.
Warren Page (editor), Media Highlights: A well-behaved cousin of the Hofstadter sequence, The College Math. Jnl., 24 (1993), p. 105.
F. Ruskey and C. Deugau, The Combinatorics of Certain k-ary Meta-Fibonacci Sequences, JIS 12 (2009) 09.4.3.
S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discr. Math. 105 (1992), 227-239. [See Higham-Tanny 1993 for updates and corrections.]
Index entries for Hofstadter-type sequences

See also A120511. A244478, A244479, A240807, A240808, A244483 have the same recurrence but different initial conditions.

Cf. A241235 (run lengths).

a006949 n = a006949_list !! n
a006949_list = 1 : 1 : 1 : zipWith (+) xs (tail xs)
   where xs = map a006949 $ zipWith (-) [1..] $ tail a006949_list
-- Reinhard Zumkeller, Apr 17 2014

A006949 := proc(n) option remember: if n<3 then 1 else A006949(n-1-A006949(n-1))+A006949(n-2-A006949(n-2)) fi end;

a[0] = a[1] = a[2] = 1; a[n_] := a[n] = a[n - 1 - a[n - 1]] + a[n - 2 - a[n - 2]]; Table[a@ n, {n, 0, 75}] (* Michael De Vlieger, Mar 24 2017 *)

{ n=20; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]+2^(i-1))); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } \\ Jon Perry, Jan 01 2004

a(n) = a(n-1) + 0 or 1 for n > 0 and lim_{n -> infinity} a(n)/n = 1/2. - Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003
G.f.: z + z * Sum_{n >= 1} Product_{k=1..n} (z + z^(2^k)). - Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca)
For an efficient way to compute this sequence for large n, see A120511.

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Jun 27 2003

A233272 a(n) = n + 1 + number of nonleading zeros in binary representation of n (A080791).

Original entry on oeis.org

1, 2, 4, 4, 7, 7, 8, 8, 12, 12, 13, 13, 15, 15, 16, 16, 21, 21, 22, 22, 24, 24, 25, 25, 28, 28, 29, 29, 31, 31, 32, 32, 38, 38, 39, 39, 41, 41, 42, 42, 45, 45, 46, 46, 48, 48, 49, 49, 53, 53, 54, 54, 56, 56, 57, 57, 60, 60, 61, 61, 63, 63, 64, 64, 71, 71, 72

Offset: 0

Antti Karttunen, Dec 12 2013

From Antti Karttunen, Jan 30 2022: (Start)
Write n in binary: 1ab..xyz, then a(n) = (1+1ab..xy) + (1+1ab..x) + ... + (1+1ab) + (1+1a) + (1+1) + (1+0) + 1. This method was found by LODA miner, see the assembly program at C. Krause link.
Proof: Compare to a similar formula given for A011371, with a(n) = a(floor(n/2)) + floor(n/2) to the new formula for this sequence which is a(n) = 1 + a(floor(n/2)) + floor(n/2), for n > 0 and a(0) = 1. It is easy to see that the difference between these, a(n) - A011371(n) = 1+A070939(n), for n > 0. As A011371(n) = n minus (number of 1's in binary expansion of n), then a(n) = 1 + (number of digits in binary expansion of n) + (n minus number of 1's in binary expansion of n) = 1 + n + (number of nonleading 0's in binary expansion of n), which indeed is the definition of this sequence.
(End)

Antti Karttunen, Table of n, a(n) for n = 0..8192
Christian Krause, et al, A mined LODA assembly source for this sequence
Index entries for sequences related to binary expansion of n

Bisection: A233273 (A120511 + 1). Iterates: A233271, A216431.

Cf. A000120, A005187, A011371, A054429, A070939, A080791, A092391.

DigitCount[#, 2, 0] + # + 1 & [Range[0, 100]] (* Paolo Xausa, Mar 01 2024 *)

A233272(n) = { my(s=1); while(n, n>>=1; s+=(1+n)); (s); }; \\ (After a LODA-assembly program found by a miner) - Antti Karttunen, Jan 30 2022

(define (A233272 n) (+ 1 n (A080791 n)))
;; Alternatively:
(define (A233272 n) (if (zero? n) 1 (+ n (A000120 (A054429 n)))))

a(n) = n + A080791(n) + 1.
For all n>=1, a(n) = n + A000120(A054429(n)).
a(0) = 1; for n > 1, a(n) = 1 + floor(n/2) + a(floor(n/2)). - (Found by LODA miner, see comments) - Antti Karttunen, Jan 30 2022

A233273 Bisection of A233272: a(n) = A233272(2n+1).

Original entry on oeis.org

2, 4, 7, 8, 12, 13, 15, 16, 21, 22, 24, 25, 28, 29, 31, 32, 38, 39, 41, 42, 45, 46, 48, 49, 53, 54, 56, 57, 60, 61, 63, 64, 71, 72, 74, 75, 78, 79, 81, 82, 86, 87, 89, 90, 93, 94, 96, 97, 102, 103, 105, 106, 109, 110, 112, 113, 117, 118, 120, 121, 124, 125, 127

Offset: 0

Antti Karttunen, Dec 12 2013

Antti Karttunen, Table of n, a(n) for n = 0..8192

a(n) = One more than A120511(n+1).

Cf. also A233272, A005408.

DigitCount[#, 2, 0] + # + 1 & [Range[1, 200, 2]] (* Paolo Xausa, Mar 01 2024 *)

(define (A233273 n) (A233272 (A005408 n)))
;; Alternative version:
(define (A233273 n) (+ 1 (A005408 n) (A080791 n)))

a(n) = A233272(2n+1) = A233272(A005408(n)).

a(n) = A120511(n+1) + 1 = A005408(n) + A080791(n) + 1.

A241218 Smallest number m such that A240808(m) = n.

Original entry on oeis.org

2, 1, 0, 5, 10, 9, 14, 19, 15, 20, 28, 24, 23, 34, 27, 41, 37, 33, 44, 40, 36, 47, 61, 45, 53, 67, 48, 56, 70, 54, 62, 73, 57, 68, 94, 78, 71, 97, 81, 74, 100, 87, 77, 106, 90, 80, 109, 93, 86, 115, 96, 89, 121, 99, 146, 124, 105, 152, 127, 108, 155, 130

Offset: 0

Reinhard Zumkeller, Apr 17 2014

nonn

A240808(a(n)) = n and A240808(m) <> n for m < a(n).

Reinhard Zumkeller, Table of n, a(n) for n = 0..20000

Cf. A120511.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a241218 = fromJust . (`elemIndex` a240808_list)

A120522 First differences of successive meta-Fibonacci numbers A006949.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0

Offset: 1

Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca), Jun 20 2006

nonn

C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), #R26, 13 pages.

Cf. A006949, A120511.

d := n -> if n=1 then 1 else A006949(n)-A006949(n-1) fi;

d(n) = 0 if node n is an inner node, or 1 if node n is a leaf.

G.f.: z (1 + z^2 ( (1 - z^[1]) / (1 - z^[1]) + z^3 * (1 - z^(2 * [i]))/(1 - z^[1]) ( (1 - z^[2]) / (1 - z^[2]) + z^5 * (1 - z^(2 * [2]))/(1 - z^[2]) (..., where [i] = (2^i - 1).

cp's OEIS Frontend

A080791 Number of nonleading 0's in binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Scheme

Formula

A006949 A well-behaved cousin of the Hofstadter sequence: a(n) = a(n - 1 - a(n-1)) + a(n - 2 - a(n-2)) for n > 2 with a(0) = a(1) = a(2) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A233272 a(n) = n + 1 + number of nonleading zeros in binary representation of n (A080791).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Scheme

Formula

A233273 Bisection of A233272: a(n) = A233272(2n+1).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A241218 Smallest number m such that A240808(m) = n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

A120522 First differences of successive meta-Fibonacci numbers A006949.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula