Newman–Shanks–Williams prime

In mathematics, a Newman–Shanks–Williams prime (NSW prime) is a prime number p which can be written in the form

\( S_{2m+1}=\frac{\left(1 + \sqrt{2}\right)^{2m+1} + \left(1 - \sqrt{2}\right)^{2m+1}}{2}. \)

NSW primes were first described by Morris Newman, Daniel Shanks and Hugh C. Williams in 1981 during the study of finite simple groups with square order.

The first few NSW primes are 7, 41, 239, 9369319, 63018038201, … (sequence A088165 in the OEIS), corresponding to the indices 3, 5, 7, 19, 29, … (sequence A005850 in the OEIS).

The sequence S alluded to in the formula can be described by the following recurrence relation:

\( S_0=1 \, \)
\( S_1=1 \, \)
\( S_n=2S_{n-1}+S_{n-2}\qquad\text{for all }n\geq 2. \)

The first few terms of the sequence are 1, 1, 3, 7, 17, 41, 99, … (sequence A001333 in the OEIS). Each term in this sequence is half the corresponding term in the sequence of companion Pell numbers. These numbers also appear in the continued fraction convergents to √2.
Further reading

Newman, M.; Shanks, D. & Williams, H. C. (1980). "Simple groups of square order and an interesting sequence of primes". Acta Arithmetica. 38 (2): 129–140.

External links

The Prime Glossary: NSW number

vte

Prime number classes
By formula

Fermat (22n + 1) Mersenne (2p − 1) Double Mersenne (22p−1 − 1) Wagstaff (2p + 1)/3 Proth (k·2n + 1) Factorial (n! ± 1) Primorial (pn# ± 1) Euclid (pn# + 1) Pythagorean (4n + 1) Pierpont (2m·3n + 1) Quartan (x4 + y4) Solinas (2m ± 2n ± 1) Cullen (n·2n + 1) Woodall (n·2n − 1) Cuban (x3 − y3)/(x − y) Carol (2n − 1)2 − 2 Kynea (2n + 1)2 − 2 Leyland (xy + yx) Thabit (3·2n − 1) Williams ((b−1)·bn − 1) Mills (⌊A3n⌋)

By integer sequence

Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin

By property

Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient

Base-dependent

Happy Dihedral Palindromic Emirp Repunit (10n − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin Tetradic

Patterns

Twin (p, p + 2) Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) k−Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain/Safe (p, 2p + 1) Cunningham (p, 2p ± 1, 4p ± 3, 8p ± 7, ...) Arithmetic progression (p + a·n, n = 0, 1, 2, 3, ...) Balanced (consecutive p − n, p, p + n)

By size

Titanic (1,000+ digits) Gigantic (10,000+ digits) Mega (1,000,000+ digits) Largest known

Complex numbers

Eisenstein prime Gaussian prime

Composite numbers

Pseudoprime
Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Somer–Lucas Strong Carmichael number Almost prime Semiprime Interprime Pernicious