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

A318928 Runs-resistance of binary representation of n.

Original entry on oeis.org

1, 2, 1, 3, 2, 3, 1, 3, 3, 2, 4, 2, 4, 3, 1, 3, 3, 5, 4, 4, 2, 5, 4, 3, 4, 4, 3, 3, 4, 3, 1, 3, 3, 5, 3, 3, 5, 4, 3, 4, 5, 2, 4, 3, 4, 5, 4, 3, 3, 3, 2, 4, 4, 3, 3, 2, 3, 4, 3, 3, 4, 3, 1, 3, 3, 5, 3, 3, 5, 3, 4, 3, 3, 5, 6, 4, 5, 3, 3, 4, 5, 4, 4, 4, 2, 5, 4, 5, 5, 4, 5, 5, 4, 5, 4

Offset: 1

N. J. A. Sloane, Sep 09 2018

Following Lenormand (2003), we define the "runs-resistance" of a finite list L to be the number of times the RUNS transformation must be applied to L in order to reduce L to a list with a single element.
Here it is immaterial whether we read the binary representation of n from left to right or right to left.
The RUNS transformation must be applied at least once, in order to obtain a list, so a(n) >= 1.

			11 in binary is [1, 0, 1, 1],
which has runs of lengths [1, 1, 2],
which has runs of lengths [2, 1],
which has runs of lengths [1, 1],
which has a single run of length [2].
This took four steps, so a(11) = 4.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
N. J. A. Sloane, Transforms

See A319103 for an inverse, and A319417 and A319418 for records.
Ignoring the first digit gives A329870.
Cuts-resistance is A319416.
Compositions counted by runs-resistance are A329744.
Binary words counted by runs-resistance are A319411 and A329767.
Cf. A107907, A319420, A329860, A329861, A329865, A329867.

with(transforms);
# compute Lenormand's "resistance" of a list
resist:=proc(a) local ct,i,b;
if whattype(a) <> list then ERROR("input must be a list"); fi:
ct:=0; b:=a; for i from 1 to 100 do
if nops(b)=1 then return(ct); fi;
b:=RUNS(b); ct:=ct+1; od; end;
a:=[1];
for n from 2 to 100 do
b:=convert(n,base,2);
r:=resist(b);
a:=[op(a),r];
od:

Table[If[n == 1, 1, Length[NestWhileList[Length/@Split[#] &, IntegerDigits[n, 2], Length[#] > 1 &]] - 1], {n, 50}] (* Gus Wiseman, Nov 25 2019 *)

a(1) corrected by N. J. A. Sloane, Sep 20 2018

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 9, 15, 25, 40, 64, 104, 169, 273, 441, 714, 1156, 1870, 3025, 4895, 7921, 12816, 20736, 33552, 54289, 87841, 142129, 229970, 372100, 602070, 974169, 1576239, 2550409, 4126648, 6677056, 10803704, 17480761, 28284465, 45765225, 74049690, 119814916

Offset: 0

N. J. A. Sloane

Number of compositions of n into 1's, 3's and 4's. - Len Smiley, May 08 2001
The sum of any two alternating terms (terms separated by one term) produces a number from the Fibonacci sequence. (e.g. 4+9=13, 9+25=34, 6+15=21, etc.) Taking square roots starting from the first term and every other term after, we get the Fibonacci sequence. - Sreyas Srinivasan (sreyas_srinivasan(AT)hotmail.com), May 02 2002
(1 + x + 2*x^2 + x^3)/(1 - x - x^3 - x^4) = 1 + 2*x + 4*x^2 + 6*x^3 + 9*x^4 + 15*x^5 + 25*x^6 + 40*x^7 + ... is the g.f. for the number of binary strings of length where neither 101 nor 111 occur. [Lozansky and Rousseau] Or, equivalently, where neither 000 nor 010 occur.
Equivalently, a(n+2) is the number of length-n binary strings with no two set bits with distance 2; see fxtbook link. - Joerg Arndt, Jul 10 2011
a(n) is the number of words written with the letters "a" and "b", with the following restriction: any "a" must be followed by at least two letters, the second of which is a "b". - Bruno Petazzoni (bpetazzoni(AT)ac-creteil.fr), Oct 31 2005. [This is also equivalent to the previous two conditions.]
Let a(0) = 1, then a(n) = partial products of Product_{n>2} (F(n)/F(n-1))^2 = 1*1*2*2*(3/2)*(3/2)*(5/3)*(5/3)*(8/5)*(8/5)*.... E.g., a(7) = 15 = 1*1*1*2*2*(3/2)*(3/2)*(5/3). - Gary W. Adamson, Dec 13 2009
Number of permutations satisfying -k <= p(i) - i <= r and p(i)-i not in I, i=1..n, with k=1, r=3, I={1}. - Vladimir Baltic, Mar 07 2012
The 2-dimensional version, which counts sets of pairs no two of which are separated by graph-distance 2, is A273461. - Gus Wiseman, Nov 27 2019
a(n+1) is the number of multus bitstrings of length n with no runs of 4 ones. - Steven Finch, Mar 25 2020

			G.f. = 1 + x + x^2 + 2*x^3 + 4*x^4 + 6*x^5 + 9*x^6 + 15*x^7 + 25*x^8 + 40*x^9 + ...
From _Gus Wiseman_, Nov 27 2019: (Start)
The a(2) = 1 through a(7) = 15 subsets with no two elements differing by 2:
  {}  {}   {}     {}     {}     {}
      {1}  {1}    {1}    {1}    {1}
           {2}    {2}    {2}    {2}
           {1,2}  {3}    {3}    {3}
                  {1,2}  {4}    {4}
                  {2,3}  {1,2}  {5}
                         {1,4}  {1,2}
                         {2,3}  {1,4}
                         {3,4}  {1,5}
                                {2,3}
                                {2,5}
                                {3,4}
                                {4,5}
                                {1,2,5}
                                {1,4,5}
(End)

E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see pp. 157 and 172.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024. See pp. 16, 18.
D. Applegate, M. LeBrun, and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
Said Amrouche and Hacène Belbachir, Unimodality and linear recurrences associated with rays in the Delannoy triangle, Turkish Journal of Mathematics (2019) Vol. 44, 118-130.
Joerg Arndt, Matters Computational (The Fxtbook), section 14.10.1, p.320.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135.
V. Baltic, Applications of the finite state automata for counting restricted permutations and variations, Yug. J. Oper. Res. 22 (2012) 183-198, Sec. 3
G. E. Bergum and V. E. Hoggatt, Jr., A combinatorial problem involving recursive sequences and tridiagonal matrices, Fib. Quart., 16 (1978), 113-118.
M. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461.
K. Edwards, A Pascal-like triangle related to the tribonacci numbers, Fib. Q., 46/47 (2008/2009), 18-25.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
T. Guardia and D. Jiménez, Fiboquadratic Sequences and Extensions of the Cassini Identity Raised From the Study of Rithmomachia, arXiv preprint arXiv:1509.03177 [math.HO], 2015-2016.
John Konvalina, Yi-Hsin Liu, subsets without q-separation and binomial products of Fibonacci numbers, J. Comb. Theo. A 57 (2) (1991) 306-310, T_n.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
M. Tetiva, Subsets that make no difference d, Mathematics Magazine 84 (2011), no. 4, 300-301.
Dominika Závacká, Cristina Dalfó, and Miquel Angel Fiol, Integer sequences from k-iterated line digraphs, CEUR: Proc. 24th Conf. Info. Tech. - Appl. and Theory (ITAT 2024) Vol 3792, 156-161. See p. 161, Table 2.
Index entries for sequences related to Chebyshev polynomials.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,1,1).

Cf. A060945 (for 1's, 2's and 4's). Essentially the same as A074677.
Diagonal sums of number triangle A059259.
Cf. A000032, A000034, A000045, A001654, A007598, A209398.
Numbers whose binary expansion has no subsequence (1,0,1) are A048716.
Cf. A003242, A005251, A027383, A167606, A261041, A273461, A329860, A329871.

a006498 n = a006498_list !! n
a006498_list = 1 : 1 : 1 : 2 : zipWith (+) (drop 3 a006498_list)
   (zipWith (+) (tail a006498_list) a006498_list)
-- Reinhard Zumkeller, Apr 07 2012

[ n eq 1 select 1 else n eq 2 select 1 else n eq 3 select 1 else n eq 4 select 2 else Self(n-1)+Self(n-3)+ Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 20 2011

LinearRecurrence[{1,0,1,1},{1,1,1,2},50] (* Harvey P. Dale, Jul 13 2011 *)
Table[Fibonacci[Floor[n/2] + 2]^Mod[n, 2]*Fibonacci[Floor[n/2] + 1]^(2 - Mod[n, 2]), {n, 0, 40}] (* David Nacin, Feb 29 2012 *)
a[ n_] := Fibonacci[ Quotient[ n+2, 2]] Fibonacci[ Quotient[ n+3, 2]] (* Michael Somos, Jan 19 2014 *)
Table[Length[Select[Subsets[Range[n]],!MatchQ[#,{_,x_,_,y_,_}/;x+2==y]&]],{n,10}] (* Gus Wiseman, Nov 27 2019 *)

{a(n) = fibonacci( (n+2)\2 ) * fibonacci( (n+3)\2 )} /* Michael Somos, Mar 10 2004 */

PARI
```
Vec(1/(1-x-x^3-x^4)+O(x^66))
```

def a(n, adict={0:1, 1:1, 2:1, 3:2}):
    if n in adict:
        return adict[n]
    adict[n]=a(n-1)+a(n-3)+a(n-4)
    return adict[n] # David Nacin, Mar 07 2012

G.f.: 1 / ((1 + x^2) * (1 - x - x^2)); a(2*n) = F(n+1)^2, a(2*n - 1) = F(n+1)*F(n). a(n) = a(-4-n) * (-1)^n. - Michael Somos, Mar 10 2004
The g.f. -(1+z+2*z^2+z^3)/((z^2+z-1)*(1+z^2)) for the truncated version 1, 2, 4, 6, 9, 15, 25, 40, ... was given in the Simon Plouffe thesis of 1992. [edited by R. J. Mathar, May 13 2008]
From Vladeta Jovovic, May 03 2002: (Start)
a(n) = round((-(1/5)*sqrt(5) - 1/5)*(-2*1/(-sqrt(5)+1))^n/(-sqrt(5)+1) + ((1/5)*sqrt(5) - 1/5)*(-2*1/( sqrt(5)+1))^n/(sqrt(5)+1)).
G.f.: 1/(1-x-x^2)/(1+x^2). (End)
a(n) = (-i)^n*Sum{k=0..n} U(n-2k, i/2) where i^2=-1. - Paul Barry, Nov 15 2003
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*F(n-2k+1). - Paul Barry, Oct 12 2007
F(floor(n/2) + 2)^(n mod 2)*F(floor(n/2) + 1)^(2 - (n mod 2)) where F(n) is the n-th Fibonacci number. - David Nacin, Feb 29 2012
a(2*n - 1) = A001654(n), a(2*n) = A007598(n+1). - Michael Somos, Mar 10 2004
a(n+1)*a(n+3) = a(n)*a(n+2) + a(n+1)*a(n+2) for all n in Z. - Michael Somos, Jan 19 2014
a(n) = round(1/(1/F(n+2) + 2/F(n+3))), where F(n) = A000045, and 0.5 is rounded to 1. - Richard R. Forberg, Aug 04 2014
5*a(n) = (-1)^floor(n/2)*A000034(n+1) + A000032(n+2). - R. J. Mathar, Sep 16 2017
a(n) = Sum_{j=0..floor(n/3)} Sum_{k=0..j} binomial(n-3j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 18 2017
E.g.f.: (2*cos(x) + sin(x) + exp(x/2)*(3*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Mar 12 2024

A319416 Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to the empty string.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 2, 3, 3, 3, 4, 5, 5, 4, 3, 3, 3, 2, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 2, 3, 4, 3, 3, 3, 4, 4, 4, 5, 6, 6, 5, 4, 4, 4, 3, 3, 3, 4, 3, 2, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2

Offset: 0

N. J. A. Sloane, Sep 21 2018

Here we are using Lenormand's "raboter" map in a stricter sense than in A318921 and A319419. If S is a binary string with successive runs of lengths b,c,d,e,..., the "raboter" map sends S to the binary string with successive runs of lengths b-1,c-1,d-1,e-1,... Runs of length 0 are omitted (they are indicated by dots in the examples below).
To get a(n), start with S equal to the binary expansion of n beginning with the most significant bit, and keep applying the map until we reach the empty string.
After the first step, the string may start with a string of 0's: this is acceptable because we are working with strings, not binary expansions of numbers.
For example, 34 = 100010 -> .00.. = 00 -> 0. = 0 -> . (the empty string), taking 3 steps, so a(34) = 3.
Note: this is not the same as the number of applications of the map k -> A318921(k) needed to reduce the binary expansion of n to zero (because A318921 does not distinguish between 0 and the empty string).
This is also not the same as the number of applications of the map k -> A319419(k) needed to reduce the binary expansion of n to -1 (because A319419 does not distinguish between a string of 0's and a single 0).
The value k appears for the first time when n = 2^k - 1.

			n: repeatedly applying the map / number of steps = a(n)
0: 0 -> . / 1
1: 1 -> . / 1
2: 10 -> . / 1
3: 11 -> 1 -> . / 2
4: 100 -> 0 -> . / 2
5: 101 -> . / 1
6: 110 -> 1 -> . / 2
7: 111 -> 11 -> 1 -> . / 3
8: 1000 -> 00 -> 0 -> . / 3
9: 1001 -> 0 -> . / 2
10: 1010 -> . / 1
11: 1011 -> 1 -> . / 2
12: 1100 -> 10 -> . / 2
...

Rémy Sigrist, Table of n, a(n) for n = 0..16384
Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003.
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)

Positions of 1's are A000975.
Positions of 2's are A329862.
The version for runs-resistance is A318928.
The version for compositions is A329861.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A318921, A319411, A319419, A319420, A329744, A329767, A329863, A329865.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[degdep[IntegerDigits[n,2]],{n,0,50}] (* Gus Wiseman, Nov 25 2019 *)

a(n) = my (b=binary(n), w=#b); for (k=1, oo, my (ww=0); for (i=2, w, if (b[i-1]==b[i], b[ww++]=b[i])); if (ww==0, return (k), w=ww)) \\ Rémy Sigrist, Sep 23 2018

More terms from Rémy Sigrist, Sep 23 2018

A329861 Triangle read by rows where T(n,k) is the number of compositions of n with cuts-resistance k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 3, 0, 1, 0, 4, 3, 0, 1, 0, 7, 6, 2, 0, 1, 0, 14, 9, 6, 2, 0, 1, 0, 23, 22, 10, 6, 2, 0, 1, 0, 39, 47, 22, 10, 7, 2, 0, 1, 0, 71, 88, 52, 24, 10, 8, 2, 0, 1, 0, 124, 179, 101, 59, 26, 11, 9, 2, 0, 1, 0, 214, 354, 220, 112, 71, 28, 12, 10, 2, 0, 1

Offset: 0

Gus Wiseman, Nov 23 2019

A composition of n is a finite sequence of positive integers summing to n.

For the operation of shortening all runs by 1, cuts-resistance is defined as the number of applications required to reach an empty word.

			Triangle begins:
  1
  0  1
  0  1  1
  0  3  0  1
  0  4  3  0  1
  0  7  6  2  0  1
  0 14  9  6  2  0  1
  0 23 22 10  6  2  0  1
  0 39 47 22 10  7  2  0  1
  0 71 88 52 24 10  8  2  0  1
Row n = 6 counts the following compositions (empty columns not shown):
  (6)     (33)    (222)    (11112)  (111111)
  (15)    (114)   (1113)   (21111)
  (24)    (411)   (3111)
  (42)    (1122)  (11121)
  (51)    (1131)  (11211)
  (123)   (1221)  (12111)
  (132)   (1311)
  (141)   (2112)
  (213)   (2211)
  (231)
  (312)
  (321)
  (1212)
  (2121)

Row sums are A000079.
Column k = 1 is A003242 (for n > 0).
Column k = 2 is A329863.
Row sums without the k = 1 column are A261983.
The version for runs-resistance is A329744.
The version for binary vectors is A329860.
The cuts-resistance of the binary expansion of n is A319416.
Cf. A175342, A240085, A319411, A319420, A319421, A329738, A329862, A329865.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]==k&]],{n,0,10},{k,0,n}]

A319421 Triangle read by rows: T(n,k) (1 <= k <= n) = one-half of the number of binary vectors of length n and cuts-resistance k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 6, 6, 2, 1, 1, 10, 11, 7, 2, 1, 1, 14, 24, 14, 8, 2, 1, 1, 22, 42, 35, 16, 9, 2, 1, 1, 30, 81, 68, 45, 18, 10, 2, 1, 1, 46, 138, 149, 89, 55, 20, 11, 2, 1, 1, 62, 250, 282, 216, 110, 66, 22, 12, 2, 1, 1, 94, 419, 577, 422, 285, 132, 78, 24, 13, 2, 1

Offset: 1

N. J. A. Sloane, Sep 23 2018

Cuts-resistance is defined in A319416.
This triangle summarizes the data shown in A319420.
Conjecture (Sloane): Sum_{i = 1..n} i * T(n,i) = A189391(n).

			Triangle begins:
   1
   1   1
   1   2   1
   1   4   2   1
   1   6   6   2   1
   1  10  11   7   2   1
   1  14  24  14   8   2   1
   1  22  42  35  16   9   2   1
   1  30  81  68  45  18  10   2   1
   1  46 138 149  89  55  20  11   2   1
   1  62 250 282 216 110  66  22  12   2   1
   1  94 419 577 422 285 132  78  24  13   2   1
Lenormand gives first 15 rows.
For example, the "1,2,1" row here refers to the 8 vectors of length 3. There are 2 vectors of cuts-resistance 1, namely 010 and 101 (see A319416), 4 vectors of cuts-resistance 2 (100,011,001,110), and 2 of cuts-resistance 3 (000 and 111). Halving these counts we get 1,2,1

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. See page 4.
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)

Row sums are A000079.
Column k = 2 appears to be A027383.
The version for runs-resistance is A319411 or A329767.
The version for compositions is A329861.
The cuts-resistance of the binary expansion of n is A319416(n).
Cf. A000975, A164707, A189391, A261983, A318921, A318928, A319420, A329738, A329860, A329865.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Tuples[{0,1},n],First[#]==1&°dep[#]==k&]],{n,8},{k,n}] (* Gus Wiseman, Nov 25 2019 *)

T(n,k) = A329860(n,k)/2. - Gus Wiseman, Nov 25 2019

A329865 Numbers whose binary expansion has the same runs-resistance as cuts-resistance.

Original entry on oeis.org

0, 8, 12, 14, 17, 24, 27, 28, 35, 36, 39, 47, 49, 51, 54, 57, 61, 70, 73, 78, 80, 99, 122, 130, 156, 175, 184, 189, 190, 198, 204, 207, 208, 215, 216, 226, 228, 235, 243, 244, 245, 261, 271, 283, 295, 304, 313, 321, 322, 336, 352, 367, 375, 378, 379, 380, 386

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

For the operation of taking the sequence of run-lengths of a finite sequence, runs-resistance is defined to be the number of applications required to reach a singleton.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The sequence of terms together with their binary expansions begins:
    0:
    8:      1000
   12:      1100
   14:      1110
   17:     10001
   24:     11000
   27:     11011
   28:     11100
   35:    100011
   36:    100100
   39:    100111
   47:    101111
   49:    110001
   51:    110011
   54:    110110
   57:    111001
   61:    111101
   70:   1000110
   73:   1001001
   78:   1001110
   80:   1010000
For example, 36 has runs-resistance 3 because we have (100100) -> (1212) -> (1111) -> (4), while the cuts-resistance is also 3 because we have (100100) -> (00) -> (0) -> ().
Similarly, 57 has runs-resistance 3 because we have (111001) -> (321) -> (111) -> (3), while the cuts-resistance is also 3 because we have (111001) -> (110) -> (1) -> ().

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Positions of 0's in A329867.
The version for runs-resistance equal to cuts-resistance minus 1 is A329866.
Compositions with runs-resistance equal to cuts-resistance are A329864.
Runs-resistance of binary expansion is A318928.
Cuts-resistance of binary expansion is A319416.
Compositions counted by runs-resistance are A329744.
Compositions counted by cuts-resistance are A329861.
Binary words counted by runs-resistance are A319411 and A329767.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A107907, A164707, A319420, A329738, A329868.

runsres[q_]:=Length[NestWhileList[Length/@Split[#]&,q,Length[#]>1&]]-1;
degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Select[Range[0,100],#==0||runsres[IntegerDigits[#,2]]==degdep[IntegerDigits[#,2]]&]

A319420 Irregular triangle read by rows: row n lists the cuts-resistances of the 2^n binary vectors of length n.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 2, 1, 2, 2, 1, 2, 3, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 5, 4, 3, 3, 3, 2, 2, 3, 3, 2, 1, 2, 2, 2, 3, 4, 4, 3, 2, 2, 2, 1, 2, 3, 3, 2, 2, 2, 3, 3, 3, 4, 5

Offset: 0

N. J. A. Sloane, Sep 22 2018

The cuts-resistance of a vector is defined in A319416. The 2^n vectors of length n are taken in lexicographic order.
Note that here the vectors can begin with either 0 or 1, whereas in A319416 only vectors beginning with 1 are considered (since there we are considering binary representations of numbers).
Conjecture: The row sums, halved, appear to match A189391.

			Triangle begins:
0,
1,1,
2,1,1,2,
3,2,1,2,2,1,2,3,
4,3,2,2,2,1,2,3,3,2,1,2,2,2,3,4,
5,4,3,3,3,2,2,3,3,2,1,2,2,2,3,4,4,3,2,2,2,1,2,3,3,2,2,2,3,3,3,4,5,
...

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003. Apparently unpublished. This is a scanned copy of the version that the author sent to me in 2003. See table on page 4.

Keeping the first digit gives A319416.
Positions of 1's are the terms > 1 of A061547 and A086893, all minus 1.
The version for runs-resistance is A329870.
Compositions counted by cuts-resistance are A329861.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A027383, A189391, A318921, A318928, A319411, A329767, A329862, A329865.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[degdep[Rest[IntegerDigits[n,2]]],{n,0,50}] (* Gus Wiseman, Nov 25 2019 *)

A329862 Positive integers whose binary expansion has cuts-resistance 2.

Original entry on oeis.org

3, 4, 6, 9, 11, 12, 13, 18, 19, 20, 22, 25, 26, 37, 38, 41, 43, 44, 45, 50, 51, 52, 53, 74, 75, 76, 77, 82, 83, 84, 86, 89, 90, 101, 102, 105, 106, 149, 150, 153, 154, 165, 166, 169, 171, 172, 173, 178, 179, 180, 181, 202, 203, 204, 205, 210, 211, 212, 213

Offset: 1

Gus Wiseman, Nov 23 2019

nonn

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The sequence of terms together with their binary expansions begins:
   3:      11
   4:     100
   6:     110
   9:    1001
  11:    1011
  12:    1100
  13:    1101
  18:   10010
  19:   10011
  20:   10100
  22:   10110
  25:   11001
  26:   11010
  37:  100101
  38:  100110
  41:  101001
  43:  101011
  44:  101100
  45:  101101
  50:  110010

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Positions of 2's in A319416.
Numbers whose binary expansion has cuts-resistance 1 are A000975.
Binary words with cuts-resistance 2 are conjectured to be A027383.
Compositions with cuts-resistance 2 are A329863.
Cuts-resistance of binary expansion without first digit is A319420.
Binary words counted by cuts-resistance are A319421 and A329860.
Compositions counted by cuts-resistance are A329861.
Cf. A107907, A114901, A164707, A318928, A319411, A329745, A329865, A329866.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Select[Range[100],degdep[IntegerDigits[#,2]]==2&]

A329863 Number of compositions of n with cuts-resistance 2.

Original entry on oeis.org

0, 0, 1, 0, 3, 6, 9, 22, 47, 88, 179, 354, 691, 1344, 2617, 5042, 9709, 18632, 35639, 68010, 129556, 246202, 467188, 885036, 1674211, 3163094, 5969022, 11251676, 21189382, 39867970, 74950464, 140798302, 264313039, 495861874, 929709687, 1742193854, 3263069271, 6108762316

Offset: 0

Gus Wiseman, Nov 23 2019

nonn

A composition of n is a finite sequence of positive integers summing to n.

For the operation of shortening all runs by 1, cuts-resistance is defined to be the number of applications required to reach an empty word.

			The a(2) = 1 through a(7) = 22 compositions (empty column not shown):
  (1,1)  (2,2)    (1,1,3)    (3,3)      (1,1,5)
         (1,1,2)  (1,2,2)    (1,1,4)    (1,3,3)
         (2,1,1)  (2,2,1)    (4,1,1)    (2,2,3)
                  (3,1,1)    (1,1,2,2)  (3,2,2)
                  (1,1,2,1)  (1,1,3,1)  (3,3,1)
                  (1,2,1,1)  (1,2,2,1)  (5,1,1)
                             (1,3,1,1)  (1,1,2,3)
                             (2,1,1,2)  (1,1,3,2)
                             (2,2,1,1)  (1,1,4,1)
                                        (1,4,1,1)
                                        (2,1,1,3)
                                        (2,1,2,2)
                                        (2,2,1,2)
                                        (2,3,1,1)
                                        (3,1,1,2)
                                        (3,2,1,1)
                                        (1,1,2,1,2)
                                        (1,1,2,2,1)
                                        (1,2,1,1,2)
                                        (1,2,2,1,1)
                                        (2,1,1,2,1)
                                        (2,1,2,1,1)

Claude Lenormand, Deux transformations sur les mots, Preprint, 5 pages, Nov 17 2003.

Column k = 2 of A329861.
Compositions with cuts-resistance 1 are A003242.
Compositions with runs-resistance 2 are A329745.
Numbers whose binary expansion has cuts-resistance 2 are A329862.
Binary words with cuts-resistance 2 are conjectured to be A027383.
Cuts-resistance of binary expansion is A319416.
Binary words counted by cuts-resistance are A319421 and A329860.
Cf. A000975, A003242, A032020, A114901, A240085, A261983, A319420, A329738, A329744, A329864.

degdep[q_]:=Length[NestWhileList[Join@@Rest/@Split[#]&,q,Length[#]>0&]]-1;
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],degdep[#]==2&]],{n,0,10}]

Ca(N) = {1/(1-sum(k=1, N, x^k/(1+x^k)))}
A_x(N) = {my(x='x+O('x^N)); concat([0,0],Vec(-1+(1+sum(m=1,N, Ca(N)*x^(2*m)*(Ca(N)-1)/(1+x^m*(2+x^m*(1+Ca(N))))))/(1-sum(m=1,N, Ca(N)*x^(2*m)/(1+x^m*(2+x^m*(1+Ca(N))))))))}
A_x(38) \\ John Tyler Rascoe, Feb 20 2025

G.f.: -1 + (1 + Ca(x) * Sum_{m>0} x^(2*m) * (Ca(x)-1)/(1 + x^m * (2 + x^m * (1+Ca(x)))))/(1 - Ca(x) * Sum_{m>0} x^(2*m)/(1 + x^m * (2 + x^m * (1+Ca(x))))) where Ca(x) is the g.f. for A003242. - John Tyler Rascoe, Feb 20 2025

a(21) onwards from John Tyler Rascoe, Feb 20 2025

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

A318928 Runs-resistance of binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A006498 a(n) = a(n-1) + a(n-3) + a(n-4), a(0) = a(1) = a(2) = 1, a(3) = 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Mathematica

PARI

PARI

Python

Formula

A319416 Cuts-resistance of n: number of applications of Lernormand's "raboter" map needed to transform the binary expansion of n to the empty string.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A329861 Triangle read by rows where T(n,k) is the number of compositions of n with cuts-resistance k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A319421 Triangle read by rows: T(n,k) (1 <= k <= n) = one-half of the number of binary vectors of length n and cuts-resistance k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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