A220466 -id:A220466 - cp's OEIS frontend

A001511 The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.

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

Offset: 1

N. J. A. Sloane

Number of 2's dividing 2*n.
a(n) is equivalently the exponent of the smallest power of 2 which does not divide n. - David James Sycamore, Oct 02 2023
a(n) - 1 is the number of trailing zeros in the binary expansion of n.
If you are counting in binary and the least significant bit is numbered 1, the next bit is 2, etc., a(n) is the bit that is incremented when increasing from n-1 to n. - Jud McCranie, Apr 26 2004
Number of steps to reach an integer starting with (n+1)/2 and using the map x -> x*ceiling(x) (cf. A073524).
a(n) is the number of the disk to be moved at the n-th step of the optimal solution to Towers of Hanoi problem (comment from Andreas M. Hinz).
Shows which bit to flip when creating the binary reflected Gray code (bits are numbered from the right, offset is 1). This is essentially equivalent to Hinz's comment. - Adam Kertesz, Jul 28 2001
a(n) is the Hamming distance between n and n-1 (in binary). This is equivalent to Kertesz's comments above. - Tak-Shing Chan (chan12(AT)alumni.usc.edu), Feb 25 2003
Let S(0) = {1}, S(n) = {S(n-1), S(n-1)-{x}, x+1} where x = last term of S(n-1); sequence gives S(infinity). - Benoit Cloitre, Jun 14 2003
The sum of all terms up to and including the first occurrence of m is 2^m-1. - Donald Sampson (marsquo(AT)hotmail.com), Dec 01 2003
m appears every 2^m terms starting with the 2^(m-1)th term. - Donald Sampson (marsquo(AT)hotmail.com), Dec 08 2003
Sequence read mod 4 gives A092412. - Philippe Deléham, Mar 28 2004
If q = 2n/2^A001511(n) and if b(m) is defined by b(0)=q-1 and b(m)=2*b(m-1)+1, then 2n = b(A001511(n)) + 1. - Gerald McGarvey, Dec 18 2004
Repeating pattern ABACABADABACABAE ... - Jeremy Gardiner, Jan 16 2005
Relation to C(n) = Collatz function iteration using only odd steps: a(n) is the number of right bits set in binary representation of A004767(n) (numbers of the form 4*m+3). So for m=A004767(n) it follows that there are exactly a(n) recursive steps where mBetween every two instances of any positive integer m there are exactly m distinct values (1 through m-1 and one value greater than m). - Franklin T. Adams-Watters, Sep 18 2006
Number of divisors of n of the form 2^k. - Giovanni Teofilatto, Jul 25 2007
Every prefix up to (but not including) the first occurrence of some k >= 2 is a palindrome. - Gary W. Adamson, Sep 24 2008
1 interleaved with (2 interleaved with (3 interleaved with ( ... ))). - Eric D. Burgess (ericdb(AT)gmail.com), Oct 17 2009
A054525 (Möbius transform) * A001511 = A036987 = A047999^(-1) * A001511. - Gary W. Adamson, Oct 26 2009
Equals A051731 * A036987, (inverse Möbius transform of the Fredholm-Rueppel sequence) = A047999 * A036987. - Gary W. Adamson, Oct 26 2009
Cf. A173238, showing links between generalized ruler functions and A000041. - Gary W. Adamson, Feb 14 2010
Given A000041, P(x) = A(x)/A(x^2) with P(x) = (1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + ...), A(x) = (1 + x + 3x^2 + 4x^3 + 10x^4 + 13x^5 + ...), A(x^2) = (1 + x^2 + 3x^4 + 4x^6 + 10x^8 + ...), where A092119 = (1, 1, 3, 4, 10, ...) = Euler transform of the ruler sequence, A001511. - Gary W. Adamson, Feb 11 2010
Subtracting 1 from every term and deleting any 0's yields the same sequence, A001511. - Ben Branman, Dec 28 2011
In the listing of the compositions of n as lists in lexicographic order, a(k) is the last part of composition(k) for all k <= 2^(n-1) and all n, see example. - Joerg Arndt, Nov 12 2012
According to Hinz, et al. (see links), this sequence was studied by Louis Gros in his 1872 pamphlet "Théorie du Baguenodier" and has therefore been called the Gros sequence.
First n terms comprise least squarefree word of length n using positive integers, where "squarefree" means that the word contains no consecutive identical subwords; e.g., 1 contains no square; 11 contains a square but 12 does not; 121 contains no square; both 1211 and 1212 have squares but 1213 does not; etc. - Clark Kimberling, Sep 05 2013
Length of 0-run starting from 2 (10, 100, 110, 1000, 1010, ...), or length of 1-run starting from 1 (1, 11, 101, 111, 1001, 1011, ...) of every second number, from right to left in binary representation. - Armands Strazds, Apr 13 2017
a(n) is also the frequency of the largest part in the integer partition having viabin number n. The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20. - Emeric Deutsch, Jul 24 2017
As A000005(n) equals the number of even divisors of 2n and A001227(n) = A001227(2n), the formula A001511(n) = A000005(n)/A001227(n) might be read as "The number of even divisors of 2n is always divisible by the number of odd divisors of 2n" (where number of divisors means sum of zeroth powers of divisors). Conjecture: For any nonnegative integer k, the sum of the k-th powers of even divisors of n is always divisible by the sum of the k-th powers of odd divisors of n. - Ivan N. Ianakiev, Jul 06 2019
From Benoit Cloitre, Jul 14 2022: (Start)
To construct the sequence, start from 1's separated by a place 1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,,1,...
Then put the 2's in every other remaining place
  1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,,1,2,1,...
Then the 3's in every other remaining place
  1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,,1,2,1,...
Then the 4's in every other remaining place
  1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,,1,2,1,3,1,2,1,4,1,2,1,...
By iterating this process, we get the ruler function 1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,... (End)
a(n) is the least positive integer k for which there does not exist i+j=n and a(i)=a(j)=k (cf. A322523). - Rémy Sigrist and Jianing Song, Aug 23 2022
a(n) is the smallest positive integer that does not occur in the coincidences of the sequence so far a(1..n-1) and its reverse. - Neal Gersh Tolunsky, Jan 18 2023
The geometric mean of this sequence approaches the Somos constant (A112302). - Jwalin Bhatt, Jan 31 2025

			For example, 2^1|2, 2^2|4, 2^1|6, 2^3|8, 2^1|10, 2^2|12, ... giving the initial terms 1, 2, 1, 3, 1, 2, ...
From _Omar E. Pol_, Jun 12 2009: (Start)
Triangle begins:
1;
2,1;
3,1,2,1;
4,1,2,1,3,1,2,1;
5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
6,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1;
7,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,...
(End)
S(0) = {} S(1) = 1 S(2) = 1, 2, 1 S(3) = 1, 2, 1, 3, 1, 2, 1 S(4) = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1. - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
From _Joerg Arndt_, Nov 12 2012: (Start)
The 16 compositions of 5 as lists in lexicographic order:
[ n]  a(n)  composition
[ 1]  [ 1]  [ 1 1 1 1 1 ]
[ 2]  [ 2]  [ 1 1 1 2 ]
[ 3]  [ 1]  [ 1 1 2 1 ]
[ 4]  [ 3]  [ 1 1 3 ]
[ 5]  [ 1]  [ 1 2 1 1 ]
[ 6]  [ 2]  [ 1 2 2 ]
[ 7]  [ 1]  [ 1 3 1 ]
[ 8]  [ 4]  [ 1 4 ]
[ 9]  [ 1]  [ 2 1 1 1 ]
[10]  [ 2]  [ 2 1 2 ]
[11]  [ 1]  [ 2 2 1 ]
[12]  [ 3]  [ 2 3 ]
[13]  [ 1]  [ 3 1 1 ]
[14]  [ 2]  [ 3 2 ]
[15]  [ 1]  [ 4 1 ]
[16]  [ 5]  [ 5 ]
a(n) is the last part in each list.
(End)
From _Omar E. Pol_, Aug 20 2013: (Start)
Also written as a triangle in which the right border gives A000027 and row lengths give A011782 and row sums give A000079 the sequence begins:
1;
2;
1,3;
1,2,1,4;
1,2,1,3,1,2,1,5;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6;
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,7;
(End)
G.f. = x + 2*x^2 + x^3 + 3*x^4 + x^5 + 2*x^6 + x^7 + 4*x^8 + x^9 + 2*x^10 + ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 2nd ed., 2001-2003; see Dim- and Dim+ on p. 98; Dividing Rulers, on pp. 436-437; The Ruler Game, pp. 469-470; Ruler Fours, Fives, ... Fifteens on p. 470.
L. Gros, Théorie du Baguenodier, Aimé Vingtrinier, Lyon, 1872.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section E22.
A. M. Hinz, The Tower of Hanoi, in Algebras and combinatorics (Hong Kong, 1997), 277-289, Springer, Singapore, 1999.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.1.3, Problem 41, p. 589.
Andrew Schloss, "Towers of Hanoi" composition, in The Digital Domain. Elektra/Asylum Records 9 60303-2, 1983. Works by Jaffe (Finale to "Silicon Valley Breakdown"), McNabb ("Love in the Asylum"), Schloss ("Towers of Hanoi"), Mattox ("Shaman"), Rush, Moorer ("Lions are Growing") and others.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
Joerg Arndt, Matters Computational (The Fxtbook), p. 9, pp. 733-734
Joerg Arndt, Subset-lex: did we miss an order?, arXiv:1405.6503 [math.CO], 2014.
B. Baker Swart, R. Florez, D. Narayan, and G. Rudolph Extrema Property of the k-Ranking of Directed Paths and Cycles, AKCE International Journal of Graphs and Combinatorics, 13 (2016) 38-53.
J. Britton, Tower of Hanoi Solution
Yann Bugeaud and Guo-Niu Han, A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence, Electronic Journal of Combinatorics 21(3) (2014), #P3.26. See G(z) in (1.1).
Antonin Callard, Léo Paviet Salomon, and Pascal Vanier, Computability of extender sets in multidimensional subshifts, arXiv:2401.07549 [cs.DM], 2024.
Imanuel Chen and Michael Z. Spivey, Integral Generalized Binomial Coefficients of Multiplicative Functions, Preprint 2015; Summer Research Paper 238, Univ. Puget Sound.
Vassili Daiev, Greatest divisors of even integers: Problem 636, Math. Mag., 40 (1967), 164-165.
P. Flajolet, J.-C. Raoult, and J. Vuillemin, The number of registers required for evaluating arithmetic expressions, Theoret. Comput. Sci. 9 (1979), no. 1, 99-125.
R. Florez and D. Narayan Maximizing the number of edges in optimal k-rankings, AKCE International Journal of Graphs and Combinatorics, 12.1 (2015) 1-8.
Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, The Star of David and Other Patterns in Hosoya Polynomial Triangles, J. Int. Seq., Vol. 21 (2018), Article 18.4.6, also arXiv:1706.04247 [math.CO], 2017.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 1, 2, 12, 24.
Fernando Q. Gouvêa, p-Adic Numbers, Springer-Verlag, 1993; see p. 23.
A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See 'The Gros Sequence', page 60. Book's website
Norbert Hungerbühler and Ernst Specker, A generalization of the Smarandache Function to several variables, INTEGERS 6 (2006) #A23. [See final section.]
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021. Section 1.1.2. p. 5.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
J. C. Lagarias and N. J. A. Sloane, Approximate squaring (pdf, ps), Experimental Math., 13 (2004), 113-128.
S. Legendre and P. Paclet, On the Permutations Generated by Cyclic Shift , J. Int. Seq. 14 (2011) # 11.3.2.
Subhayan Roy Moulik and Sergii Strelchuk, DQC1-hardness of estimating correlation functions, arXiv:2411.05208 [quant-ph], 2024. See p. 8.
Juan Carlos Nuño and Francisco J. Muñoz, On the ubiquity of the ruler sequence, arXiv:2009.14629 [math.HO], 2020.
Michael Naylor, Abacaba-Dabacaba [updated by _Jeremy Gardiner_, Sep 11 2015]
Juan Carlos Nuño and Francisco J. Muñoz, The Ruler Sequence Revisited: A Dynamic Perspective, Mathematics (2024) Vol. 12, No. 5, 742.
Simon Plouffe, On the values of the functions ... [zeta and Gamma] ..., arXiv preprint arXiv:1310.7195 [math.NT], 2013.
Joseph Rosenbaum, Elementary Problem E319, American Mathematical Monthly, volume 45, number 10, December 1938, pages 694-696. (The A indices in P at equations 1 and 2.)
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Dinesh Thakur, Gauss sums for function fields, J. Number Theory, Volume 37, Issue 2, February 1991, Pages 242-252.
Dinesh S. Thakur, Continued fraction for the exponential for F_q[T], Journal of Number Theory, 41.2 (1992): 150-155. See page 153.
Dinesh S. Thakur, Patterns of Continued Fractions for the Analogues of e and Related Numbers in the Function Field Case, Journal of Number Theory, 66.1 (1997): 129-147. See p. 130.
Eric Weisstein's World of Mathematics, Binary Carry Sequence, Ruler Function, and Towers of Hanoi
Index entries for "core" sequences
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings
Index entries for sequences related to Towers of Hanoi

Column 1 of table A050600.
Sequence read mod 2 gives A035263.
Sequence is bisection of A007814, A050603, A050604, A067029, A089309.
This is Guy Steele's sequence GS(4, 2) (see A135416).
Cf. A005187 (partial sums), A085058 (bisection), A112302 (geometric mean), A171977 (2^a(n)).
Cf. A000005, A000041, A000079, A003188, A003278, A003602, A007949, A018238, A047999, A051731, A054525, A054852, A065176, A082850, A089080, A092119, A117303, A129360, A130093, A173238, A181988, A220466.
Cf. A287896, A002487, A209229 (Mobius trans.), A092673 (Dirichlet inv.).
Cf. generalized ruler functions for k=3,4,5: A051064, A115362, A055457.

a001511 n = length $ takeWhile ((== 0) . (mod n)) a000079_list
-- Reinhard Zumkeller, Sep 27 2011

a001511 n | odd n = 1 | otherwise = 1 + a001511 (n `div` 2)
-- Walt Rorie-Baety, Mar 22 2013

nmax=5;r=1;for n=2:nmax;r=[r n r];end % Adriano Caroli, Feb 26 2016

[Valuation(2*n,2): n in [1..105]]; // Bruno Berselli, Nov 23 2015

A001511 := n->2-wt(n)+wt(n-1); # where wt is defined in A000120
# This is the binary logarithm of the denominator of (256^n-1)B_{8n}/n, in Maple parlance a := n -> log[2](denom((256^n-1)*bernoulli(8*n)/n)). - Peter Luschny, May 31 2009
A001511 := n -> padic[ordp](2*n,2): seq(A001511(n), n=1..105);  # Peter Luschny, Nov 26 2010
a:= n-> ilog2((Bits[Xor](2*n, 2*n-1)+1)/2): seq(a(n), n=1..50);  # Gary Detlefs, Dec 13 2018

Array[ If[ Mod[ #, 2] == 0, FactorInteger[ # ][[1, 2]], 0] &, 105] + 1 (* or *)
Nest[ Flatten[ # /. a_Integer -> {1, a + 1}] &, {1}, 7] (* Robert G. Wilson v, Mar 04 2005 *)
IntegerExponent[2*n, 2] (* Alexander R. Povolotsky, Aug 19 2011 *)
myHammingDistance[n_, m_] := Module[{g = Max[m, n], h = Min[m, n]}, b1 = IntegerDigits[g, 2]; b2 = IntegerDigits[h, 2, Length[b1]]; HammingDistance[b1, b2]] (* Vladimir Shevelev A206853 *) Table[ myHammingDistance[n, n - 1], {n, 111}] (* Robert G. Wilson v, Apr 05 2012 *)
Table[Position[Reverse[IntegerDigits[n,2]],1,1,1],{n,110}]//Flatten (* Harvey P. Dale, Aug 18 2017 *)

a(n) = sum(k=0,floor(log(n)/log(2)),floor(n/2^k)-floor((n-1)/2^k)) /* Ralf Stephan */

a(n)=if(n%2,1,factor(n)[1,2]+1) /* Jon Perry, Jun 06 2004 */

{a(n) = if( n, valuation(n, 2) + 1, 0)}; /* Michael Somos, Sep 30 2006 */

{a(n)=if(n==1,1,polcoeff(x-sum(k=1, n-1, a(k)*x^k*(1-x^k)*(1-x+x*O(x^n))), n))} /* Paul D. Hanna, Jun 22 2007 */

def a(n): return bin(n)[2:][::-1].index("1") + 1 # Indranil Ghosh, May 11 2017

A001511 = lambda n: (n&-n).bit_length() # M. F. Hasler, Apr 09 2020

def A001511(n): return (~n & n-1).bit_length()+1 # Chai Wah Wu, Jul 01 2022

[valuation(2*n,2) for n in (1..105)]  # Bruno Berselli, Nov 23 2015

(define (A001511 n) (let loop ((n n) (e 1)) (if (odd? n) e (loop (/ n 2) (+ 1 e))))) ;; Antti Karttunen, Oct 06 2017

a(n) = A007814(n) + 1 = A007814(2*n).
a(2*n+1) = 1; a(2*n) = 1 + a(n). - Philippe Deléham, Dec 08 2003
a(n) = 2 - A000120(n) + A000120(n-1), n >= 1. - Daniele Parisse
a(n) = 1 + log_2(abs(A003188(n) - A003188(n-1))).
Multiplicative with a(p^e) = e+1 if p = 2; 1 if p > 2. - David W. Wilson, Aug 01 2001
For any real x > 1/2: lim_{N->infinity} (1/N)*Sum_{n=1..N} x^(-a(n)) = 1/(2*x-1); also lim_{N->infinity} (1/N)*Sum_{n=1..N} 1/a(n) = log(2). - Benoit Cloitre, Nov 16 2001
s(n) = Sum_{k=1..n} a(k) is asymptotic to 2*n since s(n) = 2*n - A000120(n). - Benoit Cloitre, Aug 31 2002
For any n >= 0, for any m >= 1, a(2^m*n + 2^(m-1)) = m. - Benoit Cloitre, Nov 24 2002
a(n) = Sum_{d divides n and d is odd} mu(d)*tau(n/d). - Vladeta Jovovic, Dec 04 2002
G.f.: A(x) = Sum_{k>=0} x^(2^k)/(1-x^(2^k)). - Ralf Stephan, Dec 24 2002
a(1) = 1; for n > 1, a(n) = a(n-1) + (-1)^n*a(floor(n/2)). - Vladeta Jovovic, Apr 25 2003
A fixed point of the mapping 1->12; 2->13; 3->14; 4->15; 5->16; ... . - Philippe Deléham, Dec 13 2003
Product_{k>0} (1+x^k)^a(k) is g.f. for A000041(). - Vladeta Jovovic, Mar 26 2004
G.f. A(x) satisfies A(x) = A(x^2) + x/(1-x). - Franklin T. Adams-Watters, Feb 09 2006
a(A118413(n,k)) = A002260(n,k); = a(A118416(n,k)) = A002024(n,k); a(A014480(n)) = A003602(A014480(n)). - Reinhard Zumkeller, Apr 27 2006
Ordinal transform of A003602. - Franklin T. Adams-Watters, Aug 28 2006 (The ordinal transform of a sequence b_0, b_1, b_2, ... is the sequence a_0, a_1, a_2, ... where a_n is the number of times b_n has occurred in {b_0 ... b_n}.)
Could be extended to n <= 0 using a(-n) = a(n), a(0) = 0, a(2*n) = a(n)+1 unless n=0. - Michael Somos, Sep 30 2006
A094267(2*n) = A050603(2*n) = A050603(2*n + 1) = a(n). - Michael Somos, Sep 30 2006
Sequence = A129360 * A000005 = M*V, where M = an infinite lower triangular matrix and V = d(n) as a vector: [1, 2, 2, 3, 2, 4, ...]. - Gary W. Adamson, Apr 15 2007
Row sums of triangle A130093. - Gary W. Adamson, May 13 2007
Dirichlet g.f.: zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
a(n) = -Sum_{d divides n} mu(2*d)*tau(n/d). - Benoit Cloitre, Jun 21 2007
G.f.: x/(1-x) = Sum_{n>=1} a(n)*x^n*( 1 - x^n ). - Paul D. Hanna, Jun 22 2007
2*n = 2^a(n)* A000265(n). - Eric Desbiaux, May 14 2009 [corrected by Alejandro Erickson, Apr 17 2012]
Multiplicative with a(2^k) = k + 1, a(p^k) = 1 for any odd prime p. - Franklin T. Adams-Watters, Jun 09 2009
With S(n): 2^n - 1 first elements of the sequence then S(0) = {} (empty list) and if n > 0, S(n) = S(n-1), n, S(n-1). - Yann David (yann_david(AT)hotmail.com), Mar 21 2010
a(n) = log_2(A046161(n)/A046161(n-1)). - Johannes W. Meijer, Nov 04 2012
a((2*n-1)*2^p) = p+1, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 05 2013
a(n+1) = 1 + Sum_{j=0..ceiling(log_2(n+1))} (j * (1 - abs(sign((n mod 2^(j + 1)) - 2^j + 1)))). - Enrico Borba, Oct 01 2015
Conjecture: a(n) = A181988(n)/A003602(n). - L. Edson Jeffery, Nov 21 2015
a(n) = log_2(A006519(n)) + 1. - Doug Bell, Jun 02 2017
Inverse Moebius transform of A209229. - Andrew Howroyd, Aug 04 2018
a(n) = 1 + (A183063(n)/A001227(n)). - Omar E. Pol, Nov 06 2018 (after Franklin T. Adams-Watters)
a(n) = log_2((Xor(2*n,2*n-1)+1)/2). - Gary Detlefs, Dec 13 2018
(2^(a(n)-1)-1)*(n mod 4) = 2*floor(((n+1) mod 4)/3). - Gary Detlefs, Dec 14 2018
a(n) = A000005(n)/A001227(n). - Ivan N. Ianakiev, Jul 05 2019
a(n) = Sum_{j=1..r} (j/2^j)*(Product_{k=1..j} (1 - (-1)^floor( (n+2^(j-1))/2^(k-1) ))), for n < a predefined 2^r. - Adriano Caroli, Sep 30 2019

Name edited following suggestion by David James Sycamore, Oct 05 2023

A026741 a(n) = n if n odd, n/2 if n even.

Original entry on oeis.org

0, 1, 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8, 17, 9, 19, 10, 21, 11, 23, 12, 25, 13, 27, 14, 29, 15, 31, 16, 33, 17, 35, 18, 37, 19, 39, 20, 41, 21, 43, 22, 45, 23, 47, 24, 49, 25, 51, 26, 53, 27, 55, 28, 57, 29, 59, 30, 61, 31, 63, 32, 65, 33, 67, 34, 69, 35, 71, 36, 73, 37, 75, 38

Offset: 0

J. Carl Bellinger (carlb(AT)ctron.com)

a(n) is the size of largest conjugacy class in D_2n, the dihedral group with 2n elements. - Sharon Sela (sharonsela(AT)hotmail.com), May 14 2002
a(n+1) is the composition length of the n-th symmetric power of the natural representation of a finite subgroup of SL(2,C) of type D_4 (quaternion group). - Paul Boddington, Oct 23 2003
For n > 1, a(n) is the greatest common divisor of all permutations of {0, 1, ..., n} treated as base n + 1 integers. - David Scambler, Nov 08 2006 (see the Mathematics Stack Exchange link below).
From Dimitrios Choussos (choussos(AT)yahoo.de), May 11 2009: (Start)
Sequence A075888 and the above sequence are fitting together.
First 2 entries of this sequence have to be taken out.
In some cases two three or more sequenced entries of this sequence have to be added together to get the next entry of A075888.
Example: Sequences begin with 1, 3, 2, 5, 3, 7, 4, 9 (4 + 9 = 13, the next entry in A075888).
But it works out well up to primes around 50000 (haven't tested higher ones).
As A075888 gives a very regular graph. There seems to be a regularity in the primes. (End)
Starting with 1 = triangle A115359 * [1, 2, 3, ...]. - Gary W. Adamson, Nov 27 2009
From Gary W. Adamson, Dec 11 2009: (Start)
Let M be an infinite lower triangular matrix with (1, 1, 1, 0, 0, 0, ...) in every column, shifted down twice. This sequence starting with 1 = M * (1, 2, 3, ...)
M =
  1;
  1, 0;
  1, 1, 0;
  0, 1, 0, 0;
  0, 1, 1, 0, 0;
  0, 0, 1, 0, 0, 0;
  0, 0, 1, 1, 0, 0, 0;
  ...
A026741 = M * (1, 2, 3, ...); but A002487 = lim_{n->infinity} M^n, a left-shifted vector considered as a sequence. (End)
A particular case of sequence for which a(n+3) = (a(n+2) * a(n+1)+q)/a(n) for every n > n0. Here n0 = 1 and q = -1. - Richard Choulet, Mar 01 2010
For n >= 2, a(n+1) is the smallest m such that s_n(2*m*(n-1))/(n-1) is even, where s_b(c) is the sum of digits of c in base b. - Vladimir Shevelev, May 02 2011
A001477 and A005408 interleaved. - Omar E. Pol, Aug 22 2011
Numerator of n/((n-1)*(n-2)). - Michael B. Porter, Mar 18 2012
Number of odd terms of n-th row in the triangles A162610 and A209297. - Reinhard Zumkeller, Jan 19 2013
For n >= 3, a(n) is the periodic of integer of spiral length ratio of spiral that have (n-1) circle centers. See illustration in links. - Kival Ngaokrajang, Dec 28 2013
This is the sequence of Lehmer numbers u_n(sqrt(R), Q) with the parameters R = 4 and Q = 1. It is a strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all natural numbers n and m. Cf. A005013 and A108412. - Peter Bala, Apr 18 2014
The sequence of convergents of the 2-periodic continued fraction [0; 1, -4, 1, -4, ...] = 1/(1 - 1/(4 - 1/(1 - 1/(4 - ...)))) = 2 begins [0/1, 1/1, 4/3, 3/2, 8/5, 5/3, 12/7, ...]. The present sequence is the sequence of denominators; the sequence of numerators of the continued fraction convergents [0, 1, 4, 3, 8, 5, 12, ...] is A022998, also a strong divisibility sequence. - Peter Bala, May 19 2014
For n >= 3, (a(n-2)/a(n))*Pi = vertex angle of a regular n-gon. See illustration in links. - Kival Ngaokrajang, Jul 17 2014
For n > 1, the numerator of the harmonic mean of the first n triangular numbers. - Colin Barker, Nov 13 2014
The difference sequence is a permutation of the integers. - Clark Kimberling, Apr 19 2015
From Timothy Hopper, Feb 26 2017: (Start)
Given the function a(n, p) = n/p if n mod p = 0, else n, then a possible formula is: a(n, p) = n*(1 + (p-1)*((n^(p-1)) mod p))/p, p prime, (n^(p-1)) mod p = 1, n not divisible by p. (Fermat's Little Theorem). Examples: p = 2; a(n), p = 3; A051176(n), p = 5; A060791(n), p = 7; A106608(n).
Conjecture: lcm(n, p) = p*a(n, p), gcd(n, p) = n/a(n, p). (End)
Let r(n) = (a(n+1) + 1)/a(n+1) if n mod 2 = 1, a(n+1)/(a(n+1) + 2) otherwise; then lim_{k->oo} 2^(k+2) * Product_{n=0..k} r(n)^(k-n) = Pi. - Dimitris Valianatos, Mar 22 2021
Number of integers k from 1 to n such that gcd(n,k) is odd. - Amiram Eldar, May 18 2025

			G.f. = x + x^2 + 3*x^3 + 2*x^4 + 5*x^5 + 3*x^6 + 7*x^7 + 4*x^8 + ...

David Wells, Prime Numbers: The Most Mysterious Figures in Math. Hoboken, New Jersey: John Wiley & Sons (2005), p. 53.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, 2nd Ed. Penguin (1997), p. 79.

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, Combinatorial Identities Associated with a Multidimensional Polynomial Sequence, J. Int. Seq., Vol. 21 (2018), Article 18.7.4.
John M. Campbell, An Integral Representation of Kekulé Numbers, and Double Integrals Related to Smarandache Sequences, arXiv:1105.3399 [math.GM], 2011.
Leonhard Euler, De mirabilibus proprietatibus numerorum pentagonalium, par. 2.
Leonhard Euler, On the remarkable properties of the pentagonal numbers, arXiv:math/0505373 [math.HO], 2005.
Y. Ito and I. Nakamura, Hilbert schemes and simple singularities, New trends in algebraic geometry (Warwick, 1996), 151-233, Cambridge University Press, 1999.
Masanobu Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, J. Integer Sequences, 3 (2000), Article 00.2.9.
Mathematics Stack Exchange, Permutations (with no duplicates) of decimal base digits 1,2,...,8,9,0.
Kival Ngaokrajang, Illustration of spiral with circle centers 2..5.
Kival Ngaokrajang, Illustration of vertex angle of regular n-gon for n = 3..7.
Eric Weisstein's World of Mathematics, Lehmer Number.
Eric Weisstein's World of Mathematics, Simplex Simplex Picking.
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).
Index to divisibility sequences.

Signed version is in A030640. Partial sums give A001318.
Cf. A051176, A060819, A060791, A060789 for n / gcd(n, k) with k = 3..6. See also A106608 thru A106612 (k = 7 thru 11), A051724 (k = 12), A106614 thru A106621 (k = 13 thru 20).
Cf. A045896, A022998, A060762, A126988, A109007, A130334, A109043, A115359, A002487, A220466.
Cf. A013942.
Cf. A227042 (first column). Cf. A005013 and A108412.
Cf. A000217, A256095.

import Data.List (transpose)
a026741 n = a026741_list !! n
a026741_list = concat $ transpose [[0..], [1,3..]]
-- Reinhard Zumkeller, Dec 12 2011

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

A026741 := proc(n) if type(n,'odd') then n; else n/2; end if; end proc: seq(A026741(n), n=0..76); # R. J. Mathar, Jan 22 2011

Numerator[Abs[Table[Det[DiagonalMatrix[Table[1/i^2 - 1, {i, 1, n - 1}]] + 1], {n, 20}]]] (* Alexander Adamchuk, Jun 02 2006 *)
halfMax = 40; Riffle[Range[0, halfMax], Range[1, 2halfMax + 1, 2]] (* Harvey P. Dale, Mar 27 2011 *)
a[ n_] := Numerator[n / 2]; (* Michael Somos, Jan 20 2017 *)
Array[If[EvenQ[#],#/2,#]&,80,0] (* Harvey P. Dale, Jul 08 2023 *)

a(n) = numerator(n/2) \\ Rick L. Shepherd, Sep 12 2007

def A026741(n): return n if n % 2 else n//2 # Chai Wah Wu, Apr 02 2021

[lcm(n, 2) / 2 for n in range(77)] # Zerinvary Lajos, Jun 07 2009

G.f.: x*(1 + x + x^2)/(1-x^2)^2. - Len Smiley, Apr 30 2001
a(n) = 2*a(n-2) - a*(n-4) for n >= 4.
a(n) = n * 2^((n mod 2) - 1). - Reinhard Zumkeller, Oct 16 2001
a(n) = 2*n/(3 + (-1)^n). - Benoit Cloitre, Mar 24 2002
Multiplicative with a(2^e) = 2^(e-1) and a(p^e) = p^e, p > 2. - Vladeta Jovovic, Apr 05 2002
a(n) = n / gcd(n, 2). a(n)/A045896(n) = n/((n+1)*(n+2)).
For n > 0, a(n) = denominator of Sum_{i=1..n-1} 2/(i*(i+1)), numerator=A022998. - Reinhard Zumkeller, Apr 21 2012, Jul 25 2002 [thanks to Phil Carmody who noticed an error]
For n > 1, a(n) = GCD of the n-th and (n-1)-th triangular numbers (A000217). - Ross La Haye, Sep 13 2003
Euler transform of finite sequence [1, 2, -1]. - Michael Somos, Jun 15 2005
G.f.: x * (1 - x^3) / ((1 - x) * (1 - x^2)^2) = Sum_{k>0} k * (x^k - x^(2*k)). - Michael Somos, Jun 15 2005
a(n+3) + a(n+2) = 3 + a(n+1) + a(n). a(n+3) * a(n) = - 1 + a(n+2) * a(n+1). a(n) = -a(-n) for all n in Z. - Michael Somos, Jun 15 2005
For n > 1, a(n) is the numerator of the average of 1, 2, ..., n - 1; i.e., numerator of A000217(n-1)/(n-1), with corresponding denominators [1, 2, 1, 2, ...] (A000034). - Rick L. Shepherd, Jun 05 2006
Equals A126988 * (1, -1, 0, 0, 0, ...). - Gary W. Adamson, Apr 17 2007
For n >= 1, a(n) = gcd(n,A000217(n)). - Rick L. Shepherd, Sep 12 2007
a(n) = numerator(n/(2*n-2)) for n >= 2; A022998(n-1) = denominator(n/(2*n-2)) for n >= 2. - Johannes W. Meijer, Jun 18 2009
a(n) = A167192(n+2, 2). - Reinhard Zumkeller, Oct 30 2009
a(n) = A106619(n) * A109012(n). - Paul Curtz, Apr 04 2011
From R. J. Mathar, Apr 18 2011: (Start)
a(n) = A109043(n)/2.
Dirichlet g.f.: zeta(s-1)*(1 - 1/2^s). (End)
a(n) = A001318(n) - A001318(n-1) for n > 0. - Jonathan Sondow, Jan 28 2013
a((2*n+1)*2^p - 1) = 2^p - 1 + n*A151821(p+1), p >= 0 and n >= 0. - Johannes W. Meijer, Feb 03 2013
a(n+1) = denominator(H(n, 1)), n >= 0, with H(n, 1) = 2*n/(n+1) the harmonic mean of n and 1. a(n+1) = A227042(n, 1). See the formula a(n) = n/gcd(n, 2) given above. - Wolfdieter Lang, Jul 04 2013
a(n) = numerator(n/2). - Wesley Ivan Hurt, Oct 02 2013
a(n) = numerator(1 - 2/(n+2)), n >= 0; a(n) = denominator(1 - 2/n), n >= 1. - Kival Ngaokrajang, Jul 17 2014
a(n) = Sum_{i = floor(n/2)..floor((n+1)/2)} i. - Wesley Ivan Hurt, Apr 27 2016
Euler transform of length 3 sequence [1, 2, -1]. - Michael Somos, Jan 20 2017
G.f.: x / (1 - x / (1 - 2*x / (1 + 7*x / (2 - 9*x / (7 - 4*x / (3 - 7*x / (2 + 3*x))))))). - Michael Somos, Jan 20 2017
From Peter Bala, Mar 24 2019: (Start)
a(n) = Sum_{d|n, n/d odd} phi(d), where phi(n) is the Euler totient function A000010.
O.g.f.: Sum_{n >= 1} phi(n)*x^n/(1 - x^(2*n)). (End)
a(n) = A256095(2*n,n). - Alois P. Heinz, Jan 21 2020
E.g.f.: x*(2*cosh(x) + sinh(x))/2. - Stefano Spezia, Apr 28 2023
From Ctibor O. Zizka, Oct 05 2023: (Start)
For k >= 0, a(k) = gcd(k + 1, k*(k + 1)/2).
If (k mod 4) = 0 or 2 then a(k) = (k + 1).
If (k mod 4) = 1 or 3 then a(k) = (k + 1)/2. (End)
Sum_{n=1..oo} 1/a(n)^2 = 7*Pi^2/24. - Stefano Spezia, Dec 02 2023
a(n)*a(n+1) = A000217(n). - Rémy Sigrist, Mar 19 2025

Better description from Jud McCranie

Edited by Ralf Stephan, Jun 04 2003

A003602 Kimberling's paraphrases: if n = (2k-1)*2^m then a(n) = k.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, 5, 10, 3, 11, 6, 12, 2, 13, 7, 14, 4, 15, 8, 16, 1, 17, 9, 18, 5, 19, 10, 20, 3, 21, 11, 22, 6, 23, 12, 24, 2, 25, 13, 26, 7, 27, 14, 28, 4, 29, 15, 30, 8, 31, 16, 32, 1, 33, 17, 34, 9, 35, 18, 36, 5, 37, 19, 38, 10, 39, 20, 40, 3, 41, 21, 42

Offset: 1

N. J. A. Sloane, Mira Bernstein

Fractal sequence obtained from powers of 2.
k occurs at (2*k-1)*A000079(m), m >= 0. - Robert G. Wilson v, May 23 2006
Sequence is T^(oo)(1) where T is acting on a word w = w(1)w(2)..w(m) as follows: T(w) = "1"w(1)"2"w(2)"3"(...)"m"w(m)"m+1". For instance T(ab) = 1a2b3. Thus T(1) = 112, T(T(1)) = 1121324, T(T(T(1))) = 112132415362748. - Benoit Cloitre, Mar 02 2009
Note that iterating the post-numbering operator U(w) = w(1) 1 w(2) 2 w(3) 3... produces the same limit sequence except with an additional "1" prepended, i.e., 1,1,1,2,1,3,2,4,... - Glen Whitney, Aug 30 2023
In the binary expansion of n, first swallow all zeros from the right, then add 1, and swallow the now-appearing 0 bit as well. - Ralf Stephan, Aug 22 2013
Although A264646 and this sequence initially agree in their digit-streams, they differ after 48 digits. - N. J. A. Sloane, Nov 20 2015
"[This is a] fractal because we get the same sequence after we delete from it the first appearance of all positive integers" - see Cobeli and Zaharescu link. - Robert G. Wilson v, Jun 03 2018
From Peter Munn, Jun 16 2022: (Start)
The sequence is the list of positive integers interleaved with the sequence itself. Provided the offset is suitable (which is the case here) a term of such a self-interleaved sequence is determined by the odd part of its index. Putting some of the formulas given here into words, a(n) is the position of the odd part of n in the list of odd numbers.
Applying the interleaving transform again, we get A110963.
(End)
Omitting all 1's leaves A131987 + 1. - David James Sycamore, Jul 26 2022
a(n) is also the smallest positive number not among the terms between a(a(n-1)) and a(n-1) inclusive (with a(0)=1 prepended). - Neal Gersh Tolunsky, Mar 07 2023

			From _Peter Munn_, Jun 14 2022: (Start)
Start of table showing the interleaving with the positive integers:
   n  a(n)  (n+1)/2  a(n/2)
   1    1      1
   2    1               1
   3    2      2
   4    1               1
   5    3      3
   6    2               2
   7    4      4
   8    1               1
   9    5      5
  10    3               3
  11    6      6
  12    2               2
(End)

Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Cristian Cobeli and Alexandru Zaharescu, Promenade around Pascal Triangle - Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104) No. 1, 2013, 73-98.
J.-P. Delahaye, La marelle arithmétique, Pour la Science, No. 360, October 2007. In French.
Dale Gerdemann, Plotting Adjacent Points in A003602, Kimberling's Paraphrase, YouTube Video, 2015.
Dale Gerdemann, Plotting Adjacent Terms of A003602 Modulo Increasing Powers of 2, YouTube Video, 2015.
Douglas E. Iannucci and Urban Larsson, Game values of arithmetic functions, arXiv:2101.07608 [math.NT], 2021.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Clark Kimberling, Numeration systems and fractal sequences, Acta Arithmetica 73 (1995) 103-117.
Clark Kimberling, Fractal sequences
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Matty van-Son, Palindromic sequences of the Markov spectrum, arXiv:1804.10802 [math.NT], 2018.
Eric Weisstein's World of Mathematics, Odd Part
Index entries for sequences related to binary expansion of n

a(n) is the index of the column in A135764 where n appears (see also A054582).
Cf. A000079, A000265, A001511, A003603, A003961, A014577 (with offset 1, reduction mod 2), A025480, A035528, A048673, A101279, A110963, A117303, A126760, A181988, A220466, A249745, A253887, A337821 (2-adic valuation).
Cf. also A349134 (Dirichlet inverse), A349135 (sum with it), A349136 (Möbius transform), A349431, A349371 (inverse Möbius transform).
Cf. A065120, A131987.
Cf. A264646.
Cf. A123390, A118319.

a003602 = (`div` 2) . (+ 1) . a000265
-- Reinhard Zumkeller, Feb 16 2012, Oct 14 2010

import Data.List (transpose)
a003602 = flip div 2 . (+ 1) . a000265
a003602_list = concat $ transpose [[1..], a003602_list]
-- Reinhard Zumkeller, Aug 09 2013, May 23 2013

A003602:=proc(n) options remember: if n mod 2 = 1 then RETURN((n+1)/2) else RETURN(procname(n/2)) fi: end proc:
seq(A003602(n), n=1..83); # Pab Ter
nmax := 83: for m from 0 to ceil(simplify(log[2](nmax))) do for k from 1 to ceil(nmax/(m+2)) do a((2*k-1)*2^m) := k od: od: seq(a(k), k=1..nmax); # Johannes W. Meijer, Feb 04 2013
A003602 := proc(n)
    a := 1;
    for p in ifactors(n)[2] do
        if op(1,p) > 2 then
            a := a*op(1,p)^op(2,p) ;
        end if;
    end do  :
    (a+1)/2 ;
end proc: # R. J. Mathar, May 19 2016

a[n_] := Block[{m = n}, While[ EvenQ@m, m /= 2]; (m + 1)/2]; Array[a, 84] (* or *)
a[1] = 1; a[n_] := a[n] = If[OddQ@n, (n + 1)/2, a[n/2]]; Array[a, 84] (* Robert G. Wilson v, May 23 2006 *)
a[n_] := Ceiling[NestWhile[Floor[#/2] &, n, EvenQ]/2]; Array[a, 84] (* Birkas Gyorgy, Apr 05 2011 *)
a003602 = {1}; max = 7; Do[b = {}; Do[AppendTo[b, {k, a003602[[k]]}], {k, Length[a003602]}]; a003602 = Flatten[b], {n, 2, max}]; a003602 (* L. Edson Jeffery, Nov 21 2015 *)

A003602(n)=(n/2^valuation(n,2)+1)/2; /* Joerg Arndt, Apr 06 2011 */

import math
def a(n): return (n/2**int(math.log(n - (n & n - 1), 2)) + 1)/2 # Indranil Ghosh, Apr 24 2017

def A003602(n): return (n>>(n&-n).bit_length())+1 # Chai Wah Wu, Jul 08 2022

(define (A003602 n) (let loop ((n n)) (if (even? n) (loop (/ n 2)) (/ (+ 1 n) 2)))) ;; Antti Karttunen, Feb 04 2015

a(n) = (A000265(n) + 1)/2.
a((2*k-1)*2^m) = k, for m >= 0 and k >= 1. - Robert G. Wilson v, May 23 2006
Inverse Weigh transform of A035528. - Christian G. Bower
G.f.: 1/x * Sum_{k>=0} x^2^k/(1-2*x^2^(k+1) + x^2^(k+2)). - Ralf Stephan, Jul 24 2003
a(2*n-1) = n and a(2*n) = a(n). - Pab Ter (pabrlos2(AT)yahoo.com), Oct 25 2005
a(A118413(n,k)) = A002024(n,k); = a(A118416(n,k)) = A002260(n,k); a(A014480(n)) = A001511(A014480(n)). - Reinhard Zumkeller, Apr 27 2006
Ordinal transform of A001511. - Franklin T. Adams-Watters, Aug 28 2006
a(n) = A249745(A126760(A003961(n))) = A249745(A253887(A048673(n))). That is, this sequence plays the same role for the numbers in array A135764 as A126760 does for the odd numbers in array A135765. - Antti Karttunen, Feb 04 2015 & Jan 19 2016
G.f. satisfies g(x) = g(x^2) + x/(1-x^2)^2. - Robert Israel, Apr 24 2015
a(n) = A181988(n)/A001511(n). - L. Edson Jeffery, Nov 21 2015
a(n) = A025480(n-1) + 1. - R. J. Mathar, May 19 2016
a(n) = A110963(2n-1) = A349135(4*n). - Antti Karttunen, Apr 18 2022
a(n) = (1 + n)/2, for n odd; a(n) = a(n/2), for n even. - David James Sycamore, Jul 28 2022
a(n) = n/2^A001511(n) + 1/2. - Alan Michael Gómez Calderón, Oct 06 2023
a(n) = A123390(A118319(n)). - Flávio V. Fernandes, Mar 02 2025

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Oct 25 2005

A035263 Trajectory of 1 under the morphism 0 -> 11, 1 -> 10; parity of 2-adic valuation of 2n: a(n) = A000035(A001511(n)).

Original entry on oeis.org

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

Offset: 1

Karamanos Konstantinos, N. J. A. Sloane

First Feigenbaum symbolic (or period-doubling) sequence, corresponding to the accumulation point of the 2^{k} cycles through successive bifurcations.
To construct the sequence: start with 1 and concatenate: 1,1, then change the last term (1->0; 0->1) gives: 1,0. Concatenate those 2 terms: 1,0,1,0, change the last term: 1,0,1,1. Concatenate those 4 terms: 1,0,1,1,1,0,1,1 change the last term: 1,0,1,1,1,0,1,0, etc. - Benoit Cloitre, Dec 17 2002
Let T denote the present sequence. Here is another way to construct T. Start with the sequence S = 1,0,1,,1,0,1,,1,0,1,,1,0,1,,... and fill in the successive holes with the successive terms of the sequence T (from paper by Allouche et al.). - Emeric Deutsch, Jan 08 2003 [Note that if we fill in the holes with the terms of S itself, we get A141260. - N. J. A. Sloane, Jan 14 2009]
From N. J. A. Sloane, Feb 27 2009: (Start)
In more detail: define S to be 1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1,0,1___...
If we fill the holes with S we get A141260:
1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,
........1.........0.........1.........1.........0.......1.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.0.1.... = A141260.
But instead, if we define T recursively by filling the holes in S with the terms of T itself, we get A035263:
1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0, 1___1, 0,
........1.........0.........1.........1.........1.......0.........1.........0...
- the result is
1..0..1.1.1..0..1.0.1..0..1.1.1..0..1.1.1..0..1.1.1.0.1.0.1..0..1.1.1..0..1.0.1.. = A035263. (End)
Characteristic function of A003159, i.e., A035263(n)=1 if n is in A003159 and A035263(n)=0 otherwise (from paper by Allouche et al.). - Emeric Deutsch, Jan 15 2003
This is the sequence of R (=1), L (=0) moves in the Towers of Hanoi puzzle: R, L, R, R, R, L, R, L, R, L, R, R, R, ... - Gary W. Adamson, Sep 21 2003
Manfred Schroeder, p. 279 states, "... the kneading sequences for unimodal maps in the binary notation, 0, 1, 0, 1, 1, 1, 0, 1..., are obtained from the Morse-Thue sequence by taking sums mod 2 of adjacent elements." On p. 278, in the chapter "Self-Similarity in the Logistic Parabola", he writes, "Is there a closer connection between the Morse-Thue sequence and the symbolic dynamics of the superstable orbits? There is indeed. To see this, let us replace R by 1 and C and L by 0." - Gary W. Adamson, Sep 21 2003
Partial sums modulo 2 of the sequence 1, a(1), a(1), a(2), a(2), a(3), a(3), a(4), a(4), a(5), a(5), a(6), a(6), ... . - Philippe Deléham, Jan 02 2004
Parity of A007913, A065882 and A065883. - Philippe Deléham, Mar 28 2004
The length of n-th run of 1's in this sequence is A080426(n). - Philippe Deléham, Apr 19 2004
Also parity of A005043, A005773, A026378, A104455, A117641. - Philippe Deléham, Apr 28 2007
Equals parity of the Towers of Hanoi, or ruler sequence (A001511), where the Towers of Hanoi sequence (1, 2, 1, 3, 1, 2, 1, 4, ...) denotes the disc moved, labeled (1, 2, 3, ...) starting from the top; and the parity of (1, 2, 1, 3, ...) denotes the direction of the move, CW or CCW. The frequency of CW moves converges to 2/3. - Gary W. Adamson, May 11 2007
A conjectured identity relating to the partition sequence, A000041: p(x) = A(x) * A(x^2) when A(x) = the Euler transform of A035263 = polcoeff A174065: (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...). - Gary W. Adamson, Mar 21 2010
a(n) is 1 if the number of trailing zeros in the binary representation of n is even. - Ralf Stephan, Aug 22 2013
From Gary W. Adamson, Mar 25 2015: (Start)
A conjectured identity relating to the partition sequence, A000041 as polcoeff p(x); A003159, and its characteristic function A035263: (1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ...); and A036554 indicating n-th terms with zeros in A035263: (2, 6, 8, 10, 14, 18, 22, ...).
The conjecture states that p(x) = A(x) = A(x^2) when A(x) = polcoeffA174065 = the Euler transform of A035263 = 1/(1-x)*(1-x^3)*(1-x^4)*(1-x^5)*... = (1 + x + x^2 + 2x^3 + 3x^4 + 4x^5 + ...) and the aerated variant = the Euler transform of the complement of A035263: 1/(1-x^2)*(1-x^6)*(1-x^8)*... = (1 + x^2 + x^4 + 2x^6 + 3x^8 + 4x^10 + ...).
(End)
The conjecture above was proved by Jean-Paul Allouche on Dec 21 2013.
Regarded as a column vector, this sequence is the product of A047999 (Sierpinski's gasket) regarded as an infinite lower triangular matrix and A036497 (the Fredholm-Rueppel sequence) where the 1's have alternating signs, 1, -1, 0, 1, 0, 0, 0, -1, .... - Gary W. Adamson, Jun 02 2021
The numbers of 1's through n (A050292) can be determined by starting with the binary (say for 19 = 1 0 0 1 1) and writing: next term is twice current term if 0, otherwise twice plus 1. The result is 1, 2, 4, 9, 19. Take the difference row, = 1, 1, 2, 5, 10; and add the odd-indexed terms from the right: 5, 4, 3, 2, 1 = 10 + 2 + 1 = 13. The algorithm is the basis for determining the disc configurations in the tower of Hanoi game, as shown in the Jul 24 2021 comment of A060572. - Gary W. Adamson, Jul 28 2021

Karamanos, Kostas. "From symbolic dynamics to a digital approach." International Journal of Bifurcation and Chaos 11.06 (2001): 1683-1694. (Full version. See p. 1685)
Karamanos, K. (2000). From symbolic dynamics to a digital approach: chaos and transcendence. In Michel Planat (Ed.), Noise, Oscillators and Algebraic Randomness (Lecture Notes in Physics, pp. 357-371). Springer, Berlin, Heidelberg. (Short version. See p. 359)
Manfred R. Schroeder, "Fractals, Chaos, Power Laws", W. H. Freeman, 1991
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 892, column 2, Note on p. 84, part (a).

Antti Karttunen, Table of n, a(n) for n = 1..65536 (first 10000 terms from T. D. Noe)
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, CNRS France, 2024. See p. 6.
Jean-Paul Allouche, On the morphism 1 -> 121, 2 -> 12221, Preprint, 2024 [Local copy, with permission]
Jean-Paul Allouche, Andre Arnold, Jean Berstel, Srecko Brlek, William Jockusch, Simon Plouffe and Bruce E. Sagan, A sequence related to that of Thue-Morse, Discrete Math., 139 (1995), 455-461.
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.
Jean-Paul Allouche and Michel Mendes 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]
Jean-Paul Allouche and Jeffrey Shallit, The Ubiquitous Prouhet-Thue-Morse Sequence, in C. Ding. T. Helleseth and H. Niederreiter, eds., Sequences and Their Applications: Proceedings of SETA '98, Springer-Verlag, 1999, pp. 1-16.
Joerg Arndt, Matters Computational (The Fxtbook), pp.9-10, pp.734-738
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
Benoit Cloitre, Fractal walk on the 130000 first terms (step of unit length moving with angle Pi/3 if 0 and -Pi/3 if 1) starting at (0,0)
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
B. Derrida, A. Gervois and Y. Pomeau, Iteration of endomorphisms on the real axis and representation of number, Ann. Inst. Henri Poincaré, Section A: Physique Théorique, Vol. XXIX no. 3, 305-356 (1978).
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, arXiv:math/0407326 [math.CO], 2004.
Emeric Deutsch and Bruce E. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Num. Theory 117 (2006), 191-215.
Andreas M. Hinz, Sandi Klavžar, Uroš Milutinović, and Ciril Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 79. Book's website
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Konstantinos Karamanos, Symbolic Dynamics to a Digital Approach, Int. J. of Bifurcation and Chaos, 11(6), 1683-1694 (2001).
Konstantinos Karamanos and Grégoire Nicolis, Symbolic Dynamics and Entropy Analysis of Feigenbaum Limit Sets, Chaos, Solitons and Fractals 10(7), 1135 - 1150 (1999).
D. Kohel, S. Ling and C. Xing, Explicit Sequence Expansions
Joseph Meleshko, Pascal Ochem, Jeffrey Shallit, and Sonja Linghui Shan, Pseudoperiodic Words and a Question of Shevelev, arXiv:2207.10171 [math.CO], 2022.
Nicholas C. Metropolis, Myron L. Stein and Paul R. Stein, On finite limit sets for transformations on the unit interval, J. Combin. Theory, A 15 (1973), 25-44.
Jeffrey Shallit and Anatoly Zavyalov, Transduction of Automatic Sequences and Applications, arXiv:2303.15203 [cs.FL], 2023, see p. 5.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Binary carry sequence.
Eric Weisstein's World of Mathematics, Double-free set.
Index entries for characteristic functions
Index entries for sequences related to binary expansion of n
Index entries for sequences that are fixed points of mappings

Parity of A001511. Anti-parity of A007814.
Absolute values of first differences of A010060. Apart from signs, same as A029883. Essentially the same as A056832.
Swapping 0 and 1 gives A096268.
Cf. A033485, A050292 (partial sums), A089608, A088172, A019300, A039982, A073675, A121701, A141260, A000041, A174065, A220466, A154269 (Mobius transform).
Limit of A317957(n) for large n.
Cf. A060572

import Data.Bits (xor)
a035263 n = a035263_list !! (n-1)
a035263_list = zipWith xor a010060_list $ tail a010060_list
-- Reinhard Zumkeller, Mar 01 2012

nmax:=105: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := (p+1) mod 2 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 07 2013
A035263 := n -> 1 - padic[ordp](n, 2) mod 2:
seq(A035263(n), n=1..105); # Peter Luschny, Oct 02 2018

a[n_] := a[n] = If[ EvenQ[n], 1 - a[n/2], 1]; Table[ a[n], {n, 1, 105}] (* Or *)
Rest[ CoefficientList[ Series[ Sum[ x^(2^k)/(1 + (-1)^k*x^(2^k)), {k, 0, 20}], {x, 0, 105}], x]]
f[1] := True; f[x_] := Xor[f[x - 1], f[Floor[x/2]]]; a[x_] := Boole[f[x]] (* Ben Branman, Oct 04 2010 *)
a[n_] := If[n == 0, 0, 1 - Mod[ IntegerExponent[n, 2], 2]]; (* Jean-François Alcover, Jul 19 2013, after Michael Somos *)
Nest[ Flatten[# /. {0 -> {1, 1}, 1 -> {1, 0}}] &, {0}, 7] (* Robert G. Wilson v, Jul 23 2014 *)
SubstitutionSystem[{0->{1,1},1->{1,0}},1,{7}][[1]] (* Harvey P. Dale, Jun 06 2022 *)

{a(n) = if( n==0, 0, 1 - valuation(n, 2)%2)}; /* Michael Somos, Sep 04 2006 */

{a(n) = if( n==0, 0, n = abs(n); subst( Pol(binary(n)) - Pol(binary(n-1)), x, 1)%2)}; /* Michael Somos, Sep 04 2006 */

{a(n) = if( n==0, 0, n = abs(n); direuler(p=2, n, 1 / (1 - X^((p<3) + 1)))[n])}; /* Michael Somos, Sep 04 2006 */

def A035263(n): return (n&-n).bit_length()&1 # Chai Wah Wu, Jan 09 2023

(define (A035263 n) (let loop ((n n) (i 1)) (cond ((odd? n) (modulo i 2)) (else (loop (/ n 2) (+ 1 i)))))) ;; (Use mod instead of modulo in R6RS) Antti Karttunen, Sep 11 2017

Absolute values of first differences (A029883) of Thue-Morse sequence (A001285 or A010060). Self-similar under 10->1 and 11->0.
Series expansion: (1/x) * Sum_{i>=0} (-1)^(i+1)*x^(2^i)/(x^(2^i)-1). - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 17 2003
a(n) = Sum_{k>=0} (-1)^k*(floor((n+1)/2^k)-floor(n/2^k)). - Benoit Cloitre, Jun 03 2003
Another g.f.: Sum_{k>=0} x^(2^k)/(1+(-1)^k*x^(2^k)). - Ralf Stephan, Jun 13 2003
a(2*n) = 1-a(n), a(2*n+1) = 1. - Ralf Stephan, Jun 13 2003
a(n) = parity of A033485(n). - Philippe Deléham, Aug 13 2003
Equals A088172 mod 2, where A088172 = 1, 2, 3, 7, 13, 26, 53, 106, 211, 422, 845, ... (first differences of A019300). - Gary W. Adamson, Sep 21 2003
a(n) = a(n-1) - (-1)^n*a(floor(n/2)). - Benoit Cloitre, Dec 02 2003
a(1) = 1 and a(n) = abs(a(n-1) - a(floor(n/2))). - Benoit Cloitre, Dec 02 2003
a(n) = 1 - A096268(n+1); A050292 gives partial sums. - Reinhard Zumkeller, Aug 16 2006
Multiplicative with a(2^k) = 1 - (k mod 2), a(p^k) = 1, p > 2. Dirichlet g.f.: Product_{n = 4 or an odd prime} (1/(1-1/n^s)). - Christian G. Bower, May 18 2005
a(-n) = a(n). a(0)=0. - Michael Somos, Sep 04 2006
Dirichlet g.f.: zeta(s)*2^s/(2^s+1). - Ralf Stephan, Jun 17 2007
a(n+1) = a(n) XOR a(ceiling(n/2)), a(1) = 1. - Reinhard Zumkeller, Jun 11 2009
Let D(x) be the generating function, then D(x) + D(x^2) == x/(1-x). - Joerg Arndt, May 11 2010
a(n) = A010060(n) XOR A010060(n+1); a(A079523(n)) = 0; a(A121539(n)) = 1. - Reinhard Zumkeller, Mar 01 2012
a((2*n-1)*2^p) = (p+1) mod 2, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 07 2013
a(n) = A000035(A001511(n)). - Omar E. Pol, Oct 29 2013
a(n) = 2-A056832(n) = (5-A089608(n))/4. - Antti Karttunen, Sep 11 2017, after Benoit Cloitre
For n >= 0, a(n+1) = M(2n) mod 2 where M(n) is the Motzkin number A001006 (see Deutsch and Sagan 2006 link). - David Callan, Oct 02 2018
a(n) = A038712(n) mod 3. - Kevin Ryde, Jul 11 2019
Given any n in the form (k * 2^m, k odd), extract k and m. Categorize the results into two outcomes of (k, m, even or odd). If (k, m) is (odd, even) substitute 1. If (odd, odd), denote the result 0.  Example: 5 = (5 * 2^0), (odd, even, = 1). (6 = 3 * 2^1), (odd, odd, = 0). - Gary W. Adamson, Jun 23 2021

Alternative description added to the name by Antti Karttunen, Sep 11 2017

A025480 a(2n) = n, a(2n+1) = a(n).

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 3, 0, 4, 2, 5, 1, 6, 3, 7, 0, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 0, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 0, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10

Offset: 0

David W. Wilson

These are the Grundy values or nim-values for heaps of n beans in the game where you're allowed to take up to half of the beans in a heap. - R. K. Guy, Mar 30 2006. See Levine 2004/2006 for more about this. - N. J. A. Sloane, Aug 14 2016
When n > 0 is written as (2k+1)*2^j then k = a(n-1) and j = A007814(n), so: when n is written as (2k+1)*2^j-1 then k = a(n) and j = A007814(n+1), when n > 1 is written as (2k+1)*2^j+1 then k = a(n-2) and j = A007814(n-1). - Henry Bottomley, Mar 02 2000 [sequence id corrected by Peter Munn, Jun 22 2022]
According to the comment from Deuard Worthen (see Example section), this may be regarded as a triangle where row r=1,2,3,... has length 2^(r-1) and values T(r,2k-1)=T(r-1,k), T(r,2k)=2^(r-1)+k-1; i.e., previous row gives 1st, 3rd, 5th, ... term and 2nd, 4th, ... terms are numbers 2^(r-1),...,2^r-1 (i.e., those following the last one from the previous row). - M. F. Hasler, May 03 2008
Let StB be a Stern-Brocot tree hanging between (pseudo)fractions Left and Right, then StB(1) = mediant(Left,Right) and for n>1: StB(n) = if a(n-1)<>0 and a(n)<>0 then mediant(StB(a(n-1)),StB(a(n))) else if a(n)=0 then mediant(StB(a(n-1)),Right) else mediant(Left,StB(a(n-1))), where mediant(q1,q2) = ((numerator(q1)+numerator(q2)) / (denominator(q1)+denominator(q2))). - Reinhard Zumkeller, Dec 22 2008
This sequence is the unique fixed point of the function (a(0), a(1), a(2), ...) |--> (0, a(0), 1, a(1), 2, a(2), ...) which interleaves the nonnegative integers between the elements of a sequence. - Cale Gibbard (cgibbard(AT)gmail.com), Nov 18 2009
Also the number of remaining survivors in a Josephus problem after the person originally first in line has been eliminated (see A225381). - Marcus Hedbring, May 18 2013
A fractal sequence - see Levine 2004/2006. - N. J. A. Sloane, Aug 14 2016
From David James Sycamore, Apr 29 2020: (Start)
One of a family of fractal sequences, S_k; defined as follows for k >= 2: a(k*n) = n, a(k*n+r) = a((k-1)*n + (r-1)), r = 1..(k-1). S_2 is A025480; S_3 gives: a(3*n) = n, a(3*n + 1) = a(2*n), a(3*n + 2) = a(2*n + 1), which is A263390.
The subsequence of all nonzero terms is A131987. (End)
Similar to but different from A108202. - N. J. A. Sloane, Nov 26 2020
This sequence can be otherwise defined in two alternative (but related) ways, with a(0)=0, as follows: (i) If a(n) is a novel term, then a(n+1) = a(a(n)); if a(n) has been seen before, most recently at a(m), then a(n+1) = n-m (as in A181391). (ii) As above for novel a(n), then if a(n) has been seen before, a(n+1) = smallest k < a(n) which is not already a term. - David James Sycamore, Jul 13 2021
From a binary perspective, the sequence can be seen as even,odd pairs where the odd value is the previous even value, dropping the rightmost bits up to and including the lowest zero bit, aka right-shifted past the lowest clear bit. E.g., (5)101 -> 1, (17)10001 -> (4)100, (29)11101 -> (7)111, (39)100111 -> (2)10. - Joe Nellis, Oct 09 2022

			From Deuard Worthen (deuard(AT)raytheon.com), Jan 27 2006: (Start)
The sequence can be constructed as a triangle as:
  0
  0  1
  0  2  1  3
  0  4  2  5  1  6  3  7
  0  8  4  9  2 10  5 11  1 12  6 13  3 14  7 15
  ...
At each stage we interleave the next 2^m numbers in the previous row. (End)
Left=0/1, Right=1/0: StB=A007305/A047679; Left=0/1, Right=1/1: StB=A007305/A007306; Left=1/3, Right=2/3: StB=A153161/A153162. - _Reinhard Zumkeller_, Dec 22 2008

L. Levine, Fractal sequences and restricted Nim, Ars Combin. 80 (2006), 113-127.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
Josef Eschgfäller and Andrea Scarpante, Dichotomic random number generators, arXiv:1603.08500 [math.CO], 2016.
Ralf Hinze, Concrete stream calculus: An extended study, J. Funct. Progr. 20 (5-6) (2010) 463-535, doi, Section 3.2.4.
L. Levine, Fractal sequences and restricted Nim, arXiv:math/0409408 [math.CO], 2004.
Ralf Stephan, Some divide-and-conquer sequences ....
Ralf Stephan, Table of generating functions.
Paul Tarau, A Groupoid of Isomorphic Data Transformations, Calculemus 2009, 8th International Conference, MKM 2009, pp. 170-185, Springer, LNAI 5625.
Index entries for sequences related to the Josephus Problem.

The Y-projection of A075300.

Cf. A108202, A138002, A000265, A003602, A103391, A153733, A220466, A225381, A131987, A263390, A181391, A007814.

import Data.List
interleave xs ys = concat . transpose $ [xs,ys]
a025480 = interleave [0..] a025480
-- Cale Gibbard, Nov 18 2009

Cf. comments by Worthen and Hasler.
import Data.List (transpose)
a025480 n k = a025480_tabf !! n !! k
a025480_row n = a025480_tabf !! n
a025480_tabf = iterate (\xs -> concat $
   transpose [xs, [length xs .. 2 * length xs - 1]]) [0]
a025480_list = concat $ a025480_tabf
-- Reinhard Zumkeller, Apr 29 2012

A025480 := proc(n)
    option remember ;
    if type(n,'even') then
        n/2 ;
    else
        procname((n-1)/2) ;
    end if;
end proc:
seq(A025480(n),n=0..100) ; # R. J. Mathar, Jul 16 2020

a[n_] := a[n] = If[OddQ@n, a[(n - 1)/2], n/2]; Table[ a[n], {n, 0, 83}] (* Robert G. Wilson v, Mar 30 2006 *)
Table[BitShiftRight[n, IntegerExponent[n, 2] + 1], {n, 100}] (* IWABUCHI Yu(u)ki, Oct 13 2012 *)

a(n)={while(n%2,n\=2);n\2} \\ M. F. Hasler, May 03 2008

A025480(n)=n>>valuation(n*2+2,2) \\ M. F. Hasler, Apr 12 2012

def A025480(n): return n>>((~(n+1)&n).bit_length()+1) # Chai Wah Wu, Jul 13 2022

A025480 = lambda n: odd_part(n+1)//2
[A025480(n) for n in (0..83)] # Peter Luschny, May 20 2014

a(n) = A003602(n+1) - 1. [Corrected by Max Alekseyev, May 05 2022]
a(n) = (A000265(n+1)-1)/2 = ((n+1)/A006519(n+1)-1)/2.
a(n) = A153733(n)/2. - Reinhard Zumkeller, Dec 31 2008
2^A007814(n+1)*(2*a(n)+1) = n+1. (See functions hd, tl and cons in [Paul Tarau 2009].) - Paul Tarau (paul.tarau(AT)gmail.com), Mar 21 2010
a(3*n + 1) = A173732(n). - Reinhard Zumkeller, Apr 29 2012
a((2*n+1)*2^p-1) = n, p >= 0 and n >= 0. - Johannes W. Meijer, Jan 24 2013
a(n) = n - A225381(n). - Marcus Hedbring, May 18 2013
G.f.: -1/(1-x) + Sum_{k>=0} x^(2^k-1)/(1-2*x^2^(k+1)+x^2^(k+2)). - Ralf Stephan, May 19 2013
a(n) = A049084(A181363(n+1)). - Reinhard Zumkeller, Mar 22 2014
a(n) = floor(n / 2^A001511(n+1)). - Adam Shelly, Mar 05 2019
Recursion: a(0) = 0; a(n + 1) = a(a(n)) if a(n) is a first occurrence of a term, else a(n + 1) = n - a(n-1). - David James Sycamore, Apr 29 2020
a(n) * 2^(A007814(n+1)+1) + 2^A007814(n+1) - 1 = n (equivalent to the formula given in the comment by Paul Tarau). - Ruud H.G. van Tol, Apr 14 2023
Sum_{k=1..n} a(k) = n^2/6 + O(n). - Amiram Eldar, Aug 07 2023

Edited by M. F. Hasler, Mar 16 2018

A038712 Let k be the exponent of highest power of 2 dividing n (A007814); a(n) = 2^(k+1)-1.

Original entry on oeis.org

1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 127, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 31, 1, 3, 1, 7, 1, 3, 1, 15, 1, 3, 1, 7, 1, 3, 1, 63, 1, 3

Offset: 1

Henry Bottomley, May 02 2000

n XOR n-1, i.e., nim-sum of a pair of consecutive numbers.
Denominator of quotient sigma(2*n)/sigma(n). - Labos Elemer, Nov 04 2003
a(n) = the Towers of Hanoi disc moved at the n-th move, using standard moves with discs labeled (1, 3, 7, 15, ...) starting from top (smallest = 1). - Gary W. Adamson, Oct 26 2009
Equals row sums of triangle A168312. - Gary W. Adamson, Nov 22 2009
In the binary expansion of n, delete everything left of the rightmost 1 bit, and set all bits to the right of it. - Ralf Stephan, Aug 22 2013
Every finite sequence of positive integers summing to n may be termwise dominated by a subsequence of the first n values in this sequence [see Bannister et al., 2013]. - David Eppstein, Aug 31 2013
Sum of powers of 2 dividing n. - Omar E. Pol, Aug 18 2019
Given the binary expansion of (n-1) as {b[k-1], b[k-2], ..., b[2], b[1], b[0]}, then the binary expansion of a(n) is {bitand(b[k-1], b[k-2], ..., b[2], b[1], b[0]), bitand(b[k-2], ..., b[2], b[1], b[0]), ..., bitand(b[2], b[1], b[0]), bitand(b[1], b[0]), b[0], 1}. Recursively stated - 0th bit (L.S.B) of a(n), a(n)[0] = 1, a(n)[i] = bitand(a(n)[i-1], (n-1)[i-1]), where n[i] = i-th bit in the binary expansion of n. - Chinmaya Dash, Jun 27 2020

			a(6) = 3 because 110 XOR 101 = 11 base 2 = 3.
From _Omar E. Pol_, Aug 18 2019: (Start)
Illustration of initial terms:
a(n) is also the area of the n-th region of an infinite diagram of compositions (ordered partitions) of the positive integers, where the length of the n-th horizontal line segment is equal to A001511(n) and the length of the n-th vertical line segment is equal to A006519(n), as shown below (first eight regions):
-----------------------------
n    a(n)    Diagram
-----------------------------
.            _ _ _ _
1     1     |_| | | |
2     3     |_ _| | |
3     1     |_|   | |
4     7     |_ _ _| |
5     1     |_| |   |
6     3     |_ _|   |
7     1     |_|     |
8    15     |_ _ _ _|
.
The above diagram represents the eight compositions of 4: [1,1,1,1],[2,1,1],[1,2,1],[3,1],[1,1,2],[2,2],[1,3],[4].
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, Superpatterns and universal point sets, 21st Int. Symp. Graph Drawing, 2013, arXiv:1308.0403 [cs.CG], 2013.
Klaus Brockhaus, Illustration of A038712 and A080277.
David Eppstein, 1317131 and majorization by subsequences.
Fabrizio Frati, M. Patrignani, and V. Roselli, LR-Drawings of Ordered Rooted Binary Trees and Near-Linear Area Drawings of Outerplanar Graphs, arXiv preprint arXiv:1610.02841 [cs.CG], 2016.
Malgorzata J. Krawczyk, Paweł Oświęcimka, and Krzysztof Kułakowski, Ordered Avalanches on the Bethe Lattice, Entropy, Vol. 21, (2019) 968.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions.
Ralf Stephan, Table of generating functions.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index entries for sequences related to binary expansion of n.
Index entries for sequences related to Nim-sums.

A038713 translated from binary, diagonals of A003987 on either side of main diagonal.
Cf. A062383. Partial sums give A080277.
Bisection of A089312. Cf. A088837.
a(n)-1 is exponent of 2 in A089893(n).
Cf. A130093.
This is Guy Steele's sequence GS(6, 2) (see A135416).
Cf. A001620, A168312, A220466, A361019 (Dirichlet inverse).

int a(int n) { return n ^ (n-1); } // Russ Cox, May 15 2007

import Data.Bits (xor)
a038712 n = n `xor` (n - 1) :: Integer  -- Reinhard Zumkeller, Apr 23 2012

nmax:=98: for p from 0 to ceil(simplify(log[2](nmax))) do for n from 1 to ceil(nmax/(p+2)) do a((2*n-1)*2^p) := 2^(p+1)-1 od: od: seq(a(n), n=1..nmax); # Johannes W. Meijer, Feb 01 2013
# second Maple program:
a:= n-> Bits[Xor](n, n-1):
seq(a(n), n=1..98);  # Alois P. Heinz, Feb 02 2023

Table[Denominator[DivisorSigma[1, 2*n]/DivisorSigma[1, n]], {n, 1, 128}]
Table[BitXor[(n + 1), n], {n, 0, 100}] (* Vladimir Joseph Stephan Orlovsky, Jul 19 2011 *)

vector(66,n,bitxor(n-1,n)) \\ Joerg Arndt, Sep 01 2013; corrected by Michel Marcus, Aug 02 2018

A038712(n) = ((1<<(1+valuation(n,2)))-1); \\ Antti Karttunen, Nov 24 2024

def A038712(n): return n^(n-1) # Chai Wah Wu, Jul 05 2022

a(n) = A110654(n-1) XOR A008619(n). - Reinhard Zumkeller, Feb 05 2007
a(n) = 2^A001511(n) - 1 = 2*A006519(n) - 1 = 2^(A007814(n)+1) - 1.
Multiplicative with a(2^e) = 2^(e+1)-1, a(p^e) = 1, p > 2. - Vladeta Jovovic, Nov 06 2001; corrected by Jianing Song, Aug 03 2018
Sum_{n>0} a(n)*x^n/(1+x^n) = Sum_{n>0} x^n/(1-x^n). Inverse Moebius transform of A048298. - Vladeta Jovovic, Jan 02 2003
From Ralf Stephan, Jun 15 2003: (Start)
G.f.: Sum_{k>=0} 2^k*x^2^k/(1 - x^2^k).
a(2*n+1) = 1, a(2*n) = 2*a(n)+1. (End)
Equals A130093 * [1, 2, 3, ...]. - Gary W. Adamson, May 13 2007
Sum_{i=1..n} (-1)^A000120(n-i)*a(i) = (-1)^(A000120(n)-1)*n. - Vladimir Shevelev, Mar 17 2009
Dirichlet g.f.: zeta(s)/(1 - 2^(1-s)). - R. J. Mathar, Mar 10 2011
a(n) = A086799(2*n) - 2*n. - Reinhard Zumkeller, Aug 07 2011
a((2*n-1)*2^p) = 2^(p+1)-1, p >= 0. - Johannes W. Meijer, Feb 01 2013
a(n) = A000225(A001511(n)). - Omar E. Pol, Aug 31 2013
a(n) = A000203(n)/A000593(n). - Ivan N. Ianakiev and Omar E. Pol, Dec 14 2017
L.g.f.: -log(Product_{k>=0} (1 - x^(2^k))) = Sum_{n>=1} a(n)*x^n/n. - Ilya Gutkovskiy, Mar 15 2018
a(n) = 2^(1 + (A183063(n)/A001227(n))) - 1. - Omar E. Pol, Nov 06 2018
a(n) = sigma(n)/(sigma(2*n) - 2*sigma(n)) = 3*sigma(n)/(sigma(4*n) - 4*sigma(n)) = 7*sigma(n)/(sigma(8*n) - 8*sigma(n)), where sigma(n) = A000203(n). - Peter Bala, Jun 10 2022
Sum_{k=1..n} a(k) ~ n*log_2(n) + (1/2 + (gamma - 1)/log(2))*n, where gamma is Euler's constant (A001620). - Amiram Eldar, Nov 24 2022
a(n) = Sum_{d divides n} m(d)*phi(d), where m(n) = Sum_{d divides n} (-1)^(d+1)* mobius(d). - Peter Bala, Jan 23 2024

Definition corrected by N. J. A. Sloane, Sep 07 2015 at the suggestion of Marc LeBrun

Name corrected by Wolfdieter Lang, Aug 30 2016

A060819 a(n) = n / gcd(n,4).

Original entry on oeis.org

1, 1, 3, 1, 5, 3, 7, 2, 9, 5, 11, 3, 13, 7, 15, 4, 17, 9, 19, 5, 21, 11, 23, 6, 25, 13, 27, 7, 29, 15, 31, 8, 33, 17, 35, 9, 37, 19, 39, 10, 41, 21, 43, 11, 45, 23, 47, 12, 49, 25, 51, 13, 53, 27, 55, 14, 57, 29, 59, 15, 61, 31, 63, 16, 65, 33, 67, 17, 69, 35, 71, 18, 73, 37, 75, 19

Offset: 1

Len Smiley, Apr 30 2001

From Peter Bala, Feb 19 2019: (Start)
We make some general remarks about the sequence a(n) = numerator(n/(n + k)) = n/gcd(n,k) for k a fixed positive integer. The present sequence is the case k = 4. Several other cases are listed in the Crossrefs. In addition to being multiplicative these sequences are also strong divisibility sequences, that is, gcd(a(n),a(m)) = a(gcd(n, m)) for n, m >= 1. In particular, it follows that a(n) is a divisibility sequence: if n divides m then a(n) divides a(m).
By the multiplicativeness and strong divisibility property of the sequence a(n) it follows that if gcd(n, m) = 1 then a(a(n)*a(m) ) = a(a(n)) * a(a(m)), a(a(a(n))*a(a(m)) ) = a(a(a(n))) * a(a(a(m))) and so on.
The sequence a(n) has the rational generating function Sum_{d divides k} f(d)*x^d/(1 - x^d)^2, where f(n) is the Dirichlet inverse of the Euler totient function A000010. f(n) is a multiplicative function defined on prime powers p^k by f(p^k) = 1 - p. See A023900. Cf. A181318. (End)

			From _Peter Bala_, Feb 21 2019: (Start)
Sum_{n >= 1} n*a(n)*x^n = G(x) - 2*G(x^2) - 4*G(x^4), where G(x) = x*(1 + x)/(1 - x)^3.
Sum_{n >= 1} (1/n)*a(n)*x^n = H(x) - (1/2)*H(x^2) - (1/4)*H(x^4), where H(x) = x/(1 - x).
Sum_{n >= 1} (1/n^2)*a(n)*x^n = L(x) - (1/2^2)*L(x^2) - (1/4^2)*L(x^4), where L(x) = Log(1/(1 - x)).
Sum_{n >= 1} (1/a(n))*x^n = L(x) + (1/2)*L(x^2) + (1/2)*L(x^4). (End)

Harry J. Smith, Table of n, a(n) for n = 1..1000
Peter Bala, A note on the sequence of numerators of a rational function, 2019.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,2,0,0,0,-1).

Cf. A026741, A051176, A060791, A060789. Cf. Other sequences given by the formula numerator(n/(n + k)): A106608 thru A106612 (k = 7 thru 11), A051724 (k = 12), A106614 thru A106621 (k = 13 thru 20).

Cf. A000010, A023900, A061037, A061038, A109008, A145979, A167192, A176895, A181318, A220466.

List([1..80],n->n/Gcd(n,4)); # Muniru A Asiru, Feb 20 2019

a060819 n = n `div` a109008 n  -- Reinhard Zumkeller, Nov 25 2013

[n/GCD(n,4): n in [1..80]]; // G. C. Greubel, Sep 19 2018

A060819 := n -> numer(1/2-1/(n+2)): seq(A060819(n),n=1..75); # Gary Detlefs, Sep 16 2011

Mathematica
```
f[n_]:= n/GCD[n, 4]; Array[f, 80]
```

a(n) = { n / gcd(n, 4) } \\ Harry J. Smith, Jul 12 2009

[lcm(n,4)/4 for n in (1..80)] # Zerinvary Lajos, Jun 07 2009

G.f.: x*(1 +x +3*x^2 +x^3 +3*x^4 +x^5 +x^6)/(1 - x^4)^2.
a(n) = 2*a(n-4) - a(n-8).
a(n) = (n/16)*(11 - 5*(-1)^n - i^n - (-i)^n). - Ralf Stephan, Mar 15 2003
a(2*n+1) = a(4*n+2) = 2*n+1, a(4*n+4) = n+1. - Ralf Stephan, Jun 10 2005
Multiplicative with a(2^e) = 2^max(0, e-2), a(p^e) = p^e, p >= 3. - Mitch Harris, Jun 29 2005
a(n) = A167192(n+4,4). - Reinhard Zumkeller, Oct 30 2009
From R. J. Mathar, Apr 18 2011: (Start)
a(n) = A109045(n)/4.
Dirichlet g.f.: zeta(s-1)*(1-1/2^s-1/2^(2s)). (End)
a(n+4) - a(n) = A176895(n).  - Paul Curtz, Apr 05 2011
a(n) = numerator(Sum_{k=1..n} 1/((k+1)*(k+2))). This summation has a closed form of 1/2 - 1/(n+2) and denominator of A145979(n). - Gary Detlefs, Sep 16 2011
a((2*n-1)*2^p) = ceiling(2^(p-2))*(2*n-1), p >= 0 and n >= 1. - Johannes W. Meijer, Feb 06 2013
a(n) = n / A109008(n). - Reinhard Zumkeller, Nov 25 2013
a(n) = denominator((2n-4)/n). - Wesley Ivan Hurt, Dec 22 2016
From Peter Bala, Feb 21 2019: (Start)
O.g.f.: Sum_{n >= 0} a(n)*x^n = F(x) - F(x^2) - F(x^4), where F(x) = x/(1 - x)^2.
More generally, Sum_{n >= 0} (a(n)^m)*x^n = F(m,x) + (1 - 2^m)*( F(m,x^2) + F(m,x^4) ), where F(m,x) = A(m,x)/(1 - x)^(m+1) with A(m,x) the m_th Eulerian polynomial: A(1,x) = x, A(2,x) = x*(1 + x), A(3,x) = x*(1 + 4*x + x^2) - see A008292.
Repeatedly applying the Euler operator x*d/dx or its inverse operator to the o.g.f. for the sequence a(n) produces generating functions for the sequences ((n^m)*a(n))n>=1 for m in Z. Some examples are given below.
(End)
Sum_{k=1..n} a(k) ~ (11/32) * n^2. - Amiram Eldar, Nov 25 2022
E.g.f.: x*(8*cosh(x) + sin(x) + 3*sinh(x))/8. - Stefano Spezia, Dec 02 2023

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

Showing 1-10 of 39 results. Next

cp's OEIS Frontend

A007814 Exponent of highest power of 2 dividing n, a.k.a. the binary carry sequence, the ruler sequence, or the 2-adic valuation of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

Magma

Maple

Mathematica

PARI

Python

Python

R

Scheme

Formula

Extensions

A000265 Remove all factors of 2 from n; or largest odd divisor of n; or odd part of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Java

Julia

Magma

Maple

Mathematica

PARI

Python

Python

SageMath

Scheme

Formula

Extensions

A001511 The ruler function: exponent of the highest power of 2 dividing 2n. Equivalently, the 2-adic valuation of 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Haskell

MATLAB

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Python

Sage

Scheme

Formula

Extensions

A026741 a(n) = n if n odd, n/2 if n even.

Views

Author

Keywords

Comments

Examples

References