A309873 Period-doubling turn sequence, +1 when the 2-adic valuation of n is even or -1 when odd.

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, -1, 1, 1, 1, -1, 1, -1, 1, -1

Offset

1

Comments

a(n)=+1 when the number of low 0 bits of n is even, and a(n)=-1 when odd. This is the "period doubling" sequence A096268 but using +1,-1. See A096268 and its complement A035263 for more. The number of low 0 bits of n is A007814. a(n) is completely multiplicative since A007814(n*m) = A007814(n) + A007814(m).

a(n) is among some completely multiplicative +1,-1 sequences considered by Davis and Knuth for forming curves by unfolding. a(n) is their d(n) at equation 6.4. The curve can be drawn by successively going forward a unit step and turning by a(n)*angle. Their "bending" angle T is equivalent to turns by 180-T degrees. They draw bending angle 90 degrees which is merely 4 unit squares repeatedly traversed; and bending 60 degrees "Fido" and 120 degrees which are bigger and more interesting. Partial sums A068639 are the directions (net total turn) of the segments.

References

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, 2010, pages 571-614.

Links

Kevin Ryde, Table of n, a(n) for n = 1..4096

Kevin Ryde, Sample Images (and LaTeX source)

Kevin Ryde, Xfractint L-System Specification

Formula

a(n) = (-1)^A007814(n) = -(-1)^A065882(n) = 1 - 2*A096268(n-1) = 2*A035263(n) - 1 = A035263(n) - A096268(n-1).

a(n) = A068639(n) - A068639(n-1).

a(A003159) = 1, a(A036554) = -1.

For prime p, a(p) = -1 if p=2 (even), a(p) = 1 if p odd [Davis and Knuth, which together with completely multiplicative defines a(n)].

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1/3. - Amiram Eldar, Sep 18 2022

Dirichlet g.f.: zeta(s)*(2^s-1)/(2^s+1). - Amiram Eldar, Jan 03 2023

Mathematica

Array[(-1)^IntegerExponent[#, 2] &, 100] (* Amiram Eldar, Aug 22 2019 *)

Prog

(PARI) a(n) = (-1)^valuation(n, 2);
(UCB Logo) ; a(n), and draw "Fido" of Davis and Knuth
to a :n
  output 2*(remainder (bitxor :n :n-1) 3) - 1
end
setheading 90  ; start East
repeat 4095 [ forward 7  ; pixels
              left (a repcount) * 120 ]  ; or try 60 or 90
(Python)
def A309873(n): return -1 if (~n & n-1).bit_length()&1 else 1 # Chai Wah Wu, Dec 26 2022

Crossrefs

Cf. A096268, A035263, A003159, A036554, A007814.

Partial sums A068639.

Sequence in context: A000012 A216430 A232544 * A162511 A157895 A077008

Adjacent sequences: A309870 A309871 A309872 * A309874 A309875 A309876

Keyword

mult,sign,easy

Author

Kevin Ryde, Aug 21 2019

Status

approved