Sequences from Quadratic Residues (Part II)

A Method for Generating New Sequences

An integer r is called a quadratic residue modulo p if it is congruent to a perfect square modulo p:

x2 ≡ r (mod p)

with the number of residues for a given prime given by the equation (p − 1)/2 where the one value x2 = 0 is removed before division by 2.

The methods of Part I are being scaled up to show that they also apply to large primes such as 1193 and 135287. Thus, according to the formula when p = 1193 the number of residues is 596 as shown in Table I. Note that for each value of x there corresponds a unique value of r using the Type I to Type III formulas shown beneath the table:

Table I (Quadratic Residues)
x1...3435...4849...596
r1...3432...111115...895

Each column of numbers corresponds to either of three type of expressions that were introduced in Part I:

Type I: x2 = r + pq; q=0. Thus x2 = r
Type II: x2 = r + pq; q=1. Thus x2 = r + p
Type III: x2 = r + pq; q>1

where q is the quotient and the values of r, r + p and r + pq in the above three types are perfect squares.

The number of values of each type is made is shown as follows, where the square roots of p and 2p are used to calculate the number of values in each type:

Type I = ⌊√1193⌋ = 34 ⟺ columns 1 to 34
Type II = ⌊√2×1193⌋ − ⌊√1193⌋ = 48 − 34 = 14 ⟺ columns 35 to 48
Type III = (p − 1)/2 − (Type I + Type II) = 596 − 48 = 548 ⟺ columns 49 to 596

Accordingly, there are 34 numbers of Type I, 14 of Type II and 548 of Type III. The reason for using p = 1193 is that this prime is used as an example in Recreations in the Theory of Numbers by Albert H. Beiler (1966) (pages 203 and 208). Beiler used it to show the difficulties in finding the value of x without also knowing the value of q.

Sequences Derived from the x2

Two sequences of larger primes are shown in Tables II and III and follow the construction method of Part I. Table II depicts the sequence formed from p = 1193 having an r value of 29. Row 2 gives the initial sequence using a Δ value of 1193 while row 4 gives the rearranged sequence using the Δ values 125 and 1068.

Table II (Sequence for p=1193, r=29)
Δ...-1193-1193-1193 1193119311931193...
x...-1852-659534 1727292041135306
Δs12510681251068125 1068125...
|x|534659172718522920 304541134238

A second large prime 135287 also from the book Recreations in the Theory of Numbers (page 208) produced the following sequence

Type I = ⌊√135287⌋ = 367 ⟺ columns 1 to 367
Type II = ⌊√2×135287⌋ − ⌊√135287⌋ = 520 − 367 = 153 ⟺ columns 368 to 520
Type III = (p − 1)/2 − (Type I + Type II) = 67643 − 520 = 67123 ⟺ columns 521 to 67643

Accordingly, there are 367 numbers of Type I, 153 of Type II and 67123 of Type III.

Table III depicts the sequence with with p = 135287 with an r value of 137. Row 2 gives the initial sequence using a Δ value of 135287 while row 4 gives the rearranged sequence using the Δ values 134551 and 736.

Table III (Sequence for p=135287, r=137)
Δ...-135287-135287-135287 135287135287135287 ...
x...-270206-134919368 135655270942406229
Δs134551736134551736134551 736...
|x|368134919135655270206 270942405493406229

Go to Part III for Finite Sequences from Quadratic Residues. Go back to Part I. Go to homepage.

Copyright © 2022 by Eddie N Gutierrez. E-Mail: enaguti1949@gmail.com