A029837 Binary order of n: log_2(n) rounded up to next integer.
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
Offset: 1
Examples
a(1) = 0, since log_2(1) = 0. a(2) = 1, since log_2(2) = 1. a(3) = 2, since log_2(3) = 1.58... a(n) = 7 for n = 65, 66, ..., 127, 128. G.f. = x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 3*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + ... - _Michael Somos_, Jun 02 2019
References
- R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989, p. 70.
- G. J. E. Rawlins, Compared to What? An Introduction to the Analysis of Algorithms, W. H. Freeman, 1992; see pp. 108, 118.
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
- Cino Hilliard, The x+1 conjecture [broken link]
- Lionel Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
- Eric Weisstein's World of Mathematics, Bit Length.
- Index entries for sequences related to binary expansion of n
Crossrefs
Programs
-
Haskell
a029837 n = a029837_list !! (n-1) a029837_list = scanl1 (+) a209229_list -- Reinhard Zumkeller, Mar 07 2012 (Common Lisp) (defun A029837 (n) (integer-length (1- n))) ; James Spahlinger, Oct 15 2012
-
Magma
[Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019
-
Maple
a:= n-> (p-> p+`if`(2^p
-
Mathematica
a[n_] := Ceiling[Log[2, n]]; Array[a, 105] (* Robert G. Wilson v, Dec 09 2005 *) Table[IntegerLength[n - 1, 2], {n, 1, 105}] (* Peter Luschny, Dec 02 2017 *) a[n_] := If[n < 1, 0, BitLength[n - 1]]; (* Michael Somos, Jul 10 2018 *) Join[{0}, IntegerLength[Range[130], 2]] (* Vincenzo Librandi, Jun 14 2019 *)
-
PARI
{a(n) = if( n<1, 0, ceil(log(n) / log(2)))}; -
PARI
/* Set p = 1, then: */ xpcount(n,p) = for(x=1, n, p1 = x; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1)); print1(ct, ", "))
-
PARI
{a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */ -
Python
def A029837(n): s = bin(n)[2:] return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020
-
Python
def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022
-
Scala
(1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020
Formula
a(n) = ceiling(log_2(n)).
a(1) = 0; for n > 1, a(2n) = a(n) + 1, a(2n + 1) = a(n) + 1. Alternatively, a(1) = 0; for n > 1, a(n) = a(ceiling(n/2)) + 1. [corrected by Ilya Gutkovskiy, Mar 21 2020]
a(n) = k such that n^(1/k - 1) > 2 > n^(1/k), or the least value of k for which floor n^(1/k) = 1. a(n) = k for all n such that 2^(k - 1) < n < 2^k. - Amarnath Murthy, May 06 2001
G.f.: x/(1 - x) * Sum_{k >= 0} x^2^k. - Ralf Stephan, Apr 13 2002
A062383(n-1) = 2^a(n). - Johannes W. Meijer, Jul 06 2009
a(n+1) = -Sum_{k = 1..n} mu(2*k)*floor(n/k). - Benoit Cloitre, Oct 21 2009
a(n+1) = A113473(n). - Michael Somos, Jun 02 2019
Extensions
Additional comments from Daniele Parisse
More terms from Michael Somos, Aug 02 2002
Comments