A132666 -id:A132666 - cp's OEIS frontend

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726, 4194302, 6291454

Offset: 0

R. K. Guy

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.
Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5                R
                    / \
                   /   \
                  /     \
                 /       B
                /       / \
mrbt4          B       /   B
              / \     B   E E
             /   B   E E
mrbt3       R   E E
           / \
          /   B
mrbt2    B   E E
        / E
mrbt1  R
      E E
(Red nodes shown as R, blacks as B, externals as E.)
Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017
a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors.  For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019
Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020
Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

			After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ... - _Jason Kimberley_, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4;
a(4) = 1+1+2+2 = 6;
a(5) = 1+1+2+2+4 = 10.
_Yuchun Ji_, Nov 16 2018

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753-754.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, in Rapide Bilan 2012-2013, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013.
Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)-cage).
Bisections are A033484 (even) and A000918 (odd).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
-- Reinhard Zumkeller, Jun 17 2015

[2^Floor((n+2)/2)+2^Floor((n+1)/2)-2: n in [0..50]]; // Vincenzo Librandi, Aug 16 2011

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008

a[n_?EvenQ] := 3*2^(n/2)-2; a[n_?OddQ] := 2^(2+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0,1},n],And[Max@@Length/@Split[#]<=2,!MatchQ[Length/@Split[#],{_,2,ins:1..,2,_}/;OddQ[Plus[ins]]]]&]],{n,0,15}] (* Gus Wiseman, Nov 28 2019 *)

a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ Charles R Greathouse IV, Oct 21 2011

def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
print([a(n) for n in range(43)]) # Michael S. Branicky, Feb 19 2022

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n) = 3*2^n - 2 = A033484(n);
a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, n-k).
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1)) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n-1) + 1 for n > 0. - Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010
a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1-x), where R(k) = 1 + 2*x/( 1 - x/(x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - Luce ETIENNE, Sep 01 2014
a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - Yuchun Ji, Nov 23 2018
E.g.f.: 3*cosh(sqrt(2)*x) - 2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x) - 2*sinh(x). - Stefano Spezia, Apr 06 2022

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000

Replaced definition with a simpler one. - N. J. A. Sloane, Jul 09 2022

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 15, 23, 31, 47, 63, 95, 127, 191, 255, 383, 511, 767, 1023, 1535, 2047, 3071, 4095, 6143, 8191, 12287, 16383, 24575, 32767, 49151, 65535, 98303, 131071, 196607, 262143, 393215, 524287, 786431, 1048575, 1572863, 2097151, 3145727

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

a(n) is the least k such that A056792(k) = n.
One quarter of the number of positive integer (n+2) X (n+2) arrays with every 2 X 2 subblock summing to 1. - R. H. Hardin, Sep 29 2008
Number of length n+1 left factors of Dyck paths having no DUU's (here U=(1,1) and D=(1,-1)). Example: a(4)=7 because we have UDUDU, UUDDU, UUDUD, UUUDD, UUUDU, UUUUD, and UUUUU (the paths UDUUD, UDUUU, and UUDUU do not qualify).
Number of binary palindromes < 2^n (see A006995). - Hieronymus Fischer, Feb 03 2012
Partial sums of A016116 (omitting the initial term). - Hieronymus Fischer, Feb 18 2012
a(n - 1), n > 1, is the number of maximal subsemigroups of the monoid of order-preserving or -reversing partial injective mappings on a set with n elements. - Wilf A. Wilson, Jul 21 2017
Number of monomials of the algebraic normal form of the Boolean function representing the n-th bit of the product 3x in terms of the bits of x. - Sebastiano Vigna, Oct 04 2020

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 7*x^4 + 11*x^5 + 15*x^6 + 23*x^7 + ... - _Michael Somos_, Jun 24 2018

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019).
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, preprint, 2014.
J.-L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, Journal of Combinatorics 5 (2014), 453-469.
David Blackman and Sebastiano Vigna, Scrambled Linear Pseudorandom Number Generators, ACM Transactions on Mathematical Software, Vol. 47, No. 4, p. 1-32, 2021; arXiv preprint, arXiv:1805.01407 [cs.DS], 2018.
James East, Jitender Kumar, James D. Mitchell, and Wilf A. Wilson, Maximal subsemigroups of finite transformation and partition monoids, arXiv:1706.04967 [math.GR], 2017. [_Wilf A. Wilson_, Jul 21 2017]
Brian Hopkins and Aram Tangboonduangjit, Water Cells in Compositions of 1s and 2s, arXiv:2412.11528 [math.CO], 2024. See p. 9.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1026
Mohammed A. Raouf, Fazirulhisyam Hashim, Jiun Terng Liew, and Kamal Ali Alezabi, Pseudorandom sequence contention algorithm for IEEE 802.11ah based internet of things network, PLoS ONE (2020) Vol. 15, No. 8, e0237386.
Mark Shattuck, Further Results for the Capacity Statistic Distribution on Compositions of 1's and 2's, arXiv:2501.09931 [math.CO], 2025. See p. 3.
Index to sequences related to the complexity of n
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A000225 for even terms, A055010 for odd terms. See also A056792.
Essentially 1 more than A027383, 2 more than A060482. [Comment corrected by Klaus Brockhaus, Aug 09 2009]
Union of A000225 & A055010.
For partial sums see A027383.
See A016116 for the first differences.
Cf. A083329, A107659, A132666.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

List([0..45], n-> ((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1); # G. C. Greubel, Oct 22 2019

a052955 n = a052955_list !! n
a052955_list = 1 : 2 : map ((+ 1) . (* 2)) a052955_list
-- Reinhard Zumkeller, Feb 22 2012

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1: n in [0..45]]; // G. C. Greubel, Oct 22 2019

spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z),Z)),Union(Sequence(Z),Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n]/2, n=2..43); # Zerinvary Lajos, Mar 16 2008

a[n_]:= If[EvenQ[n], 2^(n/2+1) -1, 3*2^((n-1)/2) -1]; Table[a[n], {n, 0, 41}] (* Robert G. Wilson v, Jun 05 2004 *)
a[0]=1; a[1]=2; a[n_]:= a[n]= 2 a[n-2] +1; Array[a, 42, 0]
a[n_]:= (2 + Mod[n, 2]) 2^Quotient[n, 2] - 1; (* Michael Somos, Jun 24 2018 *)

a(n)=(2+n%2)<<(n\2)-1 \\ Charles R Greathouse IV, Jun 19 2011

{a(n) = (n%2 + 2) * 2^(n\2) - 1}; /* Michael Somos, Jun 24 2018 */

# command line argument tells how high to take n
# Beyond a(38) = 786431 you may need a special code to handle large integers
  $lim = shift;
  sub show{};
$n = $incr = $P = 1;
show($n, $incr, $P);
$incr = 1;
for $n (2..$lim) {
    $P += $incr;
    show($n, $P, $incr, $P);
    $incr *=2 if ($n % 2); # double the increment after an odd n
}
sub show {
    my($n, $P) = @_;
    printf("%4d\t%16g\n", $n, $P);
}
# Mark A. Mandel (thnidu aT  g ma(il) doT c0m), Dec 29 2010

def A052955(n): return ((2|n&1)<<(n>>1))-1 # Chai Wah Wu, Jul 13 2023

[((5-(-1)^n)/2)*2^((2*n-1+(-1)^n)/4)-1 for n in (0..45)] # G. C. Greubel, Oct 22 2019

a(0)=1, a(1)=2; thereafter a(n) = 2*a(n-2) + 1, n >= 2.
G.f.: (1 + x - x^2)/((1 - x)*(1 - 2*x^2)).
a(n) = -1 + Sum_{alpha = RootOf(-1 + 2*Z^2)} (1/4) * (3 + 4*alpha) * alpha^(-1-n). (That is, the sum is indexed by the roots of the polynomial -1 + 2*Z^2.)
a(n) = 2^(n/2) * (3*sqrt(2)/4 + 1 - (3*sqrt(2)/4 - 1) * (-1)^n) - 1. - Paul Barry, May 23 2004
a(n) = 1 + Sum_{k=0..n-1} A016116(k). - Robert G. Wilson v, Jun 05 2004
A132340(a(n)) = A027383(n). - Reinhard Zumkeller, Aug 20 2007
From Hieronymus Fischer, Sep 15 2007: (Start)
a(n) = A027383(n-1) + 1 for n>0.
a(n) = A132666(a(n+1)-1).
a(n) = A132666(a(n-1)) + 1 for n>0.
A132666(a(n)) = a(n+1) - 1. (End)
a(n) = A027383(n+1)/2. - Zerinvary Lajos, Mar 16 2008
a(n) = (5 - (-1)^n)/2*2^floor(n/2) - 1. - Hieronymus Fischer, Feb 03 2012
a(2n+1) = (a(2*n) + a(2*n+2))/2. Combined with a(n) = 2*a(n-2) + 1, n >= 2 and a(0) = 1, this specifies the sequence. - Richard R. Forberg, Nov 30 2013
a(n) = ((5 - (-1)^n)/2)*2^((2*n - 1 + (-1)^n)/4) - 1. - Luce ETIENNE, Sep 20 2014
a(n) = -(2^(n+1)) * A107659(-3-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/4)*exp(-sqrt(2)*x)*(4 - 3*sqrt(2) + (4 + 3*sqrt(2))*exp(2*sqrt(2)*x) - 4*exp(x + sqrt(2)*x)). - Stefano Spezia, Oct 22 2019
A term k appears in this sequence <=> 4 does not divide binomial(k, j) for any j in 0..k. - Peter Luschny, Jun 28 2025

Formula and more terms from Henry Bottomley, May 03 2000
Additional comments from Robert G. Wilson v, Jan 29 2001
Minor edits from N. J. A. Sloane, Jul 09 2022

A038722 Take the sequence of natural numbers (A000027) and reverse successive subsequences of lengths 1,2,3,4,... .

Original entry on oeis.org

1, 3, 2, 6, 5, 4, 10, 9, 8, 7, 15, 14, 13, 12, 11, 21, 20, 19, 18, 17, 16, 28, 27, 26, 25, 24, 23, 22, 36, 35, 34, 33, 32, 31, 30, 29, 45, 44, 43, 42, 41, 40, 39, 38, 37, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 78, 77, 76

Offset: 1

N. J. A. Sloane, May 02 2000

Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).
The rectangular array having A038722 as antidiagonals is the transpose of the rectangular array given by A000217. Column 1 of array A038722 is A000124 (central polygonal numbers). Array A038722 is the dispersion of the complement of A000124. - Clark Kimberling, Apr 05 2003
a(n) is the smallest number not yet in the sequence such that n + a(n) is one more than a square. - Franklin T. Adams-Watters, Apr 06 2009
From Hieronymus Fischer, Apr 30 2012: (Start)
A reordering of the natural numbers.
The sequence is self-inverse in that a(a(n)) = n.
Also: a(1) = 1, a(n) = m (where m is the least triangular number > a(k) for 1 <= k < n), if the minimal natural number not yet in the sequence is greater than a(n-1), otherwise a(n) = a(n-1)-1. (End)

			The rectangular array view is
   1    2    4    7   11   16   22   29   37   46
   3    5    8   12   17   23   30   38   47   57
   6    9   13   18   24   31   39   48   58   69
  10   14   19   25   32   40   49   59   70   82
  15   20   26   33   41   50   60   71   83   96
  21   27   34   42   51   61   72   84   97  111
  28   35   43   52   62   73   85   98  112  127
  36   44   53   63   74   86   99  113  128  144
  45   54   64   75   87  100  114  129  145  162
  55   65   76   88  101  115  130  146  163  181

Suggested by correspondence with Michael Somos.
R. Honsberger, "Ingenuity in Mathematics", Table 10.4 on page 87.

Hieronymus Fischer, Table of n, a(n) for n = 1..11401
Michael Somos, Introduction to Ramanujan theta functions
Eric Weisstein's World of Mathematics, Ramanujan Theta Functions
Index entries for sequences that are permutations of the natural numbers

A self-inverse permutation of the natural numbers.
Cf. A000027, A020703.
Cf. A132666, A132664, A132665, A132674.
Cf. A056011 (boustrophedon).
Cf. A000122, A000700, A010054, A121373.
Cf. A000124, A000217.
Cf. A061579.

a038722 n = a038722_list !! (n-1)
a038722_list = concat a038722_tabl
a038722_tabl = map reverse a000027_tabl
a038722_row n = a038722_tabl !! (n-1)
-- Reinhard Zumkeller, Nov 08 2013

(* Program generates dispersion array T of the increasing sequence f[n] *)
r=40; r1=12; c=40; c1=12; f[n_] := Floor[n+1/2+Sqrt[2n]]
  (* complement of column 1 *)
mex[list_] := NestWhile[#1 + 1 &, 1, Union[list][[#1]] <= #1 &, 1, Length[Union[list]]]
rows = {NestList[f, 1, c]};
Do[rows = Append[rows, NestList[f, mex[Flatten[rows]], r]], {r}];
t[i_, j_] := rows[[i, j]];
TableForm[Table[t[i, j], {i, 1, r1}, {j, 1, c1}]]
(* A038722 array *)
Flatten[Table[t[k, n - k + 1], {n, 1, c1}, {k, 1, n}]] (* A038722 sequence *)
 (* Clark Kimberling, Jun 06 2011, corrected Jan 26 2025 *)
Table[ n, {m, 12}, {n, m (m + 1)/2, m (m - 1)/2 + 1, -1}] // Flatten (* or *)
Table[ Ceiling[(Sqrt[8 n + 1] - 1)/2]^2 - n + 1, {n, 78}] (* Robert G. Wilson v, Jun 27 2014 *)
With[{nn=20},Reverse/@TakeList[Range[(nn(1+nn))/2],Range[nn]]//Flatten] (* Requires Mathematica version 11 or later *) (* Harvey P. Dale, Dec 14 2017 *)

a(n)=local(t=floor(1/2+sqrt(2*n))); if(n<1, 0, t^2-n+1) /* Paul D. Hanna */

a(n) = (sqrt(2n-1) - 1/2)*(sqrt(2n-1) + 3/2) - n + 2 = A061579(n-1) + 1. Seen as a square table by antidiagonals, T(n, k) = k + (n+k-1)*(n+k-2)/2, i.e., the transpose of A000027 as a square table.
G.f.: g(x) = (x/(1-x))*(psi(x) - x/(1-x) + 2*Sum_{k>=0} k*x^(k*(k+1)/2)) where psi(x) = Sum_{k>=0} x^(k*(k+1)/2) = (1/2)*x^(-1/8)*theta_2(0,x^(1/2)) is a Ramanujan theta function. - Hieronymus Fischer, Aug 08 2007
a(n) = floor(sqrt(2*n) + 1/2)^2 - n + 1. - Clark Kimberling, Jun 05 2011; corrected by Paul D. Hanna, Jun 27 2011
From Hieronymus Fischer, Apr 30 2012: (Start)
a(n) = a(n-1)-1, if a(n-1)-1 > 0 is not in the set {a(k)| 1<=ka(n) = n for n = 2k(k+1)+1, k >= 0.
a(n+1) = (m+2)(m+3)/2, if 8a(n)-7 is a square of an odd number, otherwise a(n+1) = a(n)-1, where m = (sqrt(8a(n)-7)-1)/2.
a(n) = ceiling((sqrt(8n+1)-1)/2)^2 - n + 1. (End)
G.f. as rectangular array: x*y*(1 - (1 + x)*y + (1 - x + x^2)*y^2)/((1 - x)^3*(1 - y)^3). - Stefano Spezia, Dec 25 2022

A084221 a(n+2) = 4*a(n), with a(0)=1, a(1)=3.

Original entry on oeis.org

1, 3, 4, 12, 16, 48, 64, 192, 256, 768, 1024, 3072, 4096, 12288, 16384, 49152, 65536, 196608, 262144, 786432, 1048576, 3145728, 4194304, 12582912, 16777216, 50331648, 67108864, 201326592, 268435456, 805306368, 1073741824, 3221225472, 4294967296, 12884901888

Offset: 0

Paul Barry, May 21 2003

Binomial transform is A060925. Binomial transform of A084222.
Sequences with similar recurrence rules: A016116 (multiplier 2), A038754 (multiplier 3), A133632 (multiplier 5). See A133632 for general formulas. - Hieronymus Fischer, Sep 19 2007
Equals A133080 * A000079. A122756 is a companion sequence. - Gary W. Adamson, Sep 19 2007

			Binary...............Decimal
1..........................1
11.........................3
100........................4
1100......................12
10000.....................16
110000....................48
1000000...................64
11000000.................192
100000000................256
1100000000...............768
10000000000.............1024
110000000000............3072, etc. - _Philippe Deléham_, Mar 21 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hester Graves, The Minimal Euclidean Function on the Gaussian Integers, arXiv:1802.08281 [math.NT], 2018. See Definition 2.3 p.3.
Index entries for linear recurrences with constant coefficients, signature (0,4)

For partial sums see A133628. Partial sums for other multipliers p: A027383(p=2), A087503(p=3), A133629(p=5).
Other related sequences: A132666, A132667, A132668, A132669.
Cf. A000302, A133080, A133087, A164346.

[(5*2^n-(-2)^n)/4: n in [0..40]]; // Vincenzo Librandi, Aug 13 2011

CoefficientList[Series[(-3*x - 1)/(4*x^2 - 1), {x, 0, 200}], x] (* Vladimir Joseph Stephan Orlovsky, Jun 10 2011 *)

a(n)=([0,1; 4,0]^n*[1;3])[1,1] \\ Charles R Greathouse IV, Oct 03 2016

a(n) = (5*2^n-(-2)^n)/4.
G.f.: (1+3*x)/((1-2*x)(1+2*x)).
E.g.f.: (5*exp(2*x) - exp(-2*x))/4.
a(n) = A133628(n) - A133628(n-1) for n>1. - Hieronymus Fischer, Sep 19 2007
Equals A133080 * [1, 2, 4, 8, ...]. Row sums of triangle A133087. - Gary W. Adamson, Sep 08 2007
a(n+1)-2a(n) = A000079 signed. a(n)+a(n+2)=5*a(n). First differences give A135520. - Paul Curtz, Apr 22 2008
a(n) = A074323(n+1)*A016116(n). - R. J. Mathar, Jul 08 2009
a(n+3) = a(n+2)*a(n+1)/a(n). - Reinhard Zumkeller, Mar 04 2011
a(n) = Sum_{k=0..n+1} A181650(n+1,k)*2^k. - Philippe Deléham, Nov 19 2011
a(2*n) = A000302(n); a(2*n+1) = A164346(n). - Philippe Deléham, Mar 21 2014

Edited by N. J. A. Sloane, Dec 14 2007

A132674 a(1)=1, a(n) = 10*a(n-1) if the minimal positive integer not yet in the sequence is greater than a(n-1), else a(n) = a(n-1) - 1.

Original entry on oeis.org

1, 10, 9, 8, 7, 6, 5, 4, 3, 2, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62

Offset: 1

Hieronymus Fischer, Aug 24 2007, Sep 15 2007

nonn

Also: a(1)=1, a(n) = maximal positive integer < a(n-1) not yet in the sequence, if it exists, else a(n) = 10*a(n-1).
Also: a(1)=1, a(n) = a(n-1) - 1, if a(n-1) - 1 > 0 and has not been encountered so far, else a(n) = 10*a(n-1).
A permutation of the positive integers. The sequence is self-inverse, in that a(a(n)) = n.

For parameters p=2 to p=9 see A132666 - A132673.

For a similar recurrence rule concerning Fibonacci and Lucas numbers see A132664 and A132665.

The following formulas are given for a general parameter p > 2 considering the recurrence rule above (i.e., a(n) = p*a(n-1)...; p=10 for this sequence).
G.f.: g(x) = (x(1-2x)/(1-x) + px^2*f'(x^((2p-1)/(p-1))) + ((2p-1)/p^2)*(f'(x^(1/(p-1))) - px - 1)/(1-x) where f(x) = Sum_{k>=0} x^(p^k) and f'(z) = derivative of f(x) at x = z.
a(n) = ((3p-1)*p^(r/2) - p - 1)/(p-1) - n if both r and s are even, else a(n) = ((p^2 + 2p - 1)*p^((s-1)/2) - p - 1)/(p-1) - n, where r = ceiling(2*log_p(((p-1)n + p)/(2p-1))) and s = ceiling(2*log_p(((p-1)n + p)/p) - 1).
a(n) = (p^floor(1 + (k+1)/2) + (2p-1)*p^floor(k/2) - p - 1)/(p-1) - n, where k=r if r is odd, else k=s (with respect to r and s above; formally, k = ((r+s) - (r-s)*(-1)^r)/2).

A087503 a(n) = 3*(a(n-2) + 1), with a(0) = 1, a(1) = 3.

Original entry on oeis.org

1, 3, 6, 12, 21, 39, 66, 120, 201, 363, 606, 1092, 1821, 3279, 5466, 9840, 16401, 29523, 49206, 88572, 147621, 265719, 442866, 797160, 1328601, 2391483, 3985806, 7174452, 11957421, 21523359, 35872266, 64570080, 107616801, 193710243, 322850406, 581130732

Offset: 0

Reinhard Zumkeller, Sep 11 2003

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

Sequences with similar recurrence rules: A027383 (p=2), A133628 (p=4), A133629 (p=5).
Other related sequences for different p: A016116 (p=2), A038754 (p=3), A084221 (p=4), A133632 (p=5).
See A133629 for general formulas with respect to the recurrence rule parameter p.
Related sequences: A132666, A132667, A132668, A132669.

[(3/2)*(3^Floor((n+1)/2)+3^Floor(n/2)-3^Floor((n-1)/2)-1): n in [0..40]]; // Vincenzo Librandi, Aug 16 2011

A087503 := proc(n)
    option remember;
    if n <=1 then
        op(n+1,[1,3]) ;
    else
        3*procname(n-2)+3 ;
    end if;
end proc:
seq(A087503(n),n=0..20) ; # R. J. Mathar, Sep 10 2021

RecurrenceTable[{a[0]==1,a[1]==3,a[n]==3(a[n-2]+1)},a,{n,40}] (* or *) LinearRecurrence[{1,3,-3},{1,3,6},40] (* Harvey P. Dale, Jan 01 2015 *)

def A087503(n): return (3+((n+1&1)<<1))*3**(n+1>>1)-3>>1 # Chai Wah Wu, Sep 02 2025

a(n) = a(n-1) + A038754(n). (i.e., partial sums of A038754).
From Hieronymus Fischer, Sep 19 2007, formulas adjusted to offset, Dec 29 2012: (Start)
G.f.: (1+2*x)/((1-3*x^2)*(1-x)).
a(n) = (3/2)*(3^((n+1)/2)-1) if n is odd, else a(n) = (3/2)*(5*3^((n-2)/2)-1).
a(n) = (3/2)*(3^floor((n+1)/2) + 3^floor(n/2) - 3^floor((n-1)/2)-1).
a(n) = 3^floor((n+1)/2) + 3^floor((n+2)/2)/2 - 3/2.
a(n) = A132667(a(n+1)) - 1.
a(n) = A132667(a(n-1) + 1) for n > 0.
A132667(a(n)) = a(n-1) + 1 for n > 0.
Also numbers such that: a(0)=1, a(n) = a(n-1) + (p-1)*p^((n+1)/2 - 1) if n is odd, else a(n) = a(n-1) + p^(n/2), where p=3. (End)
a(n) = A052993(n)+2*A052993(n-1). - R. J. Mathar, Sep 10 2021

Additional comments from Hieronymus Fischer, Sep 19 2007
Edited by N. J. A. Sloane, May 04 2010. I merged two essentially identical entries with different offsets, so some of the formulas may need to be adjusted.
Formulas and MAGMA prog adjusted to offset 0 by Hieronymus Fischer, Dec 29 2012

A020703 Take the sequence of natural numbers (A000027) and reverse successive subsequences of lengths 1,3,5,7,...

Original entry on oeis.org

1, 4, 3, 2, 9, 8, 7, 6, 5, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, 22, 21, 20, 19, 18, 17, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 81, 80, 79, 78, 77

Offset: 1

N. J. A. Sloane, May 02 2000

nonn

Arrange A000027, the natural numbers, into a (square) spiral, say clockwise as shown in A068225. Read the numbers from the resulting counterclockwise spiral of the same shape that also begins with 1 and this sequence results. - Rick L. Shepherd, Aug 04 2006
Contribution from Hieronymus Fischer, Apr 30 2012: (Start)
The sequence may also be defined as follows: a(1)=1, a(n)=m^2 (where m^2 is the least square > a(k) for 1<=kA reordering of the natural numbers.
The sequence is self-inverse in that a(a(n))=n.
(End)

			a(2)=4=2^2, since 2^2 is the least square >2=a(1) and the minimal number not yet in the sequence is 2>1=a(1);
a(8)=6=a(7)-1, since the minimal number not yet in the sequence (=5) is <=7=a(7).

R. Honsberger, "Ingenuity in Mathematics", Table 10.4 on page 87.
Suggested by correspondence with Michael Somos.

Hieronymus Fischer, Table of n, a(n) for n = 1..11131
Index entries for sequences that are permutations of the natural numbers

A self-inverse permutation of the natural numbers.
Cf. A000027, A038722.
Cf. A132666, A132664, A132665, A132674.

Flatten[Table[Range[n^2,(n-1)^2+1,-1],{n,10}]] (* Harvey P. Dale, Jan 10 2016 *)
With[{nn=20},Flatten[Reverse/@TakeList[Range[nn^2],Range[1,nn,2]]]] (* Requires Mathematica version 11 or later *) (* Harvey P. Dale, Jan 28 2019 *)

a(n)=local(t); if(n<1,0,t=sqrtint(n-1); 2*(t^2+t+1)-n)

Contribution from Hieronymus Fischer, Apr 30 2012: (Start)

a(n)=a(n-1)-1, if a(n-1)-1 > 0 is not in the set {a(k)| 1<=k

a(n)=n for n=k(k+1)+1, k>=0.

a(n+1)=(sqrt(a(n)-1)+2)^2, if a(n)-1 is a square, a(n+1)=a(n)-1, else.

a(n)=2*(floor(sqrt(n-1))+1)*floor(sqrt(n-1))-n+2. (End)

A132665 a(1)=1, a(2)=3, a(n) = a(n-1) + n if the minimal positive integer not yet in the sequencer is greater than a(n-1), else a(n) = a(n-1)-1.

Original entry on oeis.org

1, 3, 2, 6, 5, 4, 11, 10, 9, 8, 7, 19, 18, 17, 16, 15, 14, 13, 12, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69

Offset: 1

Hieronymus Fischer, Sep 15 2007

nonn

Also: a(1)=1, a(2)=3, a(n) = maximal positive number < a(n-1) not yet in the sequence, if it exists, else a(n) = a(n-1) + n.
Also: a(1)=1, a(2)=3, a(n) = a(n-1) - 1, if a(n-1) - 1 > 0 and has not been encountered so far, else a(n) = a(n-1) + n.
A permutation of the positive integers. The sequence is self-inverse, in that a(a(n)) = n.

Cf. A000045, A104152, A130233.
For an analog concerning Lucas numbers see A132664.
See A132666-A132674 for sequences with a similar recurrence rule.

G.f.: g(x) = (F'(x) - x^2 - 1/(1-x))/(1-x) where F(x) = Sum_{k>=0} x^Fibonacci(k). F(x) is the g.f. of the Fibonacci indicator sequence (see A104162) and F'(x) = derivative of F(x).
a(n) = Fibonacci(Fibonacci_inverse(n+1) + 2) - n - 3 = A000045(A130233(n+1) + 2) - n - 3.
a(n) = A000032(floor(log_phi(sqrt(5)*(n+1) + 1) + 2)) - n - 3, where phi = (1 + sqrt(5))/2 is the golden ratio.
a(n) = A000032(floor(log_phi(sqrt(5)*n + 2*phi) + 2)) - n - 3.

A132664 a(1)=1, a(2)=2, a(n) = a(n-1) + n if the minimal positive integer not yet in the sequence is greater than a(n-1), else a(n) = a(n-1) - 1.

Original entry on oeis.org

1, 2, 5, 4, 3, 9, 8, 7, 6, 16, 15, 14, 13, 12, 11, 10, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48

Offset: 1

Hieronymus Fischer, Sep 15 2007

nonn

Also: a(1)=1, a(2)=2, a(n) = maximal positive number < a(n-1) not yet in the sequence, if it exists, else a(n) = a(n-1) + n.
Also: a(1)=1, a(2)=2, a(n) = a(n-1) - 1, if a(n-1) - 1 > 0 and has not been encountered so far, else a(n) = a(n-1) + n.
A permutation of the positive integers. The sequence is self-inverse, in that a(a(n)) = n.

Cf. A000032, A102460, A130241.
For an analog concerning Fibonacci numbers see A132665.
See A132666-A132674 for sequences with a similar recurrence rule.

G.f.: g(x) = (L'(x) - x^2 - 1/(1-x))/(1-x) where L(x) = Sum_{k>=0} x^Lucas(k) and Lucas(k) = A000032(k). L(x) is the g.f. of the Lucas indicator sequence (see A102460) and L'(x) = derivative of L(x).
a(n) = Lucas(Lucas_inverse(n+1)+2) - n - 3 = A000032(A130241(n+1) + 2) - n - 3 for n > 1.
a(n) = A000032(floor(log_phi(n + 3/2)) + 2) - n - 3 for n > 1, where phi = (1 + sqrt(5))/2 is the golden ratio.

A133628 a(1)=1, a(n) = a(n-1) + (p-1)*p^(n/2-1) if n is even, else a(n) = a(n-1) + p^((n-1)/2), where p=4.

Original entry on oeis.org

1, 4, 8, 20, 36, 84, 148, 340, 596, 1364, 2388, 5460, 9556, 21844, 38228, 87380, 152916, 349524, 611668, 1398100, 2446676, 5592404, 9786708, 22369620, 39146836, 89478484, 156587348, 357913940, 626349396, 1431655764, 2505397588

Offset: 1

Hieronymus Fischer, Sep 19 2007

nonn

This is essentially a duplicate of A097164. - R. J. Mathar, Jun 08 2008

Partial sums of A084221.

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

Sequences with similar recurrence rules: A027383(p=2), A087503(p=3), A133629(p=5).
See A133629 for general formulas with respect to the recurrence rule parameter p.
Related sequences: A132666, A132667, A132668, A132669.
Other related sequences for different p: A016116(p=2), A038754(p=3), A084221(p=4), A133632(p=5).

[4^Floor(n/2)+4^Floor((n+1)/2)/3-4/3: n in [1..40]]; // Vincenzo Librandi, Aug 17 2011

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=4*a[n-2]+4 od: seq(a[n], n=1..31); # Zerinvary Lajos, Mar 17 2008

nxt[{n_,a_}]:={n+1,If[OddQ[n],a+3*4^((n+1)/2-1),a+4^(n/2)]}; Transpose[ NestList[ nxt,{1,1},30]][[2]] (* Harvey P. Dale, Mar 31 2013 *)

vector(40, n, (3*4^floor(n/2) + 4^floor((n+1)/2) - 4)/3) \\ G. C. Greubel, Nov 08 2018

a(n) = Sum_{k=1..n} A084221(k).
G.f.: x*(1+3*x)/((1-4*x^2)*(1-x)).
a(n) = (4/3)*(4^(n/2)-1) if n is even, otherwise a(n) = (4/3)*(7*4^((n-3)/2)-1).
a(n) = (4/3)*(4^floor(n/2) + 4^floor((n-1)/2) - 4^floor((n-2)/2) - 1).
a(n) = 4^floor(n/2) + 4^floor((n+1)/2)/3 - 4/3.
a(n) = A132668(a(n+1)) - 1.
a(n) = A132668(a(n-1) + 1) for n > 0.
A132668(a(n)) = a(n-1) + 1 for n > 0.

Showing 1-10 of 23 results. Next

cp's OEIS Frontend

A027383 a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A052955 a(2n) = 2*2^n - 1, a(2n+1) = 3*2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Perl

Python

Sage

Formula

Extensions

A038722 Take the sequence of natural numbers (A000027) and reverse successive subsequences of lengths 1,2,3,4,... .

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A084221 a(n+2) = 4*a(n), with a(0)=1, a(1)=3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A132674 a(1)=1, a(n) = 10*a(n-1) if the minimal positive integer not yet in the sequence is greater than a(n-1), else a(n) = a(n-1) - 1.

Views

Author

Keywords

Comments

Crossrefs

Formula

A087503 a(n) = 3*(a(n-2) + 1), with a(0) = 1, a(1) = 3.

Views

Author

Keywords

Links

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

A052955 a(2n) = 22^n - 1, a(2n+1) = 32^n - 1.