A268922 -id:A268922 - cp's OEIS frontend

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

Offset: 1

Wolfdieter Lang, Apr 03 2016

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.

			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}.

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

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

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 *)

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).

A327302 One of the two successive approximations up to 5^n for the 5-adic integer sqrt(-9). This is the 1 (mod 5) case (except for n = 0).

Original entry on oeis.org

0, 1, 21, 46, 546, 3046, 12421, 59296, 59296, 840546, 8653046, 28184296, 125840546, 369981171, 2811387421, 2811387421, 2811387421, 460575059296, 2749393418671, 10378787949921, 48525760606171, 143893192246796, 2051241825059296, 6819613407090546, 30661471317246796

Offset: 0

Jianing Song, Sep 16 2019

nonn

a(n) is the unique number k in [1, 5^n] and congruent to 1 mod 5 such that k^2 + 9 is divisible by 5^n.

			The unique number k in {1, 6, 11, 16, 21} such that k^2 + 9 is divisible by 25 is k = 21, so a(2) = 21.
The unique number k in {21, 46, 71, 96, 121} such that k^2 + 9 is divisible by 125 is k = 46, so a(3) = 46.
The unique number k in {46, 171, 296, 421, 546} such that k^2 + 9 is divisible by 625 is k = 546, so a(4) = 546.

G. P. Michon, Introduction to p-adic integers, Numericana.

For the digits of sqrt(-9) see A327304 and A327305.
Approximations of 5-adic square roots:
this sequence, A327303 (sqrt(-9));
A324027, A324028 (sqrt(-6));
A268922, A269590 (sqrt(-4));
A048898, A048899 (sqrt(-1));
A324023, A324024 (sqrt(6)).

PARI
```
a(n) = truncate(sqrt(-9+O(5^n)))
```

a(1) = 1; for n >= 2, a(n) is the unique number k in {a(n-1) + m*5^(n-1) : m = 0, 1, 2, 3, 4} such that k^2 + 9 is divisible by 5^n.

For n > 0, a(n) = 5^n - A327303(n).

A269598 Irregular triangle giving T(n, k) = -(2*A269596(n, k))^(prime(n)-2) modulo prime(n) for n >= 2.

Original entry on oeis.org

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

Offset: 2

Wolfdieter Lang, Apr 03 2016

The length of row n >= 2 is (prime(n)-1)/2 = A005097(n-1).
The irregular companion triangle -(2*A269597(n, k))^(prime(n)-2) modulo prime(n) is given in A269599.
These numbers, called z_1 = z_1(x_1,prime(n)), appear in a recurrence for the approximation sequence {x_n(prime(n), b, x1)} of the p-adic integer sqrt(-b) with entries congruent to x1 modulo prime(n). The irregular triangle for the b values is given in  A269595(n, k) for n >= 2 (odd primes), and A269596(n, k) gives the corresponding x1 values.
T(n, k) is the unique solution of the first order congruence 2*A269596(n, k)*z(n, k) + 1 == 0 (mod prime(n)), with 0 <= z(n, k) <= prime(n)-1, for  n >= 2.
For a(n), n >= 2, see column z_1 of the table of the paper given as a Wolfdieter Lang link.

			The irregular triangle T(n, k) 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
2,   3:   1
3,   5:   1  2
4,   7:   5  1  3
5,  11:   9  4  8  1  5
6:  13:   9  1  2  3  8  6
7,  17:   2  6  1 14  5  4  7  8
8,  19:  11  7  4  3 13 17  1 14  9
9,  23:  10 20 21 14 19  8  1 17 18 16 11
10, 29:   6 26 10  8  1  2 18 13 24 12  9 25  7 14
...
T(5, 3) = 8  because 2*A269596(5, 3)*8 + 1 = 2*2*8 + 1 = 33 == 0 mod 11, hence modp(33, 11) = 0 , and 8 is the unique nonnegative solution <= 10 of 2*A269596(5, 3)*z + 1 == 0 (mod 11).

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

Cf. A000040, A005097, A269596, A269599 (companion).

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}; u = Prepend[Table[SelectFirst[Range@ #, Function[x, Mod[x^2 + t[[n, k]], #] == 0]] &@ Prime@ n, {n, 2, Length@ t}, {k, (Prime@ n - 1)/2}], {1}]; Table[SelectFirst[Range@ #, Function[z, Mod[-(2 u[[n, k]] z + 1), #] == 0]] &@ Prime@ n, {n, 2, Length@ u}, {k, (Prime@ n - 1)/2}] // Flatten (* Michael De Vlieger, Apr 04 2016, Version 10 *)

T(n, k) = modp(-(2*A269596(n, k))^(prime(n) -2), prime(n)), for n >= 2 and k=1, 2, ...., (prime(n)-1)/2, with modp(a, p) giving the number a' from {0, 1, ..., p-1} with a' == a (mod p).

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

A269599 Irregular triangle giving T(n, k) = -(2*A269597(n, k))^(prime(n) -2) modulo prime(n) for n >= 2.

Original entry on oeis.org

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

Offset: 2

Wolfdieter Lang, Apr 03 2016

The length of row n >= 2 is (prime(n)-1)/2 = A005097(n-1).
The irregular companion triangle -(2*A269596(n, k))^(prime(n) -2) modulo prime(n) is given in A269598.
These numbers, called z_2 = z_2(x_2, prime(n)),  appear in a recurrence for the approximation sequence {x_n(prime(n), b, x_2)}  of the p-adic integer sqrt(-b) with entries congruent to x_2 modulo prime(n). The irregular triangle for the b values is given in  A269595(n, k) for n >= 2 (odd primes), and A269597(n, k) gives the corresponding x_2 values.
T(n, k) is the unique solution of the first order congruence 2*A269597(n, k)*z(n, k) + 1 == 0 (mod prime(n)), with 0 <= z(n, k) <= prime(n)-1, for  n >= 2.
For a(n), n >= 2, see column z_2 of the table of the paper given as a Wolfdieter Lang link.

			The irregular triangle T(n, k) 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
2,   3:   2
3,   5:   4  3
4,   7:   2  6 4
5,  11:   2  7 3  10  6
6:  13:   4 12 11 10  5  7
7,  17:  15 11 16  3 12 13 10  9
8,  19:   8 12 15 16  6  2 18  5 10
9,  23:  13  3  2  9  4 15 22  6  5  7 12
10, 29:  23  3 19 21 28 27 11 16  5 17 20  4 22 15
...
T(5, 3) = 3  because 2*A269597(5, 3)*3 + 1 = 2*9*3 + 1 = 55 == 0 mod 11, hence modp(55, 11) = 0, and 3 is the unique nonnegative solution <= 10 of  2*A269597(5, 3)*z + 1 == 0 (mod 11).

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

Cf. A000040, A005097, A269597, A269598 (companion).

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}; u = 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}]; Table[SelectFirst[Range@ #, Function[z, Mod[-(2 u[[n, k]] z + 1), #] == 0]] &@ Prime@ n, {n, 2, Length@ u}, {k, (Prime@ n - 1)/2}] // Flatten (* Michael De Vlieger, Apr 04 2016, Version 10 *)

T(n, k) = modp( -(2*A269597(n, k))^(prime(n) -2), prime(n)), for n >= 2 and k=1, 2, ...., (prime(n)-1)/2, with modp(a, p) giving the number a' from {0, 1, ..., p-1} with a' == a (mod p).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A327302 One of the two successive approximations up to 5^n for the 5-adic integer sqrt(-9). This is the 1 (mod 5) case (except for n = 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A269598 Irregular triangle giving T(n, k) = -(2*A269596(n, k))^(prime(n)-2) modulo prime(n) for n >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A269599 Irregular triangle giving T(n, k) = -(2*A269597(n, k))^(prime(n) -2) modulo prime(n) for n >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula