A099545 -id:A099545 - cp's OEIS frontend

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

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, 7, 15, 1, 17, 9, 19, 5, 21, 11, 23, 3, 25, 13, 27, 7, 29, 15, 31, 1, 33, 17, 35, 9, 37, 19, 39, 5, 41, 21, 43, 11, 45, 23, 47, 3, 49, 25, 51, 13, 53, 27, 55, 7, 57, 29, 59, 15, 61, 31, 63, 1, 65, 33, 67, 17, 69, 35, 71, 9, 73, 37, 75, 19, 77

Offset: 1

N. J. A. Sloane

When n > 0 is written as k*2^j with k odd then k = A000265(n) and j = A007814(n), so: when n is written as k*2^j - 1 with k odd then k = A000265(n+1) and j = A007814(n+1), when n > 1 is written as k*2^j + 1 with k odd then k = A000265(n-1) and j = A007814(n-1).
Also denominator of 2^n/n (numerator is A075101(n)). - Reinhard Zumkeller, Sep 01 2002
Slope of line connecting (o, a(o)) where o = (2^k)(n-1) + 1 is 2^k and (by design) starts at (1, 1). - Josh Locker (joshlocker(AT)macfora.com), Apr 17 2004
Numerator of n/2^(n-1). - Alexander Adamchuk, Feb 11 2005
From Marco Matosic, Jun 29 2005: (Start)
"The sequence can be arranged in a table:
                          1
                       1  3  1
                    1  5  3  7  1
              1  9  5 11  3 13  7 15  1
  1 17  9 19  5 21 11 23  3 25 13 27  7 29 15 31  1
Every new row is the previous row interspaced with the continuation of the odd numbers.
Except for the ones; the terms (t) in each column are t+t+/-s = t_+1. Starting from the center column of threes and working to the left the values of s are given by A000265 and working to the right by A000265." (End)
This is a fractal sequence. The odd-numbered elements give the odd natural numbers. If these elements are removed, the original sequence is recovered. - Kerry Mitchell, Dec 07 2005
2k + 1 is the k-th and largest of the subsequence of k terms separating two successive equal entries in a(n). - Lekraj Beedassy, Dec 30 2005
It's not difficult to show that the sum of the first 2^n terms is (4^n + 2)/3. - Nick Hobson, Jan 14 2005
In the table, for each row, (sum of terms between 3 and 1) - (sum of terms between 1 and 3) = A020988. - Eric Desbiaux, May 27 2009
This sequence appears in the analysis of A160469 and A156769, which resemble the  numerator and denominator of the Taylor series for tan(x). - Johannes W. Meijer, May 24 2009
Indices n such that a(n) divides 2^n - 1 are listed in A068563. - Max Alekseyev, Aug 25 2013
From Alexander R. Povolotsky, Dec 17 2014: (Start)
With regard to the tabular presentation described in the comment by Marco Matosic: in his drawing, starting with the 3rd row, the first term in the row, which is equal to 1 (or, alternatively the last term in the row, which is also equal to 1), is not in the actual sequence and is added to the drawing as a fictitious term (for the sake of symmetry); an actual A000265(n) could be considered to be a(j,k) (where j >= 1 is the row number and k>=1 is the column subscript), such that a(j,1) = 1:
  1
  1  3
  1  5  3  7
  1  9  5 11  3 13  7 15
  1 17  9 19  5 21 11 23  3 25 13 27  7 29 15 31
and so on ... .
The relationship between k and j for each row is 1 <= k <= 2^(j-1). In this corrected tabular representation, Marco's notion that "every new row is the previous row interspaced with the continuation of the odd numbers" remains true. (End)
Partitions natural numbers to the same equivalence classes as A064989. That is, for all i, j: a(i) = a(j) <=> A064989(i) = A064989(j). There are dozens of other such sequences (like A003602) for which this also holds: In general, all sequences for which a(2n) = a(n) and the odd bisection is injective. - Antti Karttunen, Apr 15 2017
From Paul Curtz, Feb 19 2019: (Start)
This sequence is the truncated triangle:
   1,  1;
   3,  1,  5;
   3,  7,  1,  9;
   5, 11,  3, 13,  7;
  15,  1, 17,  9, 19,  5;
  21, 11, 23,  3, 25, 13, 27;
   7, 29, 15, 31,  1, 33, 17, 35;
  ...
The first column is A069834. The second column is A213671. The main diagonal is A236999. The first upper diagonal is A125650 without 0.
c(n) = ((n*(n+1)/2))/A069834 = 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 2, 2, 1, 1, 8, 8, 1, 1, ... for n > 0. n*(n+1)/2 is the rank of A069834. (End)
As well as being multiplicative, a(n) is a strong divisibility sequence, that is, gcd(a(n),a(m)) = a(gcd(n,m)) for n, m >= 1. In particular, a(n) is a divisibility sequence: if n divides m then a(n) divides a(m). - Peter Bala, Feb 27 2019
a(n) is also the map n -> A026741(n) applied at least A007814(n) times. - Federico Provvedi, Dec 14 2021

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

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).

Daniel Forgues, Table of n, a(n) for n = 1..100000 (first 10000 terms from T. D. Noe)
Peter Bala, A note on the sequence of numerators of a rational function
V. Daiev and J. L. Brown, Problem H-81, Fib. Quart., 6 (1968), 52.
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Eric Weisstein's World of Mathematics, Odd Part
Eric Weisstein's World of Mathematics, Trigonometry Angles
Eric Weisstein's World of Mathematics, Sphere Line Picking

Cf. A000004, A000010, A000123, A000217, A000225, A000265, A001227.
Cf. A003602, A003961, A006516, A006519, A007814, A008683, A014577.
Cf. A020988, A025480, A026741, A027750, A035263, A038502, A049606.
Cf. A064989, A065330, A068563, A069834, A075101, A111929, A111930.
Cf. A111918, A111919, A111920, A111921, A111922, A111923, A125650.
Cf. A127793, A132739, A132740, A156769, A160469, A182469, A209308.
Cf. A213671, A220466, A236999, A242603.
Cf. A049606 (partial products), A135013 (partial sums), A099545 (mod 4), A326937 (Dirichlet inverse).
Cf. A026741 (map), A001511 (converging steps), A038550 (prime index).
Cf. A195056 (Dgf at s=3).

a000265 = until odd (`div` 2)
-- Reinhard Zumkeller, Jan 08 2013, Apr 08 2011, Oct 14 2010

int A000265(n){
    while(n%2==0) n>>=1;
    return n;
}
/* Aidan Simmons, Feb 24 2019 */

using IntegerSequences
[OddPart(n) for n in 1:77] |> println  # Peter Luschny, Sep 25 2021

A000265:= func< n | n/2^Valuation(n,2) >;
[A000265(n): n in [1..120]]; // G. C. Greubel, Jul 31 2024

A000265:=proc(n) local t1,d; t1:=1; for d from 1 by 2 to n do if n mod d = 0 then t1:=d; fi; od; t1; end: seq(A000265(n), n=1..77);
A000265 := n -> n/2^padic[ordp](n,2): seq(A000265(n), n=1..77); # Peter Luschny, Nov 26 2010

a[n_Integer /; n > 0] := n/2^IntegerExponent[n, 2]; Array[a, 77] (* Josh Locker *)
a[ n_] := If[ n == 0, 0, n / 2^IntegerExponent[ n, 2]]; (* Michael Somos, Dec 17 2014 *)

{a(n) = n >> valuation(n, 2)}; /* Michael Somos, Aug 09 2006, edited by M. F. Hasler, Dec 18 2014 */

from _future_ import division
def A000265(n):
    while not n % 2:
        n //= 2
    return n # Chai Wah Wu, Mar 25 2018

def a(n):
    while not n&1: n >>= 1
    return n
print([a(n) for n in range(1, 78)]) # Michael S. Branicky, Jun 26 2025

def A000265(n): return n//2^valuation(n,2)
[A000265(n) for n in (1..121)] # G. C. Greubel, Jul 31 2024

(define (A000265 n) (let loop ((n n)) (if (odd? n) n (loop (/ n 2))))) ;; Antti Karttunen, Apr 15 2017

a(n) = if n is odd then n, otherwise a(n/2). - Reinhard Zumkeller, Sep 01 2002
a(n) = n/A006519(n) = 2*A025480(n-1) + 1.
Multiplicative with a(p^e) = 1 if p = 2, p^e if p > 2. - David W. Wilson, Aug 01 2001
a(n) = Sum_{d divides n and d is odd} phi(d). - Vladeta Jovovic, Dec 04 2002
G.f.: -x/(1 - x) + Sum_{k>=0} (2*x^(2^k)/(1 - 2*x^(2^(k+1)) + x^(2^(k+2)))). - Ralf Stephan, Sep 05 2003
(a(k), a(2k), a(3k), ...) = a(k)*(a(1), a(2), a(3), ...) In general, a(n*m) = a(n)*a(m). - Josh Locker (jlocker(AT)mail.rochester.edu), Oct 04 2005
a(n) = Sum_{k=0..n} A127793(n,k)*floor((k+2)/2) (conjecture). - Paul Barry, Jan 29 2007
Dirichlet g.f.: zeta(s-1)*(2^s - 2)/(2^s - 1). - Ralf Stephan, Jun 18 2007
a(A132739(n)) = A132739(a(n)) = A132740(n). - Reinhard Zumkeller, Aug 27 2007
a(n) = 2*A003602(n) - 1. - Franklin T. Adams-Watters, Jul 02 2009
a(n) = n/gcd(2^n,n). (This also shows that the true offset is 0 and a(0) = 0.) - Peter Luschny, Nov 14 2009
a(-n) = -a(n) for all n in Z. - Michael Somos, Sep 19 2011
From Reinhard Zumkeller, May 01 2012: (Start)
A182469(n, k) = A027750(a(n), k), k = 1..A001227(n).
a(n) = A182469(n, A001227(n)). (End)
a((2*n-1)*2^p) = 2*n - 1, p >= 0 and n >= 1. - Johannes W. Meijer, Feb 05 2013
G.f.: G(0)/(1 - 2*x^2 + x^4) - 1/(1 - x), where G(k) = 1 + 1/(1 - x^(2^k)*(1 - 2*x^(2^(k+1)) + x^(2^(k+2)))/(x^(2^k)*(1 - 2*x^(2^(k+1)) + x^(2^(k+2))) + (1 - 2*x^(2^(k+2)) + x^(2^(k+3)))/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Aug 06 2013
a(n) = A003961(A064989(n)). - Antti Karttunen, Apr 15 2017
Completely multiplicative with a(2) = 1 and a(p) = p for prime p > 2, i.e., the sequence b(n) = a(n) * A008683(n) for n > 0 is the Dirichlet inverse of a(n). - Werner Schulte, Jul 08 2018
From Peter Bala, Feb 27 2019: (Start)
O.g.f.: F(x) - F(x^2) - F(x^4) - F(x^8) - ..., where F(x) = x/(1 - x)^2 is the generating function for the positive integers.
O.g.f. for reciprocals: Sum_{n >= 1} x^n/a(n) = L(x) + (1/2)*L(x^2) + (1/2)*L(x^4) + (1/2)*L(x^8) + ..., where L(x) = log(1/(1 - x)).
Sum_{n >= 1} x^n/a(n) =  1/2*log(G(x)), where G(x) = 1 + 2*x + 4*x^2 + 6*x^3 + 10*x^4 + ... is the o.g.f. of A000123. (End)
O.g.f.: Sum_{n >= 1} phi(2*n-1)*x^(2*n-1)/(1 - x^(2*n-1)), where phi(n) is the Euler totient function A000010. - Peter Bala, Mar 22 2019
a(n) = A049606(n) / A049606(n-1). - Flávio V. Fernandes, Dec 08 2020
a(n) = numerator of n/2^(floor(n/2)). - Federico Provvedi, Dec 14 2021
a(n) = Sum_{d divides n} (-1)^(d+1)*phi(2*n/d). - Peter Bala, Jan 14 2024
a(n) = A030101(A030101(n)). - Darío Clavijo, Sep 19 2024

Additional comments from Henry Bottomley, Mar 02 2000
More terms from Larry Reeves (larryr(AT)acm.org), Mar 14 2000
Name clarified by David A. Corneth, Apr 15 2017

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

A034947 Jacobi (or Kronecker) symbol (-1/n).

Original entry on oeis.org

1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1

Offset: 1

N. J. A. Sloane

Also the regular paper-folding sequence.
For a proof that a(n) equals the paper-folding sequence, see Allouche and Sondow, arXiv v4. - Jean-Paul Allouche and Jonathan Sondow, May 19 2015
It appears that, replacing +1 with 0 and -1 with 1, we obtain A038189. Alternatively, replacing -1 with 0 we obtain (allowing for offset) A014577. - Jeremy Gardiner, Nov 08 2004
Partial sums = A005811 starting (1, 2, 1, 2, 3, 2, 1, 2, 3, ...). - Gary W. Adamson, Jul 23 2008
The congruence in {-1,1} of the odd part of n modulo 4 (Cf. A099545). - Peter Munn, Jul 09 2022

			G.f. = x + x^2 - x^3 + x^4 + x^5 - x^6 - x^7 + x^8 + x^9 + x^10 - x^11 - x^12 + ...

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, pp. 155, 182.
H. Cohen, Course in Computational Number Theory, p. 28.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
J.-P. Allouche, G.-N. Han, and Jeffrey Shallit, On some conjectures of P. Barry, arXiv:2006.08909 [math.NT], 2020.
J.-P. Allouche and Jonathan Sondow, Summation of rational series twisted by strongly B-multiplicative coefficients, Electron. J. Combin., 22 #1 (2015) P1.59; see p. 8.
J.-P. Allouche and Jonathan Sondow, Summation of rational series twisted by strongly B-multiplicative coefficients, arXiv:1408.5770 [math.NT] v4, 2015; see p. 9.
Jean-Paul Allouche and Leo Goldmakher, Mock characters and the Kronecker symbol, arXiv:1608.03957 [math.NT], 2016.
L. Almodovar, V. H. Moll, H. Quand, Infinite products arising in paperfolding, JIS 19 (2016) # 16.5.1 eq. (1)
Joerg Arndt, Matters Computational (The Fxtbook), section 38.8.4 Differences of the sum of Gray code digits, coefficients of polynomials L.
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 -- 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, CSLI Publications, 2010, pages 571-614. a(n) = d(n) at equation 3.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]
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
Jeffrey Shallit, Cloitre's Self-Generating Sequence, arXiv:2501.00784 [math.CO], 2025. See page 4.
Eric Weisstein's World of Mathematics, Kronecker Symbol.
Index entries for sequences obtained by enumerating foldings.

Cf. A000265, A005811, A000364, A008836, A065339, A097706, A099545, A209615.
Moebius transform of A035184.
Cf. A091072 (indices of 1), A091067 (indices of -1), A371594 (indices of run starts).
The following are all essentially the same sequence: A014577, A014707, A014709, A014710, A034947, A038189, A082410. - N. J. A. Sloane, Jul 27 2012

[KroneckerSymbol(-1,n): n in [1..100]]; // Vincenzo Librandi, Aug 16 2016

with(numtheory): A034947 := n->jacobi(-1,n);

Table[KroneckerSymbol[ -1, n], {n, 0, 100}] (* Corrected by Jean-François Alcover, Dec 04 2013 *)

PARI
```
{a(n) = kronecker(-1, n)};
```

for(n=1, 81, f=factor(n); print1((-1)^sum(s=1, omega(n), f[s, 2]*(Mod(f[s, 1], 4)==3)), ", ")); \\ Arkadiusz Wesolowski, Nov 05 2013

a(n)=direuler(p=1,n,if(p==2,1/(1-kronecker(-4, p)*X)/(1-X),1/(1-kronecker(-4, p)*X))) /* Ralf Stephan, Mar 27 2015 */

a(n) = if(n%2==0, a(n/2), (n+2)%4-2) \\ Peter Munn, Jul 09 2022

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

def A034947(n): return -1 if n>>(-n&n).bit_length()&1 else 1 # Chai Wah Wu, Feb 26 2025

Multiplicative with a(2^e) = 1, a(p^e) = (-1)^(e*(p-1)/2) if p>2.
a(2*n) = a(n), a(4*n+1) = 1, a(4*n+3) = -1, a(-n) = -a(n). a(n) = 2*A014577(n-1)-1.
a(prime(n)) = A070750(n) for n > 1. - T. D. Noe, Nov 08 2004
This sequence can be constructed by starting with w = "empty string", and repeatedly applying the map w -> w 1 reverse(-w) [See Allouche and Shallit p. 182]. - N. J. A. Sloane, Jul 27 2012
a(n) = (-1)^A065339(n) = lambda(A097706(n)), where A065339(n) is number of primes of the form 4*m + 3 dividing n (counted with multiplicity) and lambda is Liouville's function, A008836. - Arkadiusz Wesolowski, Nov 05 2013 and Peter Munn, Jun 22 2022
Sum_{n>=1} a(n)/n = Pi/2, due to F. von Haeseler; more generally, Sum_{n>=1} a(n)/n^(2*d+1) = Pi^(2*d+1)*A000364(d)/(2^(2*d+2)-2)(2*d)! for d >= 0; see Allouche and Sondow, 2015. - Jean-Paul Allouche and Jonathan Sondow, Mar 20 2015
Dirichlet g.f.: beta(s)/(1-2^(-s)) = L(chi_2(4),s)/(1-2^(-s)). - Ralf Stephan, Mar 27 2015
a(n) = A209615(n) * (-1)^(v2(n)), where v2(n) = A007814(n) is the 2-adic valuation of n. - Jianing Song, Apr 24 2021
a(n) = 2 - A099545(n) == A000265(n) (mod 4). - Peter Munn, Jun 22 2022 and Jul 09 2022

cp's OEIS Frontend

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

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

A034947 Jacobi (or Kronecker) symbol (-1/n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

A099551 Odd part of n modulo 10. Final digit of A000265(n).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A099544 Odd part of n modulo 3.

Views

Author

Keywords

Comments