A343501 -id:A343501 - cp's OEIS frontend

A003324 A nonrepetitive sequence.

1, 2, 3, 4, 1, 4, 3, 2, 1, 2, 3, 2, 1, 4, 3, 4, 1, 2, 3, 4, 1, 4, 3, 4, 1, 2, 3, 2, 1, 4, 3, 2, 1, 2, 3, 4, 1, 4, 3, 2, 1, 2, 3, 2, 1, 4, 3, 2, 1, 2, 3, 4, 1, 4, 3, 4, 1, 2, 3, 2, 1, 4, 3, 4, 1, 2, 3, 4, 1

Offset: 1

N. J. A. Sloane

Let b(0) be the sequence 1,2,3,4. Proceeding by induction, let b(n) be a sequence of length 2^(n+2). Quarter b(n) into four blocks, A,B,C,D each of length 2^n, so that b(n) = ABCD. Then b(n+1) = ABCDADCB. [After Dean paper.] - Sean A. Irvine, Apr 20 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 1..10000
Richard A. Dean, A sequence without repeats on x, x^{-1}, y, y^{-1}, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.
Françoise Dejean, Sur un Théorème de Thue, J. Combinatorial Theory, vol. 13 A, iss. 1 (1972) 90-99.
N. J. A. Sloane, P. Flor, L. F. Meyers, G. A. Hedlund. M. Gardner, Collection of documents and notes related to A1285, A3270, A3324
Jianing Song, Proof for my formula for A003324

Positions of 1's, 2's, 3's and 4's: A016813, A343500, A004767, A343501.

Cf. A292077.

b[0] = Range[4];
b[n_] := b[n] = Module[{aa, bb, cc, dd}, {aa, bb, cc, dd} = Partition[b[n - 1], 2^(n-1)]; Join[aa, bb, cc, dd, aa, dd, cc, bb] // Flatten];
b[5] (* Jean-François Alcover, Sep 27 2017 *)
a[n_] := If[OddQ[n], Mod[n, 4], Module[{e = IntegerExponent[n, 2], k}, k = (n/2^e - 1)/2; If[OddQ[k + e], 2, 4]]];
Array[a, 100] (* Jean-François Alcover, Apr 19 2021, after Jianing Song *)

a(n) = if(n%2, n%4, my(e=valuation(n,2), k=bittest(n, e+1)); if((k+e)%2, 2, 4)) \\ Jianing Song, Apr 15 2021

def A003324(n): return n&3 if n&1 else 2<<(((n>>(m:=(~n&n-1).bit_length()))+1>>1)+m&1) # Chai Wah Wu, Feb 26 2025

a(n) = n mod 4 for odd n; for even n, write n = (2*k+1) * 2^e, then a(n) = 2 if k+e is odd, 4 if k+e is even. - Jianing Song, Apr 15 2021

Conjecture: a(2*n) = (A292077(n)+1)*2. Confirmed for first 1000 terms. - John Keith, Apr 18 2021 [This conjecture is correct. Write n = (2*k+1) * 2^e. If k+e is even, then we have A292077(n) = 0 and a(2n) = 2; if k+e is odd, then we have A292077(n) = 1 and a(2n) = 4. - Jianing Song, Nov 27 2021]

A209615 Completely multiplicative with a(p^e) = 1 if p == 1 (mod 4), a(p^e) = (-1)^e otherwise.

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

Offset: 1

Michael Somos, Mar 10 2012

Turn sequence of the alternate paperfolding curve. Davis and Knuth define the alternate paperfolding curve by folding a long strip of paper repeatedly in half alternately to the left side or right side, then unfolding it so each crease is 90 degrees (or other angle). a(n) is their d(n) at equation 4.2. Their equation 6.2 (varied to d(2) = -1 as described there) is equivalent to the definition here. The curve is drawn by a unit step forward, turn a(1)*90 degrees left, a unit step forward, turn a(2)*90 degrees left, and so on. - Kevin Ryde, Apr 18 2020

			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 + ...
From _Kevin Ryde_, Apr 18 2020: (Start)
                   ...              alternate
                    | -1           paperfolding
            -1 --->\ \<--- +1         curve
             ^   -1 |      ^
             |      v      |      turns +1 left
  start --> +1     +1 ---> +1        or -1 right
(End)

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.

Jianing Song, Table of n, a(n) for n = 1..10000
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]
Kevin Ryde, Iterations of the Alternate Paperfolding Curve, section "Turn".
Index to divisibility sequences

Cf. A002144, A003324, A034947, A106665, A292077.
Indices of 1: A338692 = A016813 U A343501; indices of -1: A338691 = A004767 U A343500.
Inverse Moebius transform gives A338690.

A209615[n_] := JacobiSymbol[-1, n]*(-1)^IntegerExponent[n, 2];
Array[A209615, 100] (* Paolo Xausa, Feb 26 2025 *)

{a(n) = my(v); if( n==0, 0, v = valuation( n, 2); (-1)^(n/2^v\2 + v))};

{a(n) = if( n!=0, -kronecker( -1, n) * (-1)^if( n!=0, 1 - valuation( n, 2) %2))};

{a(n) = my(A, p, e, f); sign(n) * if( n==0, 0, A = factor(abs(n)); prod( k=1, matsize(A)[1], [p, e] = A[k, ]; (-1)^(e * (p%4 != 1))) )};

def A209615(n): return -1 if ((n>>(m:=(~n&n-1).bit_length()))+1>>1)+m&1^1 else 1 # Chai Wah Wu, Feb 25 2025

G.f.: Sum_{k>=0} (-1)^k * x^(2^k) / (1 + x^(2^(k+1))).
G.f. A(x) satisfies A(x) + A(x^2) = x / (1 + x^2).
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = (v + w) - (u + v)^2 * (1 + 2*(v + w)).
If p is prime then a(p) = 1 if and only if p is in A002144.
a(4*n + 1) = 1, a(4*n + 3) = -1. a(2*n) = a(3*n) = a(-n) = -a(n).
a(n) = -(-1)^A106665(n-1) unless n=0.
a(2n) = -a(n), a(2n+1) = (-1)^n.  [Davis and Knuth equation 4.2] - Kevin Ryde, Apr 18 2020
From Jianing Song, Apr 24 2021: (Start)
a(n) = 1 <=> A003324(n) = 1 or 4, a(n) = -1 <=> A003324(n) = 2 or 3. In other words, a(n) = Legendre(A003324(n), 5) == A003324(n)^2 (mod 5).
a(n) = A034947(n) * (-1)^(v2(n)), where v2(n) = A007814(n) is the 2-adic valuation of n.
Dirichlet g.f.: beta(s)/(1 + 2^(-s)). (End)

A338691 Positions of (-1)'s in A209615.

Original entry on oeis.org

2, 3, 7, 8, 10, 11, 12, 15, 18, 19, 23, 26, 27, 28, 31, 32, 34, 35, 39, 40, 42, 43, 44, 47, 48, 50, 51, 55, 58, 59, 60, 63, 66, 67, 71, 72, 74, 75, 76, 79, 82, 83, 87, 90, 91, 92, 95, 98, 99, 103, 104, 106, 107, 108, 111, 112, 114, 115, 119, 122, 123, 124, 127, 128

Offset: 1

Jianing Song, Apr 24 2021

Also positions of 2's and 3's in A003324.
Also positions of 1's in A292077. - Jianing Song, Nov 27 2021
Numbers of the form (2*k+1) * 2^e where k+e is odd. In other words, union of {(4*m+1) * 2^(2t+1)} and {(4*m+3) * 2^(2t)}, where m >= 0, t >= 0.
Numbers whose quaternary (base-4) expansion ends in 300...00 or 0200..00 or 2200..00. Trailing 0's are not necessary.
There are precisely 2^(N-1) terms <= 2^N for every N >= 1.
Equals A004767 Union A343500.
Complement of A338692. - Jianing Song, Apr 26 2021

			15 is a term since it is in the family {(4*m+3) * 2^(2t)} with m = 3, t = 0.
18 is a term since it is in the family {(4*m+1) * 2^(2t+1)} with m = 2, t = 0.

Jianing Song, Table of n, a(n) for n = 1..8192
Kevin Ryde, Iterations of the Alternate Paperfolding Curve, see index "TurnRight" with a(n) = TurnRight(n-1).

Cf. A209615, A338692 (positions of 1's), A004767 (the odd terms), A343500 (the even terms), A003324, A292077, A343501.

A338691Q[k_] := JacobiSymbol[-1, k]*(-1)^IntegerExponent[k, 2] == -1;
Select[Range[200], A338691Q] (* Paolo Xausa, Feb 26 2025 *)

isA338691(n) = my(e=valuation(n, 2), k=bittest(n, e+1)); (k+e)%2

def A338691(n):
    def f(x): return n+x-sum(((x>>i)-1>>2)+1 for i in range(1,x.bit_length(),2))-sum(((x>>i)-3>>2)+1 for i in range(0,x.bit_length(),2))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 24 2025

a(n) = A343501(n)/2. - Jianing Song, Apr 26 2021

A338692 Positions of 1's in A209615.

Original entry on oeis.org

1, 4, 5, 6, 9, 13, 14, 16, 17, 20, 21, 22, 24, 25, 29, 30, 33, 36, 37, 38, 41, 45, 46, 49, 52, 53, 54, 56, 57, 61, 62, 64, 65, 68, 69, 70, 73, 77, 78, 80, 81, 84, 85, 86, 88, 89, 93, 94, 96, 97, 100, 101, 102, 105, 109, 110, 113, 116, 117, 118, 120, 121, 125, 126

Offset: 1

Jianing Song, Apr 24 2021

Also positions of 1's and 4's in A003324.
Also positions of 0's in A292077. - Jianing Song, Nov 27 2021
Numbers of the form (2*k+1) * 2^e where k+e is even. In other words, union of {(4*m+1) * 2^(2t)} and {(4*m+3) * 2^(2t+1)}, where m >= 0, t >= 0.
Numbers whose quaternary (base-4) expansion ends in 100...00 or 1200..00 or 3200..00. Trailing 0's are not necessary.
There are precisely 2^(N-1) terms <= 2^N for every N >= 1.
Equals A016813 Union A343501.
Complement of A338691. - Jianing Song, Apr 26 2021

			14 is a term since it is in the family {(4*m+3) * 2^(2t+1)} with m = 1, t = 0.
16 is a term since it is in the family {(4*m+1) * 2^(2t)} with m = 0, t = 2.

Jianing Song, Table of n, a(n) for n = 1..8192
Kevin Ryde, Iterations of the Alternate Paperfolding Curve, see index "TurnLeft" with a(n) = TurnLeft(n-1).

Cf. A209615, A338691 (positions of (-1)'s), A016813 (the odd terms), A343501 (the even terms), A003324, A292077, A343500.

A338692Q[k_] := JacobiSymbol[-1, k]*(-1)^IntegerExponent[k, 2] == 1;
Select[Range[200], A338692Q] (* Paolo Xausa, Feb 26 2025 *)

isA338692(n) = my(e=valuation(n, 2), k=bittest(n, e+1)); !((k+e)%2)

def A338692(n):
    def f(x): return n+sum(((x>>i)-1>>2)+1 for i in range(1,x.bit_length(),2))+sum(((x>>i)-3>>2)+1 for i in range(0,x.bit_length(),2))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 27 2025

a(n) = A343500(n)/2. - Jianing Song, Apr 26 2021

A343500 Positions of 2's in A003324.

Original entry on oeis.org

2, 8, 10, 12, 18, 26, 28, 32, 34, 40, 42, 44, 48, 50, 58, 60, 66, 72, 74, 76, 82, 90, 92, 98, 104, 106, 108, 112, 114, 122, 124, 128, 130, 136, 138, 140, 146, 154, 156, 160, 162, 168, 170, 172, 176, 178, 186, 188, 192, 194, 200, 202, 204, 210, 218, 220, 226

Offset: 1

Jianing Song, Apr 17 2021

Numbers of the form (2*k+1) * 2^e where e >= 1, k+e is odd. In other words, union of {(4*m+1) * 2^(2t-1)} and {(4*m+3) * 2^(2t)}, where m >= 0, t > 0.
Numbers whose quaternary (base-4) expansion ends in 300...00 or 0200..00 or 2200..00. At least one trailing zero is required in the first case but not in the latter two cases.
There are precisely 2^(N-2) terms <= 2^N for every N >= 2.
Also even indices of -1 in A209615. - Jianing Song, Apr 24 2021
Complement of A343501 with respect to the even numbers. - Jianing Song, Apr 26 2021

			A003324 starts with 1, 2, 3, 4, 1, 4, 3, 2, 1, 2, 3, 2, 1, 4, 3, 4, ... We have A003324(2) = A003324(8) = A003324(10) = A003324(12) = ... = 2, so this sequence starts with 2, 8, 10, 12, ...

Jianing Song, Table of n, a(n) for n = 1..16384 (all terms <= 2^16).

Cf. A003324, A343501 (positions of 4's), A209615, A338692.

Even terms in A338691.

okQ[n_] := If[OddQ[n], False, Module[{e = IntegerExponent[n, 2], k}, k = (n/2^e - 1)/2; OddQ[k + e]]];
Select[Range[1000], okQ] (* Jean-François Alcover, Apr 19 2021, after PARI *)

isA343500(n) = if(n%2, 0, my(e=valuation(n, 2), k=bittest(n,e+1)); (k+e)%2)

def A343500(n):
    def f(x): return n+x-sum(((x>>i)-1>>2)+1 for i in range(1,x.bit_length(),2))-sum(((x>>i)-3>>2)+1 for i in range(2,x.bit_length(),2))
    m, k = n, f(n)
    while m != k: m, k = k, f(k)
    return m # Chai Wah Wu, Feb 25 2025

a(n) = 2*A338692(n). - Hugo Pfoertner, Apr 26 2021

cp's OEIS Frontend

A003324 A nonrepetitive sequence.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A209615 Completely multiplicative with a(p^e) = 1 if p == 1 (mod 4), a(p^e) = (-1)^e otherwise.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

Formula

A338691 Positions of (-1)'s in A209615.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A338692 Positions of 1's in A209615.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A343500 Positions of 2's in A003324.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula