A001855 -id:A001855 - cp's OEIS frontend

A123533 Primes in A001855.

3, 5, 11, 17, 29, 37, 41, 59, 79, 89, 109, 349, 419, 433, 461, 503, 587, 601, 643, 727, 769, 809, 857, 881, 929, 937, 953, 977, 1009, 1033, 1049, 1097, 1129, 1153, 1193, 1201, 1217, 1249, 1289, 1297, 1321, 1361, 1409, 1433, 1481, 1489, 1553, 1601, 1609

Offset: 1

Jonathan Vos Post, Nov 10 2006

Paolo Xausa, Table of n, a(n) for n = 1..10000

Intersection of A000040 and A001855.

Cf. A001768, A029837, A003071, A000337, A030190, A030308, A061168.

A001855 := proc(n) local c ; c := ceil(log[2](n)) ; n*c-2^c+1 ; end: for n from 1 to 300 do srts := A001855(n) : if isprime(srts) then printf("%d, ",srts) ; fi ; od : # R. J. Mathar, Dec 16 2006

Select[Accumulate[BitLength[Range[0, 300]]], PrimeQ] (* Paolo Xausa, Jun 28 2024 *)

Corrected and extended by R. J. Mathar, Dec 16 2006

A029837 Binary order of n: log_2(n) rounded up to next integer.

Original entry on oeis.org

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

N. J. A. Sloane

Or, ceiling(log_2(n)).
Worst-case cost of binary search.
Equal to number of binary digits in n unless n is a power of 2 when it is one less.
Thus a(n) gives the length of the binary representation of n - 1 (n >= 2), which is also A070939(n - 1).
Let x(0) = n > 1 and x(k + 1) = x(k) - floor(x(k)/2), then a(n) is the smallest integer such that x(a(n)) = 1. - Benoit Cloitre, Aug 29 2002
Also number of division steps when going from n to 1 by process of adding 1 if odd, or dividing by 2 if even. - Cino Hilliard, Mar 25 2003
Number of ways to write n as (x + 2^y), x >= 0. Number of ways to write n + 1 as 2^x + 3^y (cf. A004050). - Benoit Cloitre, Mar 29 2003
The minimum number of cuts for dividing an object into n (possibly unequal) pieces. - Karl Ove Hufthammer (karl(AT)huftis.org), Mar 29 2010
Partial sums of A209229; number of powers of 2 not greater than n. - Reinhard Zumkeller, Mar 07 2012

			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

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.

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

Cf. A000523, A070939, A000193, A000195, A004233, A113473, A053644.
Partial sums of A036987.
Used for several definitions: A029827, A036378-A036390. Partial sums: A001855.

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

[Ceiling(Log(2, n)): n in [1..100]]; // Vincenzo Librandi, Jun 14 2019

a:= n-> (p-> p+`if`(2^pAlois P. Heinz, Mar 18 2013

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 *)

{a(n) = if( n<1, 0, ceil(log(n) / log(2)))};

/* 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, ", "))

{a(n) = if( n<2, 0, exponent(n-1)+1)}; /* Michael Somos, Jul 10 2018 */

def A029837(n):
    s = bin(n)[2:]
    return len(s) - (1 if s.count('1') == 1 else 0) # Chai Wah Wu, Jul 09 2020

def A029837(n): return (n-1).bit_length() # Chai Wah Wu, Jun 30 2022

(1 to 80).map(n => Math.ceil(Math.log(n)/Math.log(2)).toInt) // Alonso del Arte, Feb 19 2020

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

Additional comments from Daniele Parisse

More terms from Michael Somos, Aug 02 2002

A030308 Triangle T(n, k): Write n in base 2, reverse order of digits, to get the n-th row.

Original entry on oeis.org

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

Offset: 0

Clark Kimberling

This is the quite common, so-called "bittest" function, see PARI code. - M. F. Hasler, Jul 21 2013
For a given number m and a digit position k the corresponding sequence index n can be calculated by n(m, k) = m*(1 + floor(log_2(m))) - 2^(1 + floor(log_2(m))) + k + 1. For example: counted from right to left, the second digit of m = 13 (binary 1101) is '0'. Hence the sequence index is n = n(13, 2) = 39. - Hieronymus Fischer, May 05 2007
A070939(n) is the length of n-th row; A000120(n) is the sum of n-th row; A030101(n) is the n-th row seen as binary number; A000035(n) = T(n, 0). - Reinhard Zumkeller, Jun 17 2012

			Triangle begins :
0
1
0, 1
1, 1
0, 0, 1
1, 0, 1
0, 1, 1
1, 1, 1
0, 0, 0, 1
1, 0, 0, 1 - _Philippe Deléham_, Oct 12 2011

Reinhard Zumkeller, Rows n = 0..1023 of triangle, flattened
Index entries for sequences related to binary expansion of n

Cf. A030190.

Cf. A030341, A030386, A031235, A030567, A031007, A031045, A031087, A031298 for the base-3 to base-10 analogs.

a030308 n k = a030308_tabf !! n !! k
a030308_row n = a030308_tabf !! n
a030308_tabf = iterate bSucc [0] where
   bSucc []       = [1]
   bSucc (0 : bs) = 1 : bs
   bSucc (1 : bs) = 0 : bSucc bs
-- Reinhard Zumkeller, Jun 17 2012

A030308_row := n -> op(convert(n,base, 2)):
seq(A030308_row(n), n=0..23); # Peter Luschny, Nov 28 2017

Flatten[Table[Reverse[IntegerDigits[n, 2]], {n, 0, 23}]] (* T. D. Noe, Oct 12 2011 *)

A030308(n,k)=bittest(n,k) \\ Assuming that columns are numbered starting with k=0, as suggested by the formula from R. Zumkeller. - M. F. Hasler, Jul 21 2013

for n in range(20): print([int(z) for z in str(bin(n)[2:])[::-1]]) # Indranil Ghosh, Mar 31 2017

A030308_row = lambda n: n.bits() if n > 0 else [0]
for n in (0..23): print(A030308_row(n)) # Peter Luschny, Nov 28 2017

(0 to 31).map(Integer.toString(, 2).reverse).mkString.split("").map(Integer.parseInt()).toList // Alonso del Arte, Feb 10 2020

a(n) = floor(m/2^(k - 1)) mod 2, where m = max(j|A001855(j) < n) and k = n - A001855(m). - Hieronymus Fischer, May 05 2007, Sep 10 2007

T(n, k) = (n // 2^k) mod 2, for 0 <= k <= log[2](n) and n > 0; T(0, 0) = 0. ('//' denotes integer division). - Peter Luschny, Apr 20 2023

Initial 0 and better name by Philippe Deléham, Oct 12 2011

A047778 Concatenation of the first n numbers in binary (converted to base 10).

Original entry on oeis.org

1, 6, 27, 220, 1765, 14126, 113015, 1808248, 28931977, 462911642, 7406586283, 118505380540, 1896086088653, 30337377418462, 485398038695407, 15532737238253040, 497047591624097297, 15905522931971113522, 508976733823075632723, 16287255482338420247156

Offset: 1

Aaron Gulliver (gulliver(AT)elec.canterbury.ac.nz)

The smallest prime in this sequence is 485398038695407. What is the full subsequence of primes? - N. J. A. Sloane, Oct 03 2015

There is only the one prime in the first 22400 terms, making a second prime > 10^91000. - Hans Havermann, Oct 07 2015

			a(4) = 1 10 11 100 [base 2] = 220 [base 10].

Joe B. Stephen, Table of n, a(n) for n = 1..400 (terms 1..250 from Reinhard Zumkeller)

Cf. A001855 (bit counts, offset by 1), A061168, A066716.

Concatenation of first n numbers in other bases: 2: this sequence, 3: A048435, 4: A048436, 5: A048437, 6: A048438, 7: A048439, 8: A048440, 9: A048441, 10: A007908, 11: A048442, 12: A048443, 13: A048444, 14: A048445, 15: A048446, 16: A048447.

a047778 = (foldl (\v d -> 2*v + d) 0) . concatMap (reverse . unfoldr
   (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2)) .
   enumFromTo 1
-- Reinhard Zumkeller, Feb 19 2012

conc:= (x,y) -> x*2^(1+ilog2(y))+y:
a[1]:= 1:
for n from 2 to 30 do a[n]:= conc(a[n-1],n) od:
seq(a[n],n=1..30); # Robert Israel, Oct 07 2015

If[STARTPOINT==1,n={},n=Flatten[IntegerDigits[Range[STARTPOINT-1],2]]]; Table[AppendTo[n,IntegerDigits[w,2]];n=Flatten[n];FromDigits[n,2],{w,STARTPOINT,ENDPOINT}] (* Dylan Hamilton, Aug 04 2010 *)
f[n_] := FromDigits[ Flatten@ IntegerDigits[ Range@n, 2], 2]; Array[f, 18] (* Robert G. Wilson v, Nov 07 2010 *)
Module[{n = 1}, NestList[#*2^BitLength[++n] + n &, 1, 25]] (* Paolo Xausa, Sep 30 2024 *)

cb(a,b)=a<<#binary(b) + b
a(n)=fold(cb, [1..n]) \\ Charles R Greathouse IV, Jun 21 2017

A047778_vec(N=20,s)=vector(N,k,s=s<M. F. Hasler, Oct 25 2019

def a(n): return int("".join([(bin(i))[2:] for i in range(1, n+1)]), 2)
print([a(n) for n in range(1, 19)]) # Michael S. Branicky, Jan 06 2021

from functools import reduce
def A047778(n): return reduce(lambda i,j:(i<Chai Wah Wu, Feb 26 2023

a(n) = a(n-1)*2^(1+floor(log_2(n))) + n. - Henry Bottomley, Jan 12 2001

a(n) = 4C / 2^frac(log_2(n)) * n^{n+1} / r(frac(log_2(n)))^n + O(1), where r(x) = 2^{x - 1 + 2^{1-x}}; frac is the fractional part function frac(x) = x - floor(x); and C is the binary Champernowne constant (A066716). (In fact, a(n) is the floor of this expression; the error term is between 1/2 and 1.) r(x) takes on values between e*log(2) and 2 for x in the range 0 to 1. It follows using Stirling's approximation that the radius of convergence for the e.g.f. is log 2. - Franklin T. Adams-Watters, Sep 07 2006

More terms from Patrick De Geest, May 15 1999

Name edited by Joe B. Stephen, Jul 22 2023

A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 14, 17, 25, 27, 30, 33, 38, 41, 45, 49, 65, 67, 70, 73, 78, 81, 85, 89, 98, 101, 105, 109, 115, 119, 124, 129, 161, 163, 166, 169, 174, 177, 181, 185, 194, 197, 201, 205, 211, 215, 220, 225, 242, 245, 249, 253, 259, 263, 268, 273, 283, 287, 292, 297, 304

Offset: 1

N. J. A. Sloane

The following sequences all appear to have the same parity: A003071, A029886, A061297, A092524, A093431, A102393, A104258, A122248, A128975. - Jeremy Gardiner, Dec 28 2008

a(A092246(n)) = A230720(n); a(A230709(n)) = A230721(n+1). - Reinhard Zumkeller, Oct 28 2013

D. E. Knuth, Art of Computer Programming, Vol. 3, Sections 5.2.4 and 5.3.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Zak Seidov, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Terrillon Jean-Christophe, Hiroyuki Iida, Reaper Tournament System, 2018.
An Vinh Nguyen Dinh, Nhien Pham Hoang Bao, Mohd Nor Akmal Khalid, Hiroyuki Iida, Simulating competitiveness and precision in a tournament structure: a reaper tournament system, Int'l J. of Information Technology (2020) Vol. 12, 1-18.
Tanya Khovanova, There are no coincidences, arXiv preprint 1410.2193 [math.CO], 2014.
Index entries for sequences related to sorting

Cf. A001855, A133457.

a003071 n = 1 - 2 ^ last es +
   sum (zipWith (*) (zipWith (+) es [0..]) (map (2 ^) es))
   where es = reverse $ a133457_row n
-- Reinhard Zumkeller, Oct 28 2013

a[1] = 0; a[n_] := a[n] = a[n-1] + 2^IntegerExponent[n-1, 2] + DigitCount[n-1, 2, 1] - 1; Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Feb 10 2012, after Henry Bottomley *)

Let n = 2^e_1 + 2^e_2 + ... + 2^e_t, e_1 > e_2 > ... > e_t >= 0, t >= 1. Then a(n) = 1 - 2^e_t + Sum_{k=1..t} (e_k + k - 1)*2^e_k [Knuth, Problem 14, Section 5.2.4].
a(n) = a(n-1) + A061338(n) = a(n-1) + A006519(n) + A000120(n) - 1 = n + A000337(A000523(n)) + a(n - 2^A000523(n)). a(2^k) = k*2^k + 1 = A002064(k). - Henry Bottomley, Apr 27 2001
G.f.: x/(1-x)^3 + 1/(1-x)^2*Sum(k>=1, (-1+(1-x)*2^(k-1))*x^2^k/(1-x^2^k)). - Ralf Stephan, Apr 17 2003

More terms from David W. Wilson

A083652 Sum of lengths of binary expansions of 0 through n.

Original entry on oeis.org

1, 2, 4, 6, 9, 12, 15, 18, 22, 26, 30, 34, 38, 42, 46, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 136, 142, 148, 154, 160, 166, 172, 178, 184, 190, 196, 202, 208, 214, 220, 226, 232, 238, 244, 250, 256, 262, 268, 274, 280, 286, 292

Offset: 0

Reinhard Zumkeller, May 01 2003

a(n) = A001855(n) + 1 for n > 0;
a(0) = A070939(0)=1, n > 0: a(n) = a(n-1) + A070939(n).
A030190(a(k))=1; A030530(a(k)) = k + 1.
Partial sums of A070939. - Hieronymus Fischer, Jun 12 2012
Young writes "If n = 2^i + k [...] the maximum is (i+1)(2^i+k)-2^{i+1}+2." - Michael Somos, Sep 25 2012

			G.f. = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 12*x^5 + 15*x^6 + 18*x^7 + 22*x^8 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36.
Alfred Young, The Maximum Order of an Irreducible Covariant of a System of Binary Forms, Proc. Roy. Soc. 72 (1903), 399-400 = The Collected Papers of Alfred Young, 1977, 136-137.
Index entries for sequences related to binary expansion of n

Cf. A000120, A007088, A023416, A059015, A070939 (base 2), A123753.

A296349 is an essentially identical sequence.

a083652 n = a083652_list !! n
a083652_list = scanl1 (+) a070939_list
-- Reinhard Zumkeller, Jul 05 2012

Accumulate[Length/@(IntegerDigits[#,2]&/@Range[0,60])] (* Harvey P. Dale, May 28 2013 *)
a[n_] := (n + 1) IntegerLength[n + 1, 2] - 2^IntegerLength[n + 1, 2] + 2;Table[a[n], {n, 0, 58}] (* Peter Luschny, Dec 02 2017 *)

{a(n) = my(i); if( n<0, 0, n++; i = length(binary(n)); n*i - 2^i + 2)}; /* Michael Somos, Sep 25 2012 */

a(n)=my(i=#binary(n++));n*i-2^i+2 \\ equivalent to the above

def A083652(n):
    s, i, z = 1, n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A083652(n) for n in range(0, 59)]) # Peter Luschny, Nov 30 2017

def A083652(n): return 2+(n+1)*(m:=(n+1).bit_length())-(1<Chai Wah Wu, Mar 01 2023

a(n) = 2 + (n+1)*ceiling(log_2(n+1)) - 2^ceiling(log_2(n+1)).
G.f.: g(x) = 1/(1-x) + (1/(1-x)^2)*Sum_{j>=0} x^2^j. - Hieronymus Fischer, Jun 12 2012; corrected by Ilya Gutkovskiy, Jan 08 2017
a(n) = A123753(n) - n. - Peter Luschny, Nov 30 2017

A061168 Partial sums of floor(log_2(k)) (= A000523(k)).

Original entry on oeis.org

0, 1, 2, 4, 6, 8, 10, 13, 16, 19, 22, 25, 28, 31, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, 94, 98, 103, 108, 113, 118, 123, 128, 133, 138, 143, 148, 153, 158, 163, 168, 173, 178, 183, 188, 193, 198, 203, 208, 213, 218, 223, 228, 233, 238, 243, 248

Offset: 1

Antti Karttunen, Apr 19 2001

Given a term b>0 of the sequence and its left hand neighbor c, the corresponding unique sequence index n with property a(n)=b can be determined by n(b)=e+(b-d*(e+1)+2*(e-1))/d, where d=b-c and e=2^d. - Hieronymus Fischer, Dec 05 2006
a(n) gives index of start of binary expansion of n in the binary Champernowne sequence A076478. - N. J. A. Sloane, Dec 14 2017
a(n) is the number of pairs in ancestor relationship (= transitive closure of the parent relationship) in all (binary) heaps on n elements. - Alois P. Heinz, Feb 13 2019

D. E. Knuth, Fundamental Algorithms, Addison-Wesley, 1973, Section 1.2.4, ex. 42(b).

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from Harry J. Smith)
Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197, ex. 27.
Sung-Hyuk Cha, On Integer Sequences Derived from Balanced k-ary Trees, Applied Mathematics in Electrical and Computer Engineering, 2012.
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75.
Alan M. Cleary, Joseph Winjum, Jordan Dood, Hiroki Shibata, and Shunsuke Inenaga, Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access, Leibniz Int'l Proc. Informatics (LIPIcs) 23rd Int'l Symp. on Experim. Algor. (SEA 2025) Art. No. 12, 12:1-12:17. See p. 12:8.
Martin Griffiths, More sums involving the floor function, Math. Gaz., 86 (2002), 285-287.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Tamás Lengyel, On the 2-Adic Valuation of Differences of Harmonic Numbers, Integers (2024) Vol. 24, A27. See p. 8.
Eric Weisstein's World of Mathematics, Heap
Wikipedia, Binary heap

Cf. A000523, A001855, A123753, A076478.

import Data.List (transpose)
a061168 n = a061168_list !! n
a061168_list = zipWith (+) [0..] (zipWith (+) hs $ tail hs) where
   hs = concat $ transpose [a001855_list, a001855_list]
-- Reinhard Zumkeller, Jun 03 2013

seq(add(floor(log[2](k)),k=1..j),j=1..100);
# second Maple program:
a:= proc(n) option remember; `if`(n<1, 0, ilog2(n)+a(n-1)) end:
seq(a(n), n=1..80);   # Alois P. Heinz, Feb 12 2019

Accumulate[Floor[Log[2,Range[110]]]] (* Harvey P. Dale, Jul 16 2012 *)
a[n_] := (n+1) IntegerLength[n+1, 2] - 2^IntegerLength[n+1, 2] - n + 1;
Table[a[n], {n, 1, 61}] (* Peter Luschny, Dec 02 2017 *)

a(n)=if(n<1,0,if(n%2==0,a(n/2)+a(n/2-1)+n-1,2*a((n-1)/2)+n-1)) /* _Ralf Stephan */

a(n)=local(k); if(n<1,0,k=length(binary(n))-1; (n+1)*k-2*(2^k-1))

{ for (n=1, 1000, k=length(binary(n))-1; write("b061168.txt", n, " ", (n + 1)*k - 2*(2^k - 1)) ) } \\ Harry J. Smith, Jul 18 2009

def A061168(n):
    s, i, z = -n , n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A061168(n) for n in range(1, 62)]) # Peter Luschny, Nov 30 2017

def A061168(n): return (n+1)*((m:=n.bit_length())-1)-(1<Chai Wah Wu, Mar 29 2023

a(n) = A001855(n+1) - n.
a(n) = Sum_{k=1..n} floor(log_2(k)) = (n+1)*floor(log_2(n)) - 2*(2^floor(log_2(n)) - 1). - Diego Torres (torresvillarroel(AT)hotmail.com), Oct 29 2002
G.f.: 1/(1-x)^2 * Sum(k>=1, x^2^k). - Ralf Stephan, Apr 13 2002
a(n) = A123753(n) - 2*n - 1. - Peter Luschny, Nov 30 2017

A003314 Binary entropy function: a(1)=0; for n > 1, a(n) = n + min { a(k)+a(n-k) : 1 <= k <= n-1 }.

Original entry on oeis.org

0, 2, 5, 8, 12, 16, 20, 24, 29, 34, 39, 44, 49, 54, 59, 64, 70, 76, 82, 88, 94, 100, 106, 112, 118, 124, 130, 136, 142, 148, 154, 160, 167, 174, 181, 188, 195, 202, 209, 216, 223, 230, 237, 244, 251, 258, 265, 272, 279, 286, 293, 300, 307, 314, 321, 328, 335

Offset: 1

N. J. A. Sloane

Morris gives many other interesting properties of this function.

a(n) is a convex function of n. (See the Morris reference.)

			a(6) = 6 + min {1+12, 2+8, 5+5} = 6 + 10 = 16.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, Sect 5.4.9, Eq. (19). p. 374.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Indranil Ghosh, Table of n, a(n) for n = 1..32768 (terms 1..1000 from T. D. Noe)
Mareike Fischer, Extremal values of the Sackin balance index for rooted binary trees, arXiv:1801.10418 [q-bio.PE], 2018.
Mareike Fischer, Extremal Values of the Sackin Tree Balance Index, Ann. Comb. (2021) Vol. 25, 515-541, Remark 4.
D. Chistikov, S. Iván, A. Lubiw, and J. Shallit, Fractional coverings, greedy coverings, and rectifier networks, arXiv preprint arXiv:1509.07588 [cs.CC], 2015-2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
D. Knuth, Letter to N. J. A. Sloane, date unknown
R. Morris, Some theorems on sorting, SIAM J. Appl. Math., 17 (1969), 1-6.

Cf. A054248, A070941, A123753.

a003314 n = a003314_list !! (n-1)
a003314_list = 0 : f [0] [2..] where
   f vs (w:ws) = y : f (y:vs) ws where
     y = w + minimum (zipWith (+) vs $ reverse vs)
-- Reinhard Zumkeller, Aug 13 2013

A003314 := proc(n) local i,j; option remember; if n<=2 then n elif n=3 then 5 else j := 10^10; for i from 1 to n-1 do if A003314(i)+A003314(n-i) < j then j := A003314(i)+A003314(n-i); fi; od; n+j; fi; end;

a[1] = 0; a[n_] := If[OddQ[n], n + a[(n-1)/2 + 1] + a[(n-1)/2], 2*(n/2 + a[n/2])];
Table[a[n], {n, 1, 57}] (* Jean-François Alcover, Oct 15 2012 *)
a[n_] := n + n IntegerLength[n, 2] - 2^IntegerLength[n, 2];
Table[a[n], {n, 1, 57}] (* Peter Luschny, Dec 02 2017 *)

PARI
```
a(n)=if(n<2,0,n+a(n\2)+a((n+1)\2))
```

a(n)=local(m);if(n<2,0,m=length(binary(n-1));n*m-2^m+n)

def A003314(n):
    return n*int(math.log(4*n,2))-2**int(math.log(2*n,2)) # Indranil Ghosh, Feb 03 2017

def A003314(n):
    s, i, z = n-1, n-1, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A003314(n) for n in range(1, 58)]) # Peter Luschny, Nov 30 2017

def A003314(n): return n*(1+(m:=(n-1).bit_length()))-(1<Chai Wah Wu, Mar 29 2023

a(1) = 0; a(n) = n + a([n/2]) + a(n-[n/2]). (See the Morris reference.)
a(n) = A001855(n)+n-1. - Michael Somos Feb 07 2004
a(n) = n + a(floor(n/2)) + a(ceiling(n/2)) = n*floor(log_2(4n))-2^floor(log_2(2n)) = A033156(n) - n = n*A070941(n) - A062383(n). - Henry Bottomley, Jul 03 2002
a(1) = 0 and for n>1: a(n) = a(n-1) + A070941(2*n-1). Also a(n) = A123753(n-1) - 1. - Reinhard Zumkeller, Oct 12 2006
a(n) = A123753(n-1) - 1. - Peter Luschny, Nov 30 2017

A058935 Concatenation of first n binary numbers.

Original entry on oeis.org

0, 1, 110, 11011, 11011100, 11011100101, 11011100101110, 11011100101110111, 110111001011101111000, 1101110010111011110001001, 11011100101110111100010011010, 110111001011101111000100110101011, 1101110010111011110001001101010111100

Offset: 0

Henry Bottomley, Jan 12 2001

If the terms are read as decimal numbers, which of them are primes? For example, a(5) = 11011100101 = 1193*9229757 is not a prime. - N. J. A. Sloane, Feb 17 2023

Answer: a(231) is the first prime term when read as a decimal number; a(15) is the first when read as a binary number. - Michael S. Branicky, Feb 17 2023

Michael S. Branicky, Table of n, a(n) for n = 0..155
Eric Weisstein's World of Mathematics, Binary Champernowne Constant
Eric Weisstein's World of Mathematics, Smarandache Number
Index entries for sequences related to Most Wanted Primes video

Cf. A047778 for this converted to decimal, A001855 (offset) for number of digits.
Cf. A066716: binary Champernowne constant, A030302: binary digits, A030190: same with initial 0, A030303: indices of 1's, A007088.
Other bases: A117640 (4), A007908 (10).

FromDigits /@ Flatten /@ Rest[FoldList[Append, {}, IntegerDigits[Range[10], 2]]] (* Eric W. Weisstein, Nov 04 2015 *)

from itertools import count, islice
def agen(s=""): yield from (int(s:=s+bin(n)[2:]) for n in count(0))
print(list(islice(agen(), 13))) # Michael S. Branicky, Feb 17 2023

from functools import reduce
def A058935(n): return int(bin(reduce(lambda i,j:(i<Chai Wah Wu, Feb 26 2023

a(n) = a(n-1)*10^A029837(n) + A007088(n).

A123753 Partial sums of A070941.

Original entry on oeis.org

1, 3, 6, 9, 13, 17, 21, 25, 30, 35, 40, 45, 50, 55, 60, 65, 71, 77, 83, 89, 95, 101, 107, 113, 119, 125, 131, 137, 143, 149, 155, 161, 168, 175, 182, 189, 196, 203, 210, 217, 224, 231, 238, 245, 252, 259, 266, 273, 280, 287, 294, 301, 308, 315, 322, 329, 336, 343

Offset: 0

Reinhard Zumkeller, Oct 12 2006

nonn

Peter Luschny, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, S. Janson and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47.

Cf. A001855, A003314, A033156, A054248, A061168, A083652, A097383, A295508.

A123753 := proc(n) local i, J, z; i := n+1: J := i; i := i-1; z := 1;
while 0 <= i do J := J+i; i := i-z; z := z+z od; J end:
seq(A123753(n), n=0..57); # Peter Luschny, Nov 30 2017
# Alternatively:
a := n -> (n+1)*(1 + ilog2(2*n+3)) - 2^ilog2(2*n+3) + 1:
seq(a(n), n=0..57); # Peter Luschny, Dec 02 2017

a[n_] := (n + 1)(1 + IntegerLength[n + 1, 2]) - 2^IntegerLength[n + 1, 2] + 1;
Table[a[n], {n, 0, 57}] (* Peter Luschny, Dec 02 2017 *)

def A123753(n):
    s, i, z = n+1, n, 1
    while 0 <= i: s += i; i -= z; z += z
    return s
print([A123753(n) for n in range(0, 58)]) # Peter Luschny, Nov 30 2017

def A123753(n): return (n+1)*(1+(m:=n.bit_length()))-(1<Chai Wah Wu, Mar 29 2023

a(n) = A003314(n+1)+1. - Reinhard Zumkeller, Oct 12 2006

Let bil(n) = floor(log_2(n)) + 1 for n>0, bil(0) = 0 and b(n) = n + n*bil(n) - 2^bil(n) + 1 then a(n) = b(n+1). (This suggests that '0' be prepended to this sequence.) - Peter Luschny, Dec 02 2017

cp's OEIS Frontend

A123533 Primes in A001855.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A029837 Binary order of n: log_2(n) rounded up to next integer.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Python

Scala

Formula

Extensions

A030308 Triangle T(n, k): Write n in base 2, reverse order of digits, to get the n-th row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Sage

Scala

Formula

Extensions

A047778 Concatenation of the first n numbers in binary (converted to base 10).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A003071 Sorting numbers: maximal number of comparisons for sorting n elements by list merging.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica