A182512 -id:A182512 - cp's OEIS frontend

A043291 Every run length in base 2 is 2.

3, 12, 51, 204, 819, 3276, 13107, 52428, 209715, 838860, 3355443, 13421772, 53687091, 214748364, 858993459, 3435973836, 13743895347, 54975581388, 219902325555, 879609302220, 3518437208883, 14073748835532, 56294995342131, 225179981368524, 900719925474099

Offset: 1

Clark Kimberling

a(n) is the number whose binary representation is A153435(n). - Omar E. Pol, Jan 18 2009

See A033001 and following for the analog in other bases and the variant with runs of length >= 2. - M. F. Hasler, Feb 01 2014

Vincenzo Librandi, Table of n, a(n) for n = 1..500
Index entries for linear recurrences with constant coefficients, signature (4,1,-4).

Cf. A153435 (binary).
Bisections: A108020, A182512. Bisection of A077854.
Cf. A000975, A033001, A033114.

[Floor(4^(n+1)/5): n in [1..30]]; // Vincenzo Librandi, Jun 26 2011

seq(floor(4^(n+1)/5),n=1..25); # Mircea Merca, Dec 26 2010

f[n_] := Floor[4^(n + 1)/5]; Array[f, 23] (* or *)
a[1] = 3; a[2] = 12; a[3] = 51; a[n_] := a[n] = 4 a[n - 1] + a[n - 2] - 4 a[n - 3]; Array[a, 23] (* or *)
3 LinearRecurrence[{4, 1, -4}, {1, 4, 17}, 23] (* Robert G. Wilson v, Jul 01 2014 *)

A043291 = n->4^(n+1)\5 \\ M. F. Hasler, Feb 01 2014

def a(n): return int(''.join([['11', '00'][i%2] for i in range(n)]), 2)
print([a(n) for n in range(1, 26)]) # Michael S. Branicky, Mar 12 2021

a(n) = 4*a(n-1)+a(n-2)-4*a(n-3), n>3. - John W. Layman, Feb 01 2000
a(n) = floor(4^(n+1)/5). - Mircea Merca, Dec 26 2010
G.f.: 3*x / ( (x-1)*(4*x-1)*(1+x) ). - Joerg Arndt, Jan 08 2011
a(n) = 3*A033114(n). - R. J. Mathar, Jan 08 2011

A175046 Write n in binary, then increase each run of 0's by one 0, and increase each run of 1's by one 1. a(n) is the decimal equivalent of the result.

Original entry on oeis.org

3, 12, 7, 24, 51, 28, 15, 48, 99, 204, 103, 56, 115, 60, 31, 96, 195, 396, 199, 408, 819, 412, 207, 112, 227, 460, 231, 120, 243, 124, 63, 192, 387, 780, 391, 792, 1587, 796, 399, 816, 1635, 3276, 1639, 824, 1651, 828, 415, 224, 451, 908, 455, 920, 1843, 924

Offset: 1

Leroy Quet, Dec 02 2009

A318921 expands the runs in a similar way, and A318921(a(n)) = A001477(n). - Andrew Weimholt, Sep 08 2018
From Chai Wah Wu, Nov 18 2018: (Start)
Let f(k) = Sum_{i=2^k..2^(k+1)-1} a(i), i.e., the sum ranges over all numbers with a (k+1)-bit binary expansion. Thus f(0) = a(1) = 3 and f(1) = a(2) + a(3) = 19.
Then f(k) = 20*6^(k-1) - 2^(k-1) for k > 0.
Proof: by summing over the recurrence relations for a(n) (see formula section), we get f(k+2) = Sum_{i=2^k..2^(k+1)-1} (f(4i) + f(4i+1) + f(4i+2) + f(4i+3)) = Sum_{i=2^k..2^(k+1)-1} (6*a(2i) + 6*a(2i+1) + 4) = 6*f(k+1) + 2^(k+2). Solving this first-order recurrence relation with the initial condition f(1) = 19 shows that f(k) = 20*6^(k-1)-2^(k-1) for k > 0.
(End)

			6 in binary is 110. Increase each run by one digit to get 11100, which is 28 in decimal. So a(6) = 28.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.

Cf. A175047, A175048, A324127 (partial sums).
Cf. also A030308, A007088, A182512, A318921.
For records see A319422, A319423, A319424.

import Data.List (group)
a175046 = foldr (\b v -> 2 * v + b) 0 .
          concatMap (\bs@(b:_) -> b : bs) . group . a030308_row
-- Reinhard Zumkeller, Jul 05 2013

a[n_] := (Append[#, #[[1]]]& /@ Split[IntegerDigits[n, 2]]) // Flatten // FromDigits[#, 2]&;
Array[a, 60] (* Jean-François Alcover, Nov 12 2018 *)

A175046(n)={for(i=2,#n=binary (n*2+bittest (n,0)),n[i]!=n[i-1]&&n[i-1]*=[1,1]);fromdigits(concat(n),2)} \\ M. F. Hasler, Sep 08 2018

from re import split
def A175046(n):
    return int(''.join(d+'1' if '1' in d else d+'0' for d in split('(0+)|(1+)',bin(n)[2:]) if d != '' and d != None),2) # Chai Wah Wu, Sep 24 2018

def a(n):
    b = bin(n)[2:]
    return int(b.replace("01", "001").replace("10", "110") + b[-1], 2)
print([a(n) for n in range(1, 55)]) # Michael S. Branicky, Dec 07 2021

2n+1 <= a(n) < 2*(n+1/n)^2; a(n) mod 4 = 3*(n mod 2). - M. F. Hasler, Sep 08 2018
a(n) <= (9*n^2 + 12*n)/5, with equality iff n = (2/3)*(4^k-1) = A182512(k) for some k, i.e., n = 10101...10 in binary. - Conjectured by N. J. A. Sloane, Sep 09 2018, proved by M. F. Hasler, Sep 12 2018
From M. F. Hasler, Sep 12 2018: (Start)
Proof of N. J. A. Sloane's formula: For given (binary) length L(n) = floor(log_2(n)+1), the length of a(n) is maximal, L(a(n)) = 2*L(n), if and only if n's bits are alternating, i.e., n in A020988 (if even) or in A002450 (if odd).
For n = A020988(k) (= k times '10' in base 2) = (4^k - 1)*2/3, one has a(n) = A108020(k) (= k times '1100' in base 2) = (16^k - 1)*4/5. This yields a(n)/n = (4^k + 1)*6/5 = (n*9 + 12)/5, i.e., the given upper bound.
For n = A002450(k) = (4^k - 1)/3, one gets a(n) = A182512(k) = (16^k - 1)/5, whence a(n)/n = (4^k + 1)*3/5 = (n*9 + 6)/5, smaller than the bound.
If L(a(n)) < 2 L(n) - 1, then log_2(a(n)) < floor(log_2(a(n))+1) = L(a(n)) <= 2*L(n) - 2 = 2*floor(log_2(n)+1)-2 = 2*floor(log_2(n)) <= 2*log_2(n), whence a(n) < n^2.
It remains to consider the case L(a(n)) = 2 L(n) - 1. There are two possibilities:
If n = 10..._2, then n >= 2^(L(n)-1) and a(n) = 1100..._2 < 1101_2 * 2^(L(a(n))-4) = 13*2^(2*L(n)-5), so a(n)/n^2 < 13*2^(-5+2) = 13/8 = 1.625 < 9/5 = 1.8.
If n = 11..._2, then n >= 3*2^(L(n)-2) and a(n) = 111..._2 < 2^L(a(n)) = 2^(2*L(n)-1), so a(n)/n^2 < 2^(-1+4)/9 = 8/9 < 1 < 9/5.
This shows that a(n)/n^2 <= 9/5 + 12/(5*n) always holds, with equality iff n is in A020988; and a(n)/n^2 < 13/8 if n is not in A020988 or A002450. (End)
From M. F. Hasler, Sep 10 2018: (Start)
Right inverse of A318921: A318921 o A175046 = id (= A001477).
a(A020988(k)) = A108020(k); a(A002450(k)) = A182512(k); a(A000225(k)) = A000225(k+1) (achieves the lower bound a(n) >= 2n + 1) for all k >= 0. (End)
From David A. Corneth, Sep 20 2018: (Start)
a(4*k)   = 2*a(2*k).
a(4*k+1) = 4*a(2*k) + 3.
a(4*k+2) = 4*a(2*k+1).
a(4*k+3) = 2*a(2*k+1) + 1. (End)

Extended by Ray Chandler, Dec 18 2009

A112627 Decimal equivalent of number defined by last k bits of the infinite binary string ...0011001100110011 (numbers with leading zeros omitted).

Original entry on oeis.org

1, 3, 19, 51, 307, 819, 4915, 13107, 78643, 209715, 1258291, 3355443, 20132659, 53687091, 322122547, 858993459, 5153960755, 13743895347, 82463372083, 219902325555, 1319413953331, 3518437208883, 21110623253299, 56294995342131, 337769972052787, 900719925474099

Offset: 1

N. J. A. Sloane, based on email from Artur Jasinski, with assistance from Dean Hickerson, Ray Chandler and Robert G. Wilson v, Dec 27 2005

A182512 is a bisection. - Olena Kachko, Dec 16 2023

			1 = 1
11 = 3
10011 = 19
110011 = 51
100110011 = 307
1100110011 = 819
...

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (1,16,-16).

Cf. A182512.

seq(4^(n-1) - (4 + (-4)^n)/20, n=1..100); # Robert Israel, Sep 02 2014

t = {}; lst = First@RealDigits[ N[1/5, 100], 2]; Do[ If[ lst[[n]] == 1, AppendTo[t, FromDigits[ Reverse@Take[lst, n], 2]]], {n, 49}]; t
(* The first line establishes the binary expansion of 1/5 to 100 places (A021913, except for start). The loop extracts the first n terms in this sequence and if it ends in "1", reverses digits and converts to decimal. *)
Table[FromDigits[PadLeft[{},n,{0,0,1,1}],2],{n,60}]//Union (* Harvey P. Dale, Mar 15 2016 *)

Vec(x*(1+2*x)/((1-x)*(1-4*x)*(1+4*x)) + O(x^50)) \\ Colin Barker, May 19 2016

G.f.: x*(1+2*x)/(1-x-16*x^2+16*x^3).
a(n) = 4^(n-1) - (4 + (-4)^n)/20. - Robert Israel, Sep 02 2014
a(n) = a(n-1)+16*a(n-2)-16*a(n-3) for n>3. - Colin Barker, May 19 2016

A036991 Numbers k with the property that in the binary expansion of k, reading from right to left, the number of 0's never exceeds the number of 1's.

Original entry on oeis.org

0, 1, 3, 5, 7, 11, 13, 15, 19, 21, 23, 27, 29, 31, 39, 43, 45, 47, 51, 53, 55, 59, 61, 63, 71, 75, 77, 79, 83, 85, 87, 91, 93, 95, 103, 107, 109, 111, 115, 117, 119, 123, 125, 127, 143, 151, 155, 157, 159, 167, 171, 173, 175, 179, 181, 183, 187, 189, 191, 199, 203

Offset: 1

N. J. A. Sloane

List of binary words that correspond to a valid pairing of parentheses. - Joerg Arndt, Nov 27 2004
This sequence includes as subsequences A000225, A002450, A007583, A036994, A052940, A112627, A113836, A113841, A290114; and also A015521 (without 0), A083713 (without 0), A086224 (without 6), A182512 (without 0). - Gennady Eremin, Nov 27 2021 and Aug 26 2023
Partial differences are powers of 2 (cf. A367626, A367627). - Gennady Eremin, Dec 23 2021
This is the sequence A030101(A014486(n)), n >= 0, sorted into ascending order. See A014486 for more references, illustrations, etc., concerning Dyck paths and other associated structures enumerated by the Catalan numbers. - Antti Karttunen, Sep 25 2023
The terms in this sequence with a given length in base 2 are counted by A001405. For example, the number of terms of bit length k=5 (these are 19, 21, 23, 27, 29, and 31) is equal to A001405(k-1) = A001405(4) = 6. - Gennady Eremin, Nov 07 2023

			From _Joerg Arndt_, Dec 05 2021: (Start)
List of binary words with parentheses for those in the sequence (indicated by P). The binary words are scanned starting from the least significant bit, while the parentheses words are written left to right:
     Binary   Parentheses (if the value is in the sequence)
00:  ..... P  [empty string]
01:  ....1 P   ()
02:  ...1.
03:  ...11 P   (())
04:  ..1..
05:  ..1.1 P   ()()
06:  ..11.
07:  ..111 P   ((()))
08:  .1...
09:  .1..1
10:  .1.1.
11:  .1.11 P   (()())
12:  .11..
13:  .11.1 P   ()(())
14:  .111.
15:  .1111 P   (((())))
16:  1....
17:  1...1
18:  1..1.
19:  1..11 P   (())()
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..13496 (all terms < 2^16; first 1000 terms from Reinhard Zumkeller)
Joerg Arndt, Matters Computational (The Fxtbook), section 1.28, pp. 78-80.
Gennady Eremin, Dyck Numbers, IV. Nested patterns in OEIS A036991, arXiv:2306.10318, 2023. See pp. 1-2, 4, 7-11, 13-14.
Gennady Eremin, Partitioning the set of natural numbers into Mersenne trees and into arithmetic progressions; Natural Matrix and Linnik's constant, arXiv:2405.16143 [math.CO], 2024. See pp 2-5, 14.
Gennady Eremin, Infinite matrix of odd natural numbers. A bit about Sophie Germain prime numbers, arXiv:2501.17090 [math.GM], 2025. See pp. 3, 11.
Index entries for sequences related to binary expansion of n

Cf. A350577 (primes subsequence).
See also A014486, A030101, A036988, A036990, A036992. A036994 is a subset (requires the count of zeros to be strictly less than the count of 1's).
See also A030308, A000225, A002450, A007583, A350346, A367625, A367626 & A367627 (first differences).

a036991 n = a036991_list !! (n-1)
a036991_list = filter ((p 1) . a030308_row) [0..] where
   p     []    = True
   p ones (0:bs) = ones > 1 && p (ones - 1) bs
   p ones (1:bs) = p (ones + 1) bs
-- Reinhard Zumkeller, Jul 31 2013

q:= proc(n) local l, t, i; l:= Bits[Split](n); t:=0;
      for i to nops(l) do t:= t-1+2*l[i];
        if t<0 then return false fi
      od: true
    end:
select(q, [$0..300])[];  # Alois P. Heinz, Oct 09 2019

moreOnesRLQ[n_Integer] := Module[{digits, len, flag = True, iter = 1, ones = 0, zeros = 0}, digits = Reverse[IntegerDigits[n, 2]]; len = Length[digits]; While[flag && iter < len, If[digits[[iter]] == 1, ones++, zeros++]; flag = ones >= zeros; iter++]; flag]; Select[Range[0, 203], moreOnesRLQ] (* Alonso del Arte, Sep 21 2011 *)
Join[{0},Select[Range[210],Min[Accumulate[Reverse[IntegerDigits[#,2]]/.{0->-1}]]>-1&]] (* Harvey P. Dale, Apr 18 2014 *)

select( {is_A036991(n,c=1)=!n||!until(!n>>=1,(c-=(-1)^bittest(n,0))||return)}, [0..99]) \\ M. F. Hasler, Nov 26 2021

def ok(n):
    if n == 0: return True # by definition
    count = {"0": 0, "1": 0}
    for bit in bin(n)[:1:-1]:
        count[bit] += 1
        if count["0"] > count["1"]: return False
    return True
print([k for k in range(204) if ok(k)]) # Michael S. Branicky, Nov 25 2021

from itertools import count, islice
def A036991_gen(): # generator of terms
    yield 0
    for n in count(1):
        s = bin(n)[2:]
        c, l = 0, len(s)
        for i in range(l):
            c += int(s[l-i-1])
            if 2*c <= i:
                break
        else:
            yield n
A036991_list = list(islice(A036991_gen(),20)) # Chai Wah Wu, Dec 30 2021

If a(n) = A000225(k) for some k, then a(n+1) = a(n) + A060546(k). - Gennady Eremin, Nov 07 2023

More terms from Erich Friedman
Edited by N. J. A. Sloane, Sep 14 2008 at the suggestion of R. J. Mathar
Offset corrected and example adjusted accordingly by Reinhard Zumkeller, Jul 31 2013

A108020 a(n) is the number whose binary representation is the concatenation of n strings of the four digits "1100".

Original entry on oeis.org

0, 12, 204, 3276, 52428, 838860, 13421772, 214748364, 3435973836, 54975581388, 879609302220, 14073748835532, 225179981368524, 3602879701896396, 57646075230342348, 922337203685477580, 14757395258967641292, 236118324143482260684, 3777893186295716170956

Offset: 0

Alexandre Wajnberg, May 31 2005

Numbers whose base-16 representation consists entirely of 12's; 12 times base-16 repunits. - Franklin T. Adams-Watters, Mar 29 2006

			a(3) = 3276 because 3276 written in base 2 is the digit string "1100" written three times: 110011001100.

Colin Barker, Table of n, a(n) for n = 0..800
Index entries for linear recurrences with constant coefficients, signature (17,-16).

Cf. A131865, A182512.

Table[ FromDigits[ Flatten[ Table[{1, 1, 0, 0}, {i, n}]], 2], {n, 0, 16}] (* Robert G. Wilson v, Jun 01 2005 *)
Table[FromDigits[PadRight[{},4n,{1,1,0,0}],2],{n,0,20}] (* Harvey P. Dale, Aug 12 2012 *)

concat(0, Vec(12*x/((1-x)*(1-16*x)) + O(x^100))) \\ Colin Barker, Dec 06 2015

a(n)=12*(16^n - 1)/15 \\ Charles R Greathouse IV, Nov 01 2022

a(n) = 12*(16^n - 1)/15. - Franklin T. Adams-Watters, Mar 29 2006
From Colin Barker, Dec 06 2015: (Start)
a(n) = 17*a(n-1) - 16*a(n-2) for n > 1.
G.f.: 12*x / ((1-x)*(1-16*x)).
(End)
a(n) = 4*A182512(n). - Jamie Simpson, Oct 25 2022
a(n) = 12*A131865(n-1) for n>0. - Hugo Pfoertner, Nov 01 2022

More terms from Robert G. Wilson v, Jun 01 2005

A227451 Number whose binary expansion encodes via runlengths the partition that is at the top of the main trunk of Bulgarian solitaire game tree drawn for the deck with n(n+1)/2 cards.

Original entry on oeis.org

0, 1, 5, 18, 77, 306, 1229, 4914, 19661, 78642, 314573, 1258290, 5033165, 20132658, 80530637, 322122546, 1288490189, 5153960754, 20615843021, 82463372082, 329853488333, 1319413953330, 5277655813325, 21110623253298, 84442493013197, 337769972052786, 1351079888211149

Offset: 0

Antti Karttunen, Jul 12 2013

The terms have particular patterns in their binary expansion, which encodes for an "almost triangular partition" when runlength encoding of unordered partitions are used (please see A129594 for how that encoding works). These are obtained from the perfectly triangular partitions shown in A037481 by inserting 1 to the front of the partition and decrementing the last summand (the largest) by one:
  n   a(n)    same in binary           run lengths   unordered partition
    0                 0                    []                    {}
    1                 1                   [1]                   {1}
    5               101               [1,1,1]               {1+1+1}
   18             10010             [1,2,1,1]             {1+1+2+2}
   77           1001101           [1,2,2,1,1]           {1+1+2+3+3}
  306         100110010         [1,2,2,2,1,1]         {1+1+2+3+4+4}
 1229       10011001101       [1,2,2,2,2,1,1]       {1+1+2+3+4+5+5}
 4914     1001100110010     [1,2,2,2,2,2,1,1]     {1+1+2+3+4+5+6+6}
19661   100110011001101   [1,2,2,2,2,2,2,1,1]   {1+1+2+3+4+5+6+7+7}
78642 10011001100110010 [1,2,2,2,2,2,2,2,1,1] {1+1+2+3+4+5+6+7+8+8}
These partitions occur at the tops of the main trunks of the game trees constructed for decks consisting of 1+2+3+...+k cards. See A037481 for the encoding of the roots of the main trunks of the same trees.

Martin Gardner, Colossal Book of Mathematics, Chapter 34, Bulgarian Solitaire and Other Seemingly Endless Tasks, pp. 455-467, W. W. Norton & Company, 2001.

Antti Karttunen, Table of n, a(n) for n = 0..1000
Wikipedia, Bulgarian solitaire
Index entries for linear recurrences with constant coefficients, signature (4,1,-4).

Cf. A037481, A182512.

The left edge of the table A227452.

LinearRecurrence[{4,1,-4},{0,1,5,18,77},40] (* Harvey P. Dale, Sep 22 2016 *)

a(n)=if(n<1,0,if(n==1,1,(3*4^n+7*(-1)^n-5)/10)) \\ Ralf Stephan

a(0)=0, a(1)=1, for n>=2, a(n) = A053645(2*A037481(n)) + (1 - (n mod 2)). [Follows from the "insert 1 and decrement the largest part by one" operation on triangular partitions]
Alternatively:
a(0)=0, a(1)=1, and for n>=2, if n is even, then a(n) = 1 + (4*A182512((n-2)/2)) + 2^(2*(n-1)), and if n is odd, then a(n) = 2 + (16*A182512((n-3)/2)) + 2^(2*(n-1)).
From Ralf Stephan, Jul 20 2013: (Start)
a(n) = (1/10) * (3*4^n + 7*(-1)^n - 5).
a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3), n>3.
G.f.: (4*x^4 - 3*x^3 + x^2 + x)/((1-x)*(1+x)*(1-4*x)). (End)

cp's OEIS Frontend

A043291 Every run length in base 2 is 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A175046 Write n in binary, then increase each run of 0's by one 0, and increase each run of 1's by one 1. a(n) is the decimal equivalent of the result.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Python

Formula

Extensions

A112627 Decimal equivalent of number defined by last k bits of the infinite binary string ...0011001100110011 (numbers with leading zeros omitted).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A036991 Numbers k with the property that in the binary expansion of k, reading from right to left, the number of 0's never exceeds the number of 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A108020 a(n) is the number whose binary representation is the concatenation of n strings of the four digits "1100".

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A227451 Number whose binary expansion encodes via runlengths the partition that is at the top of the main trunk of Bulgarian solitaire game tree drawn for the deck with n(n+1)/2 cards.

Views

Author

Keywords

Comments