A105198 a(n) = n(n+1)/2 mod 4.

0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0, 1, 3, 2, 2, 3, 1, 0, 0

Offset: 0

Author

Oscar Takeshita, Apr 11 2005

Keywords

• nonn
• easy

Comments

0,1,3,2,2,3,1,0 repeated indefinitely.

If N is any power of 2 then n(n+1)/2 mod N is a repeating pattern of length 2N. Moreover, the first N digits form a permutation P of A={0,1,...,N-1}. The subsequent N digits are P in the reversed order. The technique is useful for the generation of arbitrarily large pseudo-random permutations.

Links

• Antti Karttunen, Table of n, a(n) for n = 0..8191
• O. Y. Takeshita and D. J. Costello, Jr., New Deterministic Interleaver Designs for Turbo-Codes, IEEE Trans. Inform. Theory, vol. 46, no. 6, pp. 1988-2006, Sept. 2000.
• Index entries for linear recurrences with constant coefficients, signature (1,-1,1,-1,1,-1,1).

Crossrefs

Cf. triangular numbers A000217, A105332-A105340.

One less than A110549, A133882 shifted once right, with zero inserted to front.

Programs

Magma

[ -Ceiling(n/2)*(-1)^n mod 4 : n in [0..100]]; // Wesley Ivan Hurt, Jul 13 2014

Maple

for n from 0 to 300 do printf(`%d,`, n*(n+1)/2 mod 4) od: # James Sellers, Apr 21 2005
A105198:=n->-ceil(n/2)*(-1)^n mod 4: seq(A105198(n), n=0..100); # Wesley Ivan Hurt, Jul 13 2014

Mathematica

Table[Mod[-Ceiling[n/2] (-1)^n, 4], {n, 0, 100}] (* Wesley Ivan Hurt, Jul 13 2014 *)

PARI

Vec((x+2*x^2+2*x^4+x^5)/(1-x+x^2-x^3+x^4-x^5+x^6-x^7) + O(x^90)) \\ Michel Marcus, Jul 13 2014

Python

def A105198(n): return (n*(n+1)>>1)&3 # Chai Wah Wu, Apr 17 2025

Scheme

(define (A105198 n) (modulo (* 1/2 n (+ 1 n)) 4)) ;; Antti Karttunen, Aug 10 2017

Formula

From Paul Barry, Jul 26 2005: (Start)

G.f.: (x + 2x^2 + 2x^4 + x^5)/(1 - x + x^2 - x^3 + x^4 - x^5 + x^6 - x^7).

a(n) = a(n-1) - a(n-2) + a(n-3) - a(n-4) + a(n-5) - a(n-6) + a(n-7).

a(n) = cos(3*Pi*n/4 + Pi/4)/2 + (1/2 - sqrt(2)/2)*sin(3*Pi*n/4 + Pi/4) - (1/2 + sqrt(2)/2)*cos(Pi*n/4 + Pi/4) - sin(Pi*n/4 + Pi/4)/2 - cos(Pi*n/2)/2 + sin(Pi*n/2)/2 + 3/2. (End)

a(n) = (((n+1)^5 - n^5 - 1) mod 120)/30. - Gary Detlefs, Mar 25 2012

a(n) = -ceiling(n/2)*(-1)^n mod 4. - Wesley Ivan Hurt, Jul 13 2014

Extensions

More terms from James Sellers, Apr 21 2005