A108020 -id:A108020 - 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

A109499 Number of closed walks of length n on the complete graph on 5 nodes from a given node.

Original entry on oeis.org

1, 0, 4, 12, 52, 204, 820, 3276, 13108, 52428, 209716, 838860, 3355444, 13421772, 53687092, 214748364, 858993460, 3435973836, 13743895348, 54975581388, 219902325556, 879609302220, 3518437208884, 14073748835532

Offset: 0

Mitch Harris, Jun 30 2005

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Christopher R. Kitching, Henri Kauhanen, Jordan Abbott, Deepthi Gopal, Ricardo Bermúdez-Otero, and Tobias Galla, Estimating transmission noise on networks from stationary local order, arXiv:2405.12023 [cond-mat.stat-mech], 2024. See p. 48.
Index entries for linear recurrences with constant coefficients, signature (3,4).

Cf. A108020 (bisection), A109502.

Cf. A001045, A078008, A097073, A115341, A015518, A054878, A015521 (forms k=4^n-k). - Vladimir Joseph Stephan Orlovsky, Dec 11 2008

a:=[1,0];; for n in [3..30] do a[n]:=3*a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Mar 23 2019

[(4^n + 4*(-1)^n)/5: n in [0..30]]; // Vincenzo Librandi, Aug 12 2011

CoefficientList[Series[(1-3*x)/(1-3*x-4*x^2), {x,0,30}], x] (* or *) LinearRecurrence[{3,4}, {1,0}, 30] (* G. C. Greubel, Dec 30 2017 *)

a(n)=(4^n+4*(-1)^n)/5 \\ Charles R Greathouse IV, Oct 01 2012

[(4^n+4*(-1)^n)/5 for n in (0..30)] # G. C. Greubel, Mar 23 2019

G.f.: (1 - 3*x)/(1 - 3*x - 4*x^2).
a(n) = (4^n + 4*(-1)^n)/5.
a(n+1) = 4*A015521(n). - Paul Curtz, Nov 01 2009
a(n) = 3*a(n-1) + 4*a(n-1). - G. C. Greubel, Dec 30 2017
a(n) = A108020((n - 1) / 2) = 'ccc...c' (n digits) in base 16, for odd n. - Georg Fischer, Mar 23 2019
E.g.f.: (exp(4*x) + 4*exp(-x))/5. - G. C. Greubel, Mar 23 2019

Corrected by Franklin T. Adams-Watters, Sep 18 2006

A182512 a(n) = (16^n - 1)/5.

Original entry on oeis.org

0, 3, 51, 819, 13107, 209715, 3355443, 53687091, 858993459, 13743895347, 219902325555, 3518437208883, 56294995342131, 900719925474099, 14411518807585587, 230584300921369395, 3689348814741910323, 59029581035870565171, 944473296573929042739

Offset: 0

Brad Clardy, May 03 2012

Even bisection of A015521 and also A112627. All of the terms are divisible by 3, even terms by 17.

These are binary numbers 11, 110011, 1100110011, ... - Jamie Simpson, Oct 28 2022

Robert Israel, Table of n, a(n) for n = 0..830
E. Estrada and J. A. de la Pena, From Integer Sequences to Block Designs via Counting Walks in Graphs, arXiv preprint arXiv:1302.1176 [math.CO], 2013. - From _N. J. A. Sloane_, Feb 28 2013
E. Estrada and J. A. de la Pena, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Index entries for linear recurrences with constant coefficients, signature (17,-16).

Cf. A015521, A112627.

Magma
```
[(1/5)*2^(4*i) -(1/5): i in [0..30]];
```

seq((16^n-1)/5, n=0..50); # Robert Israel, Jan 22 2016

(16^Range[0,20]-1)/5 (* Harvey P. Dale, Aug 07 2019 *)
LinearRecurrence[{17,-16},{0,3},20] (* Harvey P. Dale, Aug 07 2019 *)

a(n) = (16^n - 1)/5; \\ Michel Marcus, Jan 22 2016

a(n) = 16*a(n-1) + 3 where a(0)=0.
a(n) = A015521(2n).
a(n) = A112627(2n) for n >= 1; a(0)=0.
G.f.: 3*x / ( (16*x-1)*(x-1) ). - R. J. Mathar, Apr 20 2015
a(n) = 3*A131865(n-1). - R. J. Mathar, Apr 20 2015
a(n) = A108020(n)/4. - Jamie Simpson, Oct 28 2022

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

A109499 Number of closed walks of length n on the complete graph on 5 nodes from a given node.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A182512 a(n) = (16^n - 1)/5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula