A088748 -id:A088748 - cp's OEIS frontend

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 2, 3, 4, 3, 4, 5, 4, 3, 2, 3, 4, 3, 2, 3, 2, 1, 2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5, 6, 7, 6, 5, 4, 5, 6, 5, 4, 5

Offset: 0

N. J. A. Sloane, Jeffrey Shallit, Simon Plouffe

Starting with a(1) = 0 mirror all initial 2^k segments and increase by one.
a(n) gives the net rotation (measured in right angles) after taking n steps along a dragon curve. - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
This sequence generates A082410: (0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, ...) and A014577; identical to the latter except starting 1, 1, 0, ...; by writing a "1" if a(n+1) > a(n); if not, write "0". E.g., A014577(2) = 0, since a(3) < a(2), or 1 < 2. - Gary W. Adamson, Sep 20 2003
Starting with 1 = partial sums of A034947: (1, 1, -1, 1, 1, -1, -1, 1, 1, 1, ...). - Gary W. Adamson, Jul 23 2008
The composer Per Nørgård's name is also written in the OEIS as Per Noergaard.
Can be used as a binomial transform operator: Let a(n) = the n-th term in any S(n); then extract 2^k strings, adding the terms. This results in the binomial transform of S(n). Say S(n) = 1, 3, 5, ...; then we obtain the strings: (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), ...; = the binomial transform of (1, 3, 5, ...) = (1, 4, 12, 32, 80, ...). Example: the 8-bit string has a sum of 32 with a distribution of (1, 3, 3, 1) or one 1, three 3's, three 5's, and one 7; as expected. - Gary W. Adamson, Jun 21 2012
Considers all positive odd numbers as nodes of a graph. Two nodes are connected if and only if the sum of the two corresponding odd numbers is a power of 2. Then a(n) is the distance between 2n + 1 and 1. - Jianing Song, Apr 20 2019

			Considered as a triangle with 2^k terms per row, the first few rows are:
  1
  2, 1
  2, 3, 2, 1
  2, 3, 4, 3, 2, 3, 2, 1
  ...
The n-th row becomes right half of next row; left half is mirrored terms of n-th row increased by one. - _Gary W. Adamson_, Jun 20 2012

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..10000
Joerg Arndt, Matters Computational (The Fxtbook).
J.-P. Allouche, G.-N. Han and J. Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Danielle Cox and Karyn McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted with addendum in Donald E. Knuth, Selected Papers on Fun and Games, 2010, pages 571-614. Equation 3.2 g(n) = a(n-1).
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
P. Flajolet et al., Mellin Transforms And Asymptotics: Digital Sums, Theoret. Computer Sci. 23 (1994), 291-314.
P. Flajolet and Lyle Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142-158.
Sara Kropf and Stephan Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
Sara Kropf and S. Wagner, On q-Quasiadditive and q-Quasimultiplicative Functions, arXiv preprint arXiv:1608.03700 [math.CO], 2016.
Shuo Li, Palindromic length sequence of the ruler sequence and of the period-doubling sequence, arXiv:2007.08317 [math.CO], 2020.
Helmut Prodinger and Friedrich J. Urbanek, Infinite 0-1-Sequences Without Long Adjacent Identical Blocks, Discrete Mathematics, volume 28, issue 3, 1979, pages 277-289. Also first author's copy. Their "variation" v(k) at definition 3.4 is a(k).
Jeffrey Shallit, The mathematics of Per Noergaard's rhythmic infinity system, Fib. Q., 43 (2005), 262-268.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions.
Index entries for "core" sequences.
Index entries for sequences related to binary expansion of n.

Cf. A037834 (-1), A088748 (+1), A246960 (mod 4), A034947 (first differences), A000975 (indices of record highs), A173318 (partial sums).
Cf. A056539, A014707, A014577, A082410, A030308, A090079, A044813, A165413, A226227, A226228, A226229.
Partial sums of A112347. Recursion depth of A035327.
Cf. A000120, A003188.

import Data.List (group)
a005811 0 = 0
a005811 n = length $ group $ a030308_row n
a005811_list = 0 : f [1] where
   f (x:xs) = x : f (xs ++ [x + x `mod` 2, x + 1 - x `mod` 2])
-- Reinhard Zumkeller, Feb 16 2013, Mar 07 2011

A005811 := proc(n)
    local i, b, ans;
    if n = 0 then
        return 0 ;
    end if;
    ans := 1;
    b := convert(n, base, 2);
    for i from nops(b)-1 to 1 by -1 do
        if b[ i+1 ]<>b[ i ] then
            ans := ans+1
        fi
    od;
    return ans ;
end proc:
seq(A005811(i), i=1..50) ;
# second Maple program:
a:= n-> add(i, i=Bits[Split](Bits[Xor](n, iquo(n, 2)))):
seq(a(n), n=0..100);  # Alois P. Heinz, Feb 01 2023

Table[ Length[ Length/@Split[ IntegerDigits[ n, 2 ] ] ], {n, 1, 255} ]
a[n_] := DigitCount[BitXor[n, Floor[n/2]], 2, 1]; Array[a, 100, 0] (* Amiram Eldar, Jul 11 2024 *)

a(n)=sum(k=1,n,(-1)^((k/2^valuation(k,2)-1)/2))

a(n)=if(n<1,0,a(n\2)+(a(n\2)+n)%2) \\ Benoit Cloitre, Jan 20 2014

a(n) = hammingweight(bitxor(n, n>>1));  \\ Gheorghe Coserea, Sep 03 2015

def a(n): return bin(n^(n>>1))[2:].count("1") # Indranil Ghosh, Apr 29 2017

a(2^k + i) = a(2^k - i + 1) + 1 for k >= 0 and 0 < i <= 2^k. - Reinhard Zumkeller, Aug 14 2001
a(2n+1) = 2a(n) - a(2n) + 1, a(4n) = a(2n), a(4n+2) = 1 + a(2n+1).
a(j+1) = a(j) + (-1)^A014707(j). - Christopher Hendrie (hendrie(AT)acm.org), Sep 11 2002
G.f.: (1/(1-x)) * Sum_{k>=0} x^2^k/(1+x^2^(k+1)). - Ralf Stephan, May 02 2003
Delete the 0, make subsets of 2^n terms; and reverse the terms in each subset to generate A088696. - Gary W. Adamson, Oct 19 2003
a(0) = 0, a(2n) = a(n) + [n odd], a(2n+1) = a(n) + [n even]. - Ralf Stephan, Oct 20 2003
a(n) = Sum_{k=1..n} (-1)^((k/2^A007814(k)-1)/2) = Sum_{k=1..n} (-1)^A025480(k-1). - Ralf Stephan, Oct 29 2003
a(n) = A069010(n) + A033264(n). - Ralf Stephan, Oct 29 2003
a(0) = 0 then a(n) = a(floor(n/2)) + (a(floor(n/2)) + n) mod 2. - Benoit Cloitre, Jan 20 2014
a(n) = A037834(n) + 1.
a(n) = A000120(A003188(n)). - Amiram Eldar, Jul 11 2024

Additional description from Wouter Meeussen

A014577 The regular paper-folding sequence (or dragon curve sequence). Alphabet {1,0}.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0

Offset: 0

N. J. A. Sloane, Eric W. Weisstein

a(n) is the complement of the bit to the left of the least significant "1" in the binary expansion of n+1. E.g., n = 3, n+1 = 4 = 100_2, so a(3) = (complement of bit to left of 1) = 1. - Robert L. Brown, Nov 28 2001 [Adjusted to match offset by N. J. A. Sloane, Apr 15 2021]
To construct the sequence: start from 1,(..),0,(..),1,(..),0,(..),1,(..),0,(..),1,(..),0,... and fill undefined places with the sequence itself. - Benoit Cloitre, Jul 08 2007
This is the characteristic function of A091072 - 1. - Gary W. Adamson, Apr 11 2010
Turns (by 90 degrees) of the Heighway dragon which can be rendered as follows: [Init] Set n=0 and direction=0. [Draw] Draw a unit line (in the current direction). Turn left/right if a(n) is zero/nonzero respectively. [Next] Set n=n+1 and goto (draw). See fxtbook link below. - Joerg Arndt, Apr 15 2010
Sequence can be obtained by the L-system with rules L->L1R, R->L0R, 1->1, 0->0, starting with L, and then dropping all L's and R's (see example). - Joerg Arndt, Aug 28 2011
From Gary W. Adamson, Jun 20 2012: (Start)
One half of the infinite Farey tree can be mapped one-to-one onto A014577 since both sequences can be derived directly from the binary. First few terms are
   1,   1,   0,   1,   1,   0,   0,   1,   1,   1, ...
  1/2  2/3  1/3  3/4  3/5  2/5  1/4  4/5  5/7  5/8, ...
Infinite Farey tree fractions can be derived from the binary by appending a repeat of rightmost binary term to the right, then recording the number of runs to obtain the continued fraction representation. Example: 9 = 1001 which becomes 10011 which becomes [1,2,2] = 5/7. (End)
The sequence can be considered as a binomial transform operator for a target sequence S(n). Replace the first 1 in A014577 with the first term in S(n), then for successive "1" term in A014577, map the next higher term in S(n). If "0" in A014577, map the next lower term in S(n). Using the sequence S(n) = (1, 3, 5, 7, ...), we obtain (1), (3, 1), (3, 5, 3, 1), (3, 5, 7, 5, 3, 5, 3, 1), .... Then parse the terms into subsequences of 2^k terms, adding the terms in each string.  We obtain (1, 4, 12, 32, 80, ...), the binomial transform of (1, 3, 5, 7, ...). The 8-bit string has one 1, three 5's, three 7's and one 1) as expected, or (1, 3, 3, 1) dot (1, 3, 5, 7). - Gary W. Adamson, Jun 24 2012
From Gary W. Adamson, May 29 2013: (Start)
The sequence can be generated directly from the lengths of continued fraction representations of fractions in one half of the Stern-Brocot tree (fractions between 0 and 1):
   1/2
   1/3 2/3
   1/4 2/5 3/5 3/4
   1/5 2/7 3/8 3/7 4/7 5/8 5/7 4/5
   ...
and their corresponding continued fraction representations are:
   [2]
   [3] [1,2]
   [4] [2,2] [1,1,2] [1,3]
   [5] [3,2] [2,1,2] [2,3] [1,1,3] [1,1,1,2] [1,2,2] [1,4]
   ...
Record the lengths by rows then reverse rows, getting:
   1,
   2, 1,
   2, 3, 2, 1,
   2, 3, 4, 3, 2, 3, 2, 1,
   ...
start with "1" and if the next term is greater than the current term, record a 1, otherwise 0; getting the present sequence, the Harter-Heighway dragon curve.  (End)
The paper-folding word "110110011100100111011000..." can be created by concatenating the terms of a fixed point of the morphism or string substitution rule: 00 -> 1000, 01 -> 1001, 10 -> 1100 & 11 -> 1101, beginning with "11". - Robert G. Wilson v, Jun 11 2015
From Gary W. Adamson, Jun 04 2021: (Start)
Since the Heighway dragon is composed of right angles, it can be mapped with unit trajectories (Right = 1, Left = (-1), Up = i and Down = -i) on the complex plane where i = sqrt(-1). The initial (0th) iterate is chosen in this case to be the unit line from (0,0) to (-1,0). Then follow the directions below as indicated, resulting in a reflected variant of the dragon curve shown at the Eric Weisstein link. The conjectured system of complex plane trajectories is:
  0   -1
  1   -1, i
  2   -1, i, 1, i
  3   -1, i, 1, i, 1, -i, 1, i
  4   -1, i, 1, i, 1, -i, 1, i, 1, -i, -1, -i, 1, -i, 1, i
  ...
The conjecture succeeds through the 4th iterate. It appears that to generate the (n+1)-th row, bring down the n-th row as the left half of row (n+1). For the right half of row (n+1), bring down the n-th row but change the signs of the first half of row n. For example, to get the complex plane instructions for the third iterate of the dragon curve, bring down (-1, i, 1, i) as the left half, and the right half is (1, -i, 1, i).  (End)
From Gary W. Adamson, Jun 09 2021: (Start)
Partial sums of the iterate trajectories produce a sequence of complex addresses for unit segments. Partial sums of row 4 are:  -1, (-1+i), i, 2i, (1+2i), (1+i), (2+i), (2+2i), (3+2i), (3+i), (2+i), 2, 3, (3-i), (4-i), 4. (zeros are omitted with terms of the form a+0i).  The reflected variant of the dragon curve has the 0th iterate from (0,0) to (1,0), and the respective addresses simply change the signs of the real terms.  (End)

			1 + x + x^3 + x^4 + x^7 + x^8 + x^9 + x^12 + x^15 + x^16 + x^17 + x^19 + ...
From _Joerg Arndt_, Aug 28 2011: (Start)
Generation via string substitution:
Start: L
Rules:
  L --> L1R
  R --> L0R
  0 --> 0
  1 --> 1
-------------
0:   (#=1)
  L
1:   (#=3)
  L1R
2:   (#=7)
  L1R1L0R
3:   (#=15)
  L1R1L0R1L1R0L0R
4:   (#=31)
  L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R
5:   (#=63)
  L1R1L0R1L1R0L0R1L1R1L0R0L1R0L0R1L1R1L0R1L1R0L0R0L1R1L0R0L1R0L0R
Drop all L and R to obtain 1101100111001001110110001100100
(End)

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted in Donald E. Knuth, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614.
Michel Dekking, Michel Mendes France, and Alf van der Poorten, "Folds", The Mathematical Intelligencer, 4.3 (1982): 130-138 & front cover, and 4:4 (1982): 173-181 (printed in two parts).
Martin Gardner, Mathematical Magic Show, New York: Vintage, pp. 207-209 and 215-220, 1978.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Ivan Panchenko, Table of n, a(n) for n = 0..10000
Ibrahim M. Alabdulmohsin, "Analytic Summability Theory", in Summability Calculus: A Comprehensive Theory of Fractional Finite Sums, Springer, Cham, pp 65-91.
Jean-Paul Allouche and Michel Mendès France, Automata and Automatic Sequences, in: F. Axel and D. Gratias (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
Jean-Paul Allouche and Michel Mendès France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
Joerg Arndt, Matters Computational (The Fxtbook), pp. 88-92; image of the dragon curve on p. 89.
Paul Barry, Conjectures and results on some generalized Rueppel sequences, arXiv:2107.00442 [math.CO], 2021.
Michael Coons, An Irrationality Measure for Regular Paperfolding Numbers, Journal of Integer Sequences, Vol. 15 (2012), Article #12.1.6.
Danielle Cox and K. McLellan, A problem on generation sets containing Fibonacci numbers, Fib. Quart., 55 (No. 2, 2017), 105-113.
Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. [Cached copy, with permission]
Alexey Garber, On triangular paperfolding patterns, arXiv:1807.05627 [math.CO], 2018.
Franz Gahler and Johan Nilsson, Substitution rules for higher-dimensional paperfolding structures, arXiv:1408.4997 [math.DS], 2014.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 63. Book's website
Eve Kivivuori, Implementing, analyzing, and benchmarking the Relative Lempel-Ziv compression algorithm, Master's Thesis, Univ. Helsinki (Finland 2023).
Guy Melançon, Factorizing infinite words using Maple, MapleTech journal, (14 Mb) vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
Johan Nilsson, The Pattern Complexity of the 2-Dimensional Paperfolding Sequence, arXiv:2409.03068 [math.CO], 2024. See p. 1.
Larry Riddle, Heighway Dragon, Classic Iterated Function Systems.
Luke Schaeffer and Jeffrey Shallit, Closed, Palindromic, Rich, Privileged, Trapezoidal, and Balanced Words in Automatic Sequences, Electronic Journal of Combinatorics 23(1) (2016), #P1.25.
Joshua E. S. Socolar and Joan M. Taylor, An aperiodic hexagonal tile, arXiv:1003.4279 [math.CO], 2010.
László Tóth, Evaluating zeta(s) At Odd Positive Integers Using Automatic Dirichlet Series, arXiv:2508.04151 [math.NT], 2025.
Eric Weisstein's World of Mathematics, Dragon curve.
Hans Zantema, Complexity of Automatic Sequences, International Conference on Language and Automata Theory and Applications (LATA 2020): Language and Automata Theory and Applications, 260-271.
Index entries for 2-automatic sequences.
Index entries for sequences obtained by enumerating foldings.
Index entries for sequences related to binary expansion of n.

Essentially the same: A014707, A014709, A014710, A034947, A038189, A082410, A089013, A099545, A112347, A121238, A317335, A317336.
Cf. A059125, A065339, A005811, A220466, A088748, A091072, A343173 (first differences), A343174 (partial sums).
The two bisections are A000035 and the sequence itself.
See A343181 for prefixes of length 2^k-1.

[(1+KroneckerSymbol(-1,n))/2: n in [1..100]]; // Vincenzo Librandi, Aug 05 2015

[Floor(1/2*(1+(-1)^(1/2*((n+1)/2^Valuation(n+1, 2)-1)))): n in [0..100]]; // Vincenzo Librandi, Aug 05 2015

nmax:=98: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 0 to ceil(nmax/(p+2))+1 do a((2*n+1)*2^p-1) := (n+1) mod 2 od: od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Jan 28 2013
a014577 := proc(n) local p,s1,s2,i;
if n=0 then return(1); fi;
s1:=convert(n,base,2); s2:=nops(s1);
for i from 1 to s2 do if s1[i]=1 then p:=i; break; fi; od:
if p <= s2-1 then 1-s1[p+1]; else 1; fi; end;
[seq(a014577(i),i=1..120)]; # N. J. A. Sloane, Apr 08 2021
# third Maple program:
a:= n-> 1-irem(iquo((n+1)/2^padic[ordp](n+1, 2), 2), 2):
seq(a(n), n=0..120);  # Alois P. Heinz, Apr 08 2021

a[n_] := Boole[EvenQ[((n+1)/2^IntegerExponent[n+1, 2]-1)/2]]; Table[a[n], {n, 0, 98}] (* Jean-François Alcover, Feb 16 2012, after Gary W. Adamson, updated Nov 21 2014 *)
Table[1-(((Mod[#1,2^(#2+2)]/2^#2)&[n,IntegerExponent[n,2]])-1)/2,{n,1,100,1}] (* WolframAlpha compatible code; Robert L. Brown, Jan 06 2015 *)
MapThread[(a[x_/;IntegerQ[(x-#1)/4]]:= #2)&,{{1,3},{1,0}}];a[x_/;IntegerQ[x/2]]:=a[x/2];a/@ Range[100] (* Bradley Klee, Aug 04 2015 *)
(1 + JacobiSymbol[-1, Range[100]])/2 (* Paolo Xausa, May 22 2024 *)
Array[Boole[BitAnd[#, BitAnd[#, -#]*2] == 0] &, 100] (* Paolo Xausa, May 22 2024, after Joerg Arndt C++ code *)

{a(n) = if( n%2, a(n\2), 1 - (n/2%2))} /* Michael Somos, Feb 05 2012 */

a(n)=1/2*(1+(-1)^(1/2*((n+1)/2^valuation(n+1,2)-1))) \\ Ralf Stephan, Sep 02 2013

a(n)=!bittest(n+1,valuation(n+1,2)+1); \\ Robert L. Brown, Jul 07 2025

def A014577(n):
    s = bin(n+1)[2:]
    m = len(s)
    i = s[::-1].find('1')
    return 1-int(s[m-i-2]) if m-i-2 >= 0 else 1 # Chai Wah Wu, Apr 08 2021

a(n) = (1+Jacobi(-1,n+1))/2 (cf. A034947). - N. J. A. Sloane, Jul 27 2012 [Adjusted to match offset by Peter Munn, Jul 01 2022]
Set a=1, b=0, S(0)=a, S(n+1) = S(n), a, F(S(n)), where F(x) reverses x and then interchanges a and b; sequence is limit S(infinity).
From Ralf Stephan, Jul 03 2003: (Start)
a(4*n) = 1, a(4*n+2) = 0, a(2*n+1) = a(n).
a(n) = 1 - A014707(n) = 2 - A014709(n) = A014710(n) - 1. (End)
Set a=1, b=0, S(0)=a, S(n+1)=S(n), a, M(S(n)), where M(S) is S but the bit in the middle position flipped. (Proof via isomorphism of both formulas to a modified string substitution.) - Benjamin Heiland, Dec 11 2011
a(n) = 1 if A005811(n+1) > A005811(n), otherwise a(n) = 0. - Gary W. Adamson, Jun 20 2012
a((2*n+1)*2^p-1) = (n+1) mod 2, p >= 0. - Johannes W. Meijer, Jan 28 2013
G.f. g(x) satisfies g(x) = x*g(x^2) + 1/(1-x^4). - Robert Israel, Jan 06 2015
a(n) = 1 - A065339(n+1) mod 2. - Peter Munn, Jun 29 2022
From A.H.M. Smeets, Mar 19 2023: (Start)
a(n) = 1 - A038189(n+1).
a(n) = A082410(n+2).
a(n) = 1 - A089013(n+1)
a(n) = (3 - A099545(n+1))/2.
a(n) = (A112347(n+1) + 1)/2.
a(n) = (A121238(n+1) + 1)/2.
a(n) = (A317335(n) + 2)/3.
a(n) = (A317336(n) + 10)/3. (End)
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/2. - Amiram Eldar, Sep 14 2024

More terms from Ralf Stephan, Jul 03 2003

A088696 Triangle read by rows, giving number of partial quotients in continued fraction representation of terms in the left branch of the infinite Stern-Brocot tree.

Original entry on oeis.org

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

Offset: 1

Gary W. Adamson, Oct 07 2003

Each next row is the last row concatenated with the last row reversed with elements incremented. A000120 is produced by a similar principle, omitting the reversal step. [Edited by Andrey Zabolotskiy, Mar 27 2020]
From Gary W. Adamson, Aug 08 2009: (Start)
The row with 8 terms: (1, 2, 3, 2, 3, 4, 3, 2); can be used to generate the numbers of hydrogen bonds per codon/anti-codon; superimposed on the DNA codon array of A147995 as follows: top row and left column of an 8 X 8 array is composed of the 8 terms (1, 2, 3, 2, 3, 4, 3, 2). If rows and columns have an offset of "1", then odd rows circulate downward starting from the position (n,n). Even rows circulate in the opposite direction starting from position (n,n).
This produces the array:
  1 2 3 2 3 4 3 2
  2 1 2 3 4 3 2 3
  3 2 1 2 3 2 3 4
  2 3 2 1 2 3 2 3
  3 4 3 2 1 2 3 2
  4 3 2 3 2 1 4 3
  3 2 3 4 3 2 1 2
  2 3 4 3 2 3 2 1
  ...
This produces a semi-magic square with a diagonal of (1,1,1,...). Using the simple replacement rule ("complement to 10"): (1->9); (2->8); (3->7); (4->6) we obtain the chart of DNA hydrogen bonds per codon/anti-codon shown in A147995. Top row of the hydrogen bond array as well as left column = (9, 8, 7, 8, 7, 6, 7, 8).
Alternatively, using the circulant rule for alternate rows and putting all 9's along the diagonal, we obtain the chart of hydrogen bonds. (End)
Rows tend to A088748 (which can also be generated from the dragon curve, A014577). - Gary W. Adamson, Aug 30 2009
Positions of records are A081254. - Andrey Zabolotskiy, Mar 27 2020

			Fractions in the left branch of the infinite Stern-Brocot tree (the fractions between 0 and 1), are:
  1/2;
  1/3, 2/3;
  1/4, 2/5, 3/5, 3/4;
  1/5, 2/7, 3/8, 3/7, 4/7, 5/8, 5/7, 4/5;
  ...
and their corresponding continued fraction representations are:
  [2]
  [3] [1,2]
  [4] [2,2] [1,1,2] [1,3]
  [5] [3,2] [2,1,2] [2,3] [1,1,3] [1,1,1,2] [1,2,2] [1,4]
  ...
with the number of terms in each continued fraction representation generating the present triangle:
  1
  1 2
  1 2 3 2
  1 2 3 2 3 4 3 2
  ...

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 116-117.

Andrey Zabolotskiy, Table of n, a(n) for n = 1..8191

Cf. A000120, A007305, A007306.
Cf. A147995.
Cf. A088748, A014577.

a088696 n = a088696_list !! (n-1)
a088696_list = f [1] where
   f (x:xs) = x : f (xs ++ [x + 1 - x `mod` 2, x + x `mod` 2])
-- Reinhard Zumkeller, Mar 07 2011

sb[n_List] := Block[{k = l = Length[n], a = n}, While[k > 1, a = Insert[ a, (Numerator[ a[[k]]] + Numerator[ a[[k - 1]]]) / (Denominator[ a[[k]]] + Denominator[ a[[k - 1]]]), k]; k-- ]; a]; sbn[n_] := Complement[ Nest[ sb, {0, 1}, n], Nest[ sb, {0, 1}, n - 1]]; f[n_] := Length /@ (ContinuedFraction /@ sbn[n]) - 1; Flatten[ Table[ f[n], {n, 7}]] (* Robert G. Wilson v, Jun 09 2004 *)
Flatten[NestList[Join[#, Reverse[#] + 1] &, {1}, 7]]; (* from A164738, Jon Maiga, Sep 26 2019 *)

a = [[1]]
for n in range(6):
    a.append(a[-1] + [x+1 for x in a[-1][::-1]])
print(sum(a, []))
# Andrey Zabolotskiy, Mar 27 2020, after Jon Maiga

Edited and extended by Robert G. Wilson v, Jun 09 2004

cp's OEIS Frontend

A164910 Partial sums of A088748.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A005811 Number of runs in binary expansion of n (n>0); number of 1's in Gray code for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A014577 The regular paper-folding sequence (or dragon curve sequence). Alphabet {1,0}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A088696 Triangle read by rows, giving number of partial quotients in continued fraction representation of terms in the left branch of the infinite Stern-Brocot tree.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Extensions