A296349 -id:A296349 - cp's OEIS frontend

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

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

A341766 a(n) = difference between the starting positions of the first digit of the binary representation of n, where n starts at its natural position in the string, and the second occurrence of the same string in the binary Champernowne string (starting at 0) 011011100101110111100010011010... (cf. A030190).

Original entry on oeis.org

3, 1, 4, 1, 12, 4, 5, 1, 32, 13, 2, 9, 15, 5, 6, 1, 80, 36, 12, 31, 76, 8, 23, 21, 39, 16, 69, 11, 18, 6, 7, 1, 192, 91, 38, 85, 3, 45, 20, 73, 163, 67, 2, 22, 40, 3, 45, 49, 95, 43, 139, 37, 118, 31, 3, 25, 46, 19, 137, 13, 21, 7, 8, 1, 448, 218, 100, 211, 31, 136, 79, 197, 429, 25, 58, 123

Offset: 0

Scott R. Shannon, Feb 19 2021

Consider the infinite string 011011100101110111100010011010... (cf. A030190) formed by the concatenation of all binary digits of all nonnegative numbers. From the position of the first digit of the binary representation of n, where n starts as its natural position in the string, find the number of digits one has to move forward to get to the start of the second occurrence of n. This is a(n).

			a(0) = 3 as '0' starts at position 1 and appears again at position 4.
a(1) = 1 as '1' starts at position 2 and appears again at position 3.
a(4) = 12 as '100' starts at position 7 and appears again at position 19.
a(7) = 1 as '111' starts at position 16 and appears again at position 17.
a(8) = 32 as '1000' starts at position 19 and appears again at position 51.

Michael S. Branicky, Table of n, a(n) for n = 0..16383
Scott R. Shannon, Image of the first 100000 terms.

Cf. A030190, A337227 (base 10), A296354, A296349, A296355.

def a(n):
    b = s = bin(n)[2:]
    while s.find(b, 1) < 0: n += 1; s += bin(n)[2:]
    return s.find(b, 1)
print([a(n) for n in range(76)]) # Michael S. Branicky, Sep 16 2022

From Michael S. Branicky, Sep 16 2022: (Start)
a(2^k-1) = 1, for k >= 1;
a(2^k) = (k+1)*2^k, for k >= 0. (End)

A083655 Numbers which do not appear prematurely in the binary Champernowne word (A030190).

Original entry on oeis.org

0, 1, 2, 4, 8, 10, 16, 32, 36, 64, 128, 136, 256, 512, 528, 1024, 2048, 2080, 4096, 8192, 8256, 16384, 32768, 32896, 65536, 131072, 131328, 262144, 524288, 524800, 1048576, 2097152, 2098176, 4194304, 8388608, 8390656, 16777216, 33554432

Offset: 0

Reinhard Zumkeller, May 01 2003

In other words, numbers k whose binary expansion first appears in A030190 at its expected place, i.e., n appears first starting at position A296349(n). - N. J. A. Sloane, Dec 17 2017

a(n) are the Base 2 "Punctual Bird" numbers: write the nonnegative integers, base 2, in a string 011011100101110111.... Sequence gives numbers which do not occur in the string ahead of their natural place. - Graeme McRae, Aug 11 2007

Graeme McRae, Aug 11 2007, Table of n, a(n) for n = 0..113 - Corrected by _Rémy Sigrist_, Jun 14 2020
Index entries for linear recurrences with constant coefficients, signature (0,0,6,0,0,-8).

A000079 is a subsequence.
Cf. A030190, A030304, A007088, A131881, A132131.
For the complement, the "Early Bird" numbers, see A296365.

LinearRecurrence[{0,0,6,0,0,-8},{0,1,2,4,8,10,16,32,36},50] (* Harvey P. Dale, Aug 19 2020 *)

a(n)= if (n<=2, n, my (m=n\3); if (n%3==0, 2^(2*m), n%3==1, 2^(2*m+1), 2^m + 2^(2*m+1)))  \\ Rémy Sigrist, Jun 14 2020

concat(0, Vec(x*(1 + 2*x + 4*x^2 + 2*x^3 - 2*x^4 - 8*x^5 - 8*x^6 - 8*x^7) / ((1 - 2*x^3)*(1 - 4*x^3)) + O(x^40))) \\ Colin Barker, Jun 14 2020

a(n) = 2^((2*n+1)\3) + (n%3==2)<<(n\3) - (n<3) \\ Charles R Greathouse IV, Dec 16 2022

A083653(a(n))=a(n), A083654(a(n))=1.
a(0)=0, a(1)=1, a(2)=2; then for n>=1, a(3n)=2^(2n), a(3n+1)=2^(2n+1), a(3n+2)=2^(2n+1)+2^n. - Graeme McRae, Aug 11 2007
From Colin Barker, Jun 14 2020: (Start)
G.f.: x*(1 + 2*x + 4*x^2 + 2*x^3 - 2*x^4 - 8*x^5 - 8*x^6 - 8*x^7) / ((1 - 2*x^3)*(1 - 4*x^3)).
a(n) = 6*a(n-3) - 8*a(n-6) for n>8. (End)
a(n) = 2^floor(2*(n+2)/3-1) + (floor((n+1)/3)-floor(n/3))*2^(floor(n/3)) - floor(5/(n+3)). - Alan Michael Gómez Calderón, Dec 15 2022

More terms from Graeme McRae, Aug 11 2007

cp's OEIS Frontend

A296364 a(n) = A296349(n) - A030304(n).

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Python

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A083655 Numbers which do not appear prematurely in the binary Champernowne word (A030190).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions