A269597 - OEIS

A269597

Irregular triangle giving in row n the larger of the two roots of x^2 + b modulo prime(n) from {0, 1, ..., prime(n)-1} corresponding to b from row n of A269595.

1, 2, 3, 4, 5, 4, 6, 8, 7, 9, 6, 10, 8, 7, 10, 11, 9, 12, 13, 10, 9, 14, 12, 15, 11, 16, 13, 15, 12, 16, 11, 14, 10, 17, 18, 15, 19, 17, 14, 20, 13, 12, 21, 16, 18, 22, 17, 24, 16, 20, 15, 22, 25, 19, 26, 23, 21, 18, 27, 28

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

The length of row n >= 2 is (prime(n)-1)/2 = A005097(n-1), and for row n = 1 it is 1.

The other roots of x^2 + b modulo prime(n) from {0, 1, ..., prime(n)-1} are given in A269596.

See A269595 for the irregular triangle with the quadratic residues -b modulo prime(n) = A000040(n), for n >= 1. For n=1 (prime 2) there is a double root x1 = x2 = 1 of x^2 + 1 (mod 2).

Each row n >= 2 consists of a certain permutation of (prime(n)+1)/2, ..., prime(n) - 1.

For a(n), n >= 2, see column x_2 of the table in the Wolfdieter Lang link.

LINKS

Table of n, a(n) for n=1..60.

Wolfdieter Lang, Note on a Recurrence for Approximation Sequences of p-adic Square Roots

FORMULA

T(n, k) gives the larger zero of x^2 + A269595(n, k) == 0 (mod prime(n)), n >= 1, for k=1 if n=1 and k = 1, 2, ..., (prime(n)-1)/2 = A005097(n-1) for n >= 2. Only representatives from the smallest nonnegative complete residue class modulo prime(n) are considered.

T(n, k) = prime(n) - A269596(n, k).

EXAMPLE

The irregular triangle begins (P(n) stands here for prime(n)):

n, P(n)\k 1 2 3 4 5 6 7 8 9 10 11 12 13 14

1, 2: 1

2, 3: 2

3, 5: 3 4

4, 7: 5 4 6

5, 11: 8 7 9 6 10

6: 13: 8 7 10 11 9 12

7, 17: 13 10 9 14 12 15 11 16

8, 19: 13 15 12 16 11 14 10 17 18

9, 23: 15 19 17 14 20 13 12 21 16 18 22

10, 29: 17 24 16 20 15 22 25 19 26 23 21 18 27 28

...

Row n=7, prime 17 has the permutation (in cycle notation) (9,13,12,14,15,11) (10) (16) of {9, 10, ..., 16}.

MATHEMATICA

nn = 12; s = Table[Select[Range[Prime@ n - 1], JacobiSymbol[#, Prime@ n] == 1 &], {n, nn}]; t = Table[Prime@ n - s[[n, (Prime@ n - 1)/2 - k + 1]], {n, Length@ s}, {k, (Prime@ n - 1)/2}] /. {} -> {1}; Prepend[Table[SelectFirst[Range[#, 1, -1], Function[x, Mod[x^2 + t[[n, k]], #] == 0]] &@ Prime@ n, {n, 2, Length@ t}, {k, (Prime@ n - 1)/2}], {1}] // Flatten (* Michael De Vlieger, Apr 04 2016, Version 10 *)

CROSSREFS

Cf. A000040, A005097, A269595, A269596 (x1).

Sequence in context: A303233 A137912 A324196 * A233775 A118577 A377070

Adjacent sequences: A269594 A269595 A269596 * A269598 A269599 A269600

KEYWORD

nonn,tabf,easy

AUTHOR

Wolfdieter Lang, Apr 03 2016

STATUS

approved