Jump to content

Williams number: Difference between revisions

Page semi-protected
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
m Reverted edits by 淺井39 (talk) to last version by MusikBot II
Tags: Rollback Reverted
stub down to clear out old X cruft
 
(23 intermediate revisions by 10 users not shown)
Line 1: Line 1:
{{Short description|Class of numbers in number theory}}
{{pp-semi-indef|small=yes}}
{{pp-semi-indef|small=yes}}
{{short description|class of numbers in number theory}}
{{distinguish|Newman–Shanks–Williams prime}}
{{distinguish|Newman–Shanks–Williams prime}}
In [[number theory]], a '''Williams number base ''b''''' is a [[natural number]] of the form <math>(b-1) \cdot b^n-1</math> for integers ''b'' ≥ 2 and ''n'' ≥ 1.<ref>[http://harvey563.tripod.com/wills.txt Williams primes]</ref> The Williams numbers base 2 are exactly the [[Mersenne number]]s.
In [[number theory]], a '''Williams number base ''b''''' is a [[natural number]] of the form <math>(b-1) \cdot b^n-1</math> for integers ''b'' ≥ 2 and ''n'' ≥ 1.<ref>[http://harvey563.tripod.com/wills.txt Williams primes]</ref> The Williams numbers base 2 are exactly the [[Mersenne number]]s.

==Williams prime==


A '''Williams prime''' is a Williams number that is [[prime number|prime]]. They were considered by [[Hugh C. Williams]].<ref>See Table 1 in the last page of the paper: {{cite journal |last=Williams |first=H. C. |author-link=Hugh C. Williams |title= The primality of certain integers of the form 2 ''A'' ''r''<sup>''n''</sup> – 1 |journal=[[Acta Arithmetica|Acta Arith.]] |volume=39 |date=1981 |pages=7–17 |doi=10.4064/aa-39-1-7-17 |doi-access=free }}</ref>
A '''Williams prime''' is a Williams number that is [[prime number|prime]]. They were considered by [[Hugh C. Williams]].<ref>See Table 1 in the last page of the paper: {{cite journal |last=Williams |first=H. C. |author-link=Hugh C. Williams |title= The primality of certain integers of the form 2 ''A'' ''r''<sup>''n''</sup> – 1 |journal=[[Acta Arithmetica|Acta Arith.]] |volume=39 |date=1981 |pages=7–17 |doi=10.4064/aa-39-1-7-17 |doi-access=free }}</ref>


It is conjectured that for every ''b'' ≥ 2, there are infinitely many Williams primes for base ''b''.
Least ''n'' ≥ 1 such that (''b''−1)·''b<sup>n</sup>'' − 1 is prime are: (start with ''b'' = 2)
:2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 2, 1, 14, 1, 1, 2, 6, 1, 1, 1, 55, 12, 1, 133, 1, 20, 1, 2, 1, 1, 2, 15, 3, 1, 7, 136211, 1, 1, 7, 1, 7, 7, 1, 1, 1, 2, 1, 25, 1, 5, 3, 1, 1, 1, 1, 2, 3, 1, 1, 899, 3, 11, 1, 1, 1, 63, 1, 13, 1, 25, 8, 3, 2, 7, 1, 44, 2, 11, 3, 81, 21495, 1, 2, 1, 1, 3, 25, 1, 519, 77, 476, 1, 1, 2, 1, 4983, 2, 2, ...

{|class="wikitable"
|''b''
|numbers ''n'' ≥ 1 such that (''b''−1)×''b''<sup>''n''</sup>−1 is prime (these ''n'' are checked up to 25000)
|[[OEIS]] sequence
|-
|2
|2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, [[43,112,609 (number)|43112609]], 57885161, 74207281, 77232917, 82589933, ...
|{{OEIS link|A000043}}
|-
|3
|1, 2, 3, 7, 8, 12, 20, 23, 27, 35, 56, 62, 68, 131, 222, 384, 387, 579, 644, 1772, 3751, 5270, 6335, 8544, 9204, 12312, 18806, 21114, 49340, 75551, 90012, 128295, 143552, 147488, 1010743, 1063844, 1360104, ...
|{{OEIS link|A003307}}
|-
|4
|1, 2, 3, 9, 17, 19, 32, 38, 47, 103, 108, 153, 162, 229, 235, 637, 1638, 2102, 2567, 6338, 7449, 12845, 20814, 40165, 61815, 77965, 117380, 207420, 351019, 496350, 600523, 1156367, 2117707, 5742009, 5865925, 5947859, ...
|{{OEIS link|A272057}}
|-
|5
|1, 3, 9, 13, 15, 25, 39, 69, 165, 171, 209, 339, 2033, 6583, 15393, 282989, 498483, 504221, 754611, 864751, ...
|{{OEIS link|A046865}}
|-
|6
|1, 2, 6, 7, 11, 23, 33, 48, 68, 79, 116, 151, 205, 1016, 1332, 1448, 3481, 3566, 3665, 11233, 13363, 29166, 44358, 58530, 191706, ...
|{{OEIS link|A079906}}
|-
|7
|1, 2, 7, 18, 55, 69, 87, 119, 141, 189, 249, 354, 1586, 2135, 2865, 2930, 4214, 7167, 67485, 74402, 79326, ...
|{{OEIS link|A046866}}
|-
|8
|3, 7, 15, 59, 6127, 8703, 11619, 23403, 124299, ...
|{{OEIS link|A268061}}
|-
|9
|1, 2, 5, 25, 85, 92, 97, 649, 2017, 2978, 3577, 4985, 17978, 21365, 66002, 95305, 142199, ...
|{{OEIS link|A268356}}
|-
|10
|1, 3, 7, 19, 29, 37, 93, 935, 8415, 9631, 11143, 41475, 41917, 48051, 107663, 212903, 223871, 260253, 364521, 383643, 1009567, ...
|{{OEIS link|A056725}}
|-
|11
|1, 3, 37, 119, 255, 355, 371, 497, 1759, 34863, 50719, 147709, 263893, ...
|{{OEIS link|A046867}}
|-
|12
|1, 2, 21, 25, 33, 54, 78, 235, 1566, 2273, 2310, 4121, 7775, 42249, 105974, 138961, ...
|{{OEIS link|A079907}}
|-
|13
|2, 7, 11, 36, 164, 216, 302, 311, 455, 738, 1107, 2244, 3326, 4878, 8067, 46466, ...
|{{OEIS link|A297348}}
|-
|14
|1, 3, 5, 27, 35, 165, 209, 2351, 11277, 21807, 25453, 52443, ...
|{{OEIS link|A273523}}
|-
|15
|14, 33, 43, 20885, ...
|
|-
|16
|1, 20, 29, 43, 56, 251, 25985, 27031, 142195, 164066, ...
|
|-
|17
|1, 3, 71, 139, 265, 793, 1729, 18069, ...
|
|-
|18
|2, 6, 26, 79, 91, 96, 416, 554, 1910, 4968, ...
|
|-
|19
|6, 9, 20, 43, 174, 273, 428, 1388, ...
|
|-
|20
|1, 219, 223, 3659, ...
|
|-
|21
|1, 2, 7, 24, 31, 60, 230, 307, 750, 1131, 1665, 1827, 8673, ...
|
|-
|22
|1, 2, 5, 19, 141, 302, 337, 4746, 5759, 16530, ...
|
|-
|23
|55, 103, 115, 131, 535, 1183, 9683, ...
|
|-
|24
|12, 18, 63, 153, 221, 1256, 13116, 15593, ...
|
|-
|25
|1, 5, 7, 30, 75, 371, 383, 609, 819, 855, 7130, 7827, 9368, ...
|
|-
|26
|133, 205, 215, 1649, ...
|
|-
|27
|1, 3, 5, 13, 15, 31, 55, 151, 259, 479, 734, 1775, 2078, 6159, 6393, 9013, ...
|
|-
|28
|20, 1091, 5747, 6770, ...
|
|-
|29
|1, 7, 11, 57, 69, 235, 16487, ...
|
|-
|30
|2, 83, 566, 938, 1934, 2323, 3032, 7889, 8353, 9899, 11785, ...
|
|}

{{As of|2018|9}}, the largest known Williams prime base 3 is 2×3<sup>1360104</sup>−1.<ref>[https://primes.utm.edu/primes/page.php?id=120178 The Prime Database: 2&middot;3<sup>1360104</sup>&nbsp;−&nbsp;1]</ref>

==Generalization==

A '''Williams number of the second kind base ''b''''' is a [[natural number]] of the form <math>(b-1) \cdot b^n+1</math> for integers ''b'' ≥ 2 and ''n'' ≥ 1, a '''Williams prime of the second kind ''' is a Williams number of the second kind that is prime. The Williams primes of the second kind base 2 are exactly the [[Fermat prime]]s.

Least ''n'' ≥ 1 such that (''b''−1)·''b<sup>n</sup>'' + 1 is prime are: (start with ''b'' = 2)
:1, 1, 1, 2, 1, 1, 2, 1, 3, 10, 3, 1, 2, 1, 1, 4, 1, 29, 14, 1, 1, 14, 2, 1, 2, 4, 1, 2, 4, 5, 12, 2, 1, 2, 2, 9, 16, 1, 2, 80, 1, 2, 4, 2, 3, 16, 2, 2, 2, 1, 15, 960, 15, 1, 4, 3, 1, 14, 1, 6, 20, 1, 3, 946, 6, 1, 18, 10, 1, 4, 1, 5, 42, 4, 1, 828, 1, 1, 2, 1, 12, 2, 6, 4, 30, 3, 3022, 2, 1, 1, 8, 2, 4, 4, 2, 11, 8, 2, 1, ... {{OEIS|A305531}}

{|class="wikitable"
|''b''
|numbers ''n'' ≥ 1 such that (''b''−1)×''b''<sup>''n''</sup>+1 is prime (these ''n'' are checked up to 25000)
|[[OEIS]] sequence
|-
|2
|1, 2, 4, 8, 16, ...
|
|-
|3
|1, 2, 4, 5, 6, 9, 16, 17, 30, 54, 57, 60, 65, 132, 180, 320, 696, 782, 822, 897, 1252, 1454, 4217, 5480, 6225, 7842, 12096, 13782, 17720, 43956, 64822, 82780, 105106, 152529, 165896, 191814, 529680, 1074726, 1086112, 1175232, ...
|{{OEIS link|A003306}}
|-
|4
|1, 3, 4, 6, 9, 15, 18, 33, 138, 204, 219, 267, 1104, 1408, 1584, 1956, 17175, 21147, 24075, 27396, 27591, 40095, 354984, 400989, 916248, 1145805, 2541153, 5414673, ...
|{{OEIS link|A326655}}
|-
|5
|2, 6, 18, 50, 290, 2582, 20462, 23870, 26342, 31938, 38122, 65034, 70130, 245538, ...
|{{OEIS link|A204322}}
|-
|6
|1, 2, 4, 17, 136, 147, 203, 590, 754, 964, 970, 1847, 2031, 2727, 2871, 5442, 7035, 7266, 11230, 23307, 27795, 34152, 42614, 127206, 133086, ...
|{{OEIS link|A247260}}
|-
|7
|1, 4, 9, 99, 412, 2633, 5093, 5632, 28233, 36780, 47084, 53572, ...
|{{OEIS link|A245241}}
|-
|8
|2, 40, 58, 60, 130, 144, 752, 7462, 18162, 69028, 187272, 268178, 270410, 497284, 713304, 722600, 1005254, ...
|{{OEIS link|A269544}}
|-
|9
|1, 4, 5, 11, 26, 29, 38, 65, 166, 490, 641, 2300, 9440, 44741, 65296, 161930, ...
|{{OEIS link|A056799}}
|-
|10
|3, 4, 5, 9, 22, 27, 36, 57, 62, 78, 201, 537, 696, 790, 905, 1038, 66886, 70500, 91836, 100613, 127240, ...
|{{OEIS link|A056797}}
|-
|11
|10, 24, 864, 2440, 9438, 68272, 148602, ...
|{{OEIS link|A057462}}
|-
|12
|3, 4, 35, 119, 476, 507, 6471, 13319, 31799, ...
|{{OEIS link|A251259}}
|-
|13
|1, 2, 4, 21, 34, 48, 53, 160, 198, 417, 773, 1220, 5361, 6138, 15557, 18098, ...
|
|-
|14
|2, 40, 402, 1070, 6840, ...
|
|-
|15
|1, 3, 4, 9, 11, 14, 23, 122, 141, 591, 2115, 2398, 2783, 3692, 3748, 10996, 16504, ...
|
|-
|16
|1, 3, 11, 12, 28, 42, 225, 702, 782, 972, 1701, 1848, 8556, 8565, 10847, 12111, 75122, 183600, 307400, 342107, 416936, ...
|
|-
|17
|4, 20, 320, 736, 2388, 3344, 8140, ...
|
|-
|18
|1, 6, 9, 12, 22, 30, 102, 154, 600, ...
|
|-
|19
|29, 32, 59, 65, 303, 1697, 5358, 9048, ...
|
|-
|20
|14, 18, 20, 38, 108, 150, 640, 8244, ...
|
|-
|21
|1, 2, 3, 4, 12, 17, 38, 54, 56, 123, 165, 876, 1110, 1178, 2465, 3738, 7092, 8756, 15537, 19254, 24712, ...
|
|-
|22
|1, 9, 53, 261, 1491, 2120, 2592, 6665, 9460, 15412, 24449, ...
|
|-
|23
|14, 62, 84, 8322, 9396, 10496, 24936, ...
|
|-
|24
|2, 4, 9, 42, 47, 54, 89, 102, 118, 269, 273, 316, 698, 1872, 2126, 22272, ...
|
|-
|25
|1, 4, 162, 1359, 2620, ...
|
|-
|26
|2, 18, 100, 1178, 1196, 16644, ...
|
|-
|27
|4, 5, 167, 408, 416, 701, 707, 1811, 3268, 3508, 7020, 7623, 16449, ...
|
|-
|28
|1, 2, 136, 154, 524, 1234, 2150, 2368, 7222, 10082, 14510, 16928, ...
|
|-
|29
|2, 4, 6, 44, 334, 24714, ...
|
|-
|30
|4, 5, 9, 18, 71, 124, 165, 172, 888, 2218, 3852, 17871, 23262, ...
|
|}

{{As of|2018|9}}, the largest known Williams prime of the second kind base 3 is 2×3<sup>1175232</sup>+1.<ref>[https://primes.utm.edu/primes/page.php?id=91957 The Prime Database: 2&middot;3<sup>1175232</sup>&nbsp;+&nbsp;1]</ref>

A '''Williams number of the third kind base ''b''''' is a [[natural number]] of the form <math>(b+1) \cdot b^n-1</math> for integers ''b'' ≥ 2 and ''n'' ≥ 1, the Williams number of the third kind base 2 are exactly the [[Thabit number]]s. A '''Williams prime of the third kind ''' is a Williams number of the third kind that is prime.

A '''Williams number of the fourth kind base ''b''''' is a [[natural number]] of the form <math>(b+1) \cdot b^n+1</math> for integers ''b'' ≥ 2 and ''n'' ≥ 1, a '''Williams prime of the fourth kind ''' is a Williams number of the fourth kind that is prime, such primes do not exist for <math>b \equiv 1 \bmod 3</math>.

{|class="wikitable"
|''b''
|numbers ''n'' such that <math>(b+1) \cdot b^n-1</math> is prime
|numbers ''n'' such that <math>(b+1) \cdot b^n+1</math> is prime
|-
|2
|{{oeis|A002235}}
|{{oeis|A002253}}
|-
|3
|{{oeis|A005540}}
|{{oeis|A005537}}
|-
|5
|{{oeis|A257790}}
|{{oeis|A143279}}
|-
|10
|{{oeis|A111391}}
|(not exist)
|}

It is conjectured that for every ''b'' ≥ 2, there are infinitely many Williams primes of the first kind (the original Williams primes) base ''b'', infinitely many Williams primes of the second kind base ''b'', and infinitely many Williams primes of the third kind base ''b''. Besides, if ''b'' is not = 1 mod 3, then there are infinitely many Williams primes of the fourth kind base ''b''.

==Dual form==

If we let ''n'' take negative values, and choose the [[numerator]] of the numbers, then we get these numbers:

'''Dual Williams numbers of the first kind base ''b''''': numbers of the form <math>b^n-(b-1)</math> with ''b'' ≥ 2 and ''n'' ≥ 1.

'''Dual Williams numbers of the second kind base ''b''''': numbers of the form <math>b^n+(b-1)</math> with ''b'' ≥ 2 and ''n'' ≥ 1.

'''Dual Williams numbers of the third kind base ''b''''': numbers of the form <math>b^n-(b+1)</math> with ''b'' ≥ 2 and ''n'' ≥ 1.

'''Dual Williams numbers of the fourth kind base ''b''''': numbers of the form <math>b^n+(b+1)</math> with ''b'' ≥ 2 and ''n'' ≥ 1. (not exist when ''b'' = 1 mod 3)

Unlike the original Williams primes of each kind, some large dual Williams primes of each kind are only [[probable prime]]s, since for these primes ''N'', neither ''N''−1 not ''N''+1 can be trivially written into a product.

{|class="wikitable"
|''b''
|numbers ''n'' such that <math>b^n-(b-1)</math> is (probable) prime (dual Williams primes of the first kind)
|numbers ''n'' such that <math>b^n+(b-1)</math> is (probable) prime (dual Williams primes of the second kind)
|numbers ''n'' such that <math>b^n-(b+1)</math> is (probable) prime (dual Williams primes of the third kind)
|numbers ''n'' such that <math>b^n+(b+1)</math> is (probable) prime (dual Williams primes of the fourth kind)
|-
|2
|{{oeis|A000043}}
|(see [[Fermat prime]])
|{{oeis|A050414}}
|{{oeis|A057732}}
|-
|3
|{{oeis|A014224}}
|{{oeis|A051783}}
|{{oeis|A058959}}
|{{oeis|A058958}}
|-
|4
|{{oeis|A059266}}
|{{oeis|A089437}}
|{{oeis|A217348}}
|(not exist)
|-
|5
|{{oeis|A059613}}
|{{oeis|A124621}}
|{{oeis|A165701}}
|{{oeis|A089142}}
|-
|6
|{{oeis|A059614}}
|{{oeis|A145106}}
|{{oeis|A217352}}
|{{oeis|A217351}}
|-
|7
|{{oeis|A191469}}
|{{oeis|A217130}}
|{{oeis|A217131}}
|(not exist)
|-
|8
|{{oeis|A217380}}
|{{oeis|A217381}}
|{{oeis|A217383}}
|{{oeis|A217382}}
|-
|9
|{{oeis|A177093}}
|{{oeis|A217385}}
|{{oeis|A217493}}
|{{oeis|A217492}}
|-
|10
|{{oeis|A095714}}
|{{oeis|A088275}}
|{{oeis|A092767}}
|(not exist)
|}

(for the smallest dual Williams primes of the 1st, 2nd and 3rd kinds base ''b'', see {{oeis|A113516}}, {{oeis|A076845}} and {{oeis|A178250}})

It is conjectured that for every ''b'' ≥ 2, there are infinitely many dual Williams primes of the first kind (the original Williams primes) base ''b'', infinitely many dual Williams primes of the second kind base ''b'', and infinitely many dual Williams primes of the third kind base ''b''. Besides, if ''b'' is not = 1 mod 3, then there are infinitely many dual Williams primes of the fourth kind base ''b''.


==See also==
==See also==
* [[Thabit number]], which is exactly the Williams number of the third kind base 2
* [[Thabit number]]


==References==
==References==
Line 384: Line 18:


* [http://matwbn.icm.edu.pl/ksiazki/aa/aa39/aa3912.pdf The primality of certain integers of the form 2''Ar''<sup>''n''</sup>&nbsp;−&nbsp;1]
* [http://matwbn.icm.edu.pl/ksiazki/aa/aa39/aa3912.pdf The primality of certain integers of the form 2''Ar''<sup>''n''</sup>&nbsp;−&nbsp;1]
* [http://www.ams.org/journals/mcom/1972-26-120/S0025-5718-1972-0314747-X/home.html Some prime numbers of the forms 2&middot;3<sup>''n''</sup>&nbsp;+&nbsp;1 and 2&middot;3<sup>''n''</sup>&nbsp;−&nbsp;1]
* [http://www.ams.org/journals/mcom/1972-26-120/S0025-5718-1972-0314747-X/home.html Some prime numbers of the forms 2·3<sup>''n''</sup>&nbsp;+&nbsp;1 and 2·3<sup>''n''</sup>&nbsp;−&nbsp;1]
* [https://www.rieselprime.de/ziki/Williams_prime Williams prime] at PrimeWiki
* Chris Caldwell, [http://primes.utm.edu/primes/home.php The Largest Known Primes Database] at The Prime Pages

* [http://primes.utm.edu/primes/page.php?id=120909 A Williams prime of the first kind base 2: (2−1)·2<sup>74207281</sup> − 1]
* [http://primes.utm.edu/primes/page.php?id=120178 A Williams prime of the first kind base 3: (3−1)·3<sup>1360104</sup> − 1]
* [http://primes.utm.edu/primes/page.php?id=91957 A Williams prime of the second kind base 3: (3−1)·3<sup>1175232</sup> + 1]
* [http://primes.utm.edu/primes/page.php?id=97291 A Williams prime of the first kind base 10: (10−1)·10<sup>383643</sup> − 1]
* [http://primes.utm.edu/primes/page.php?id=109482 A Williams prime of the first kind base 113: (113−1)·113<sup>286643</sup> − 1]
* [https://www.rieselprime.de/ziki/Williams_prime Williams prime] in [[Prime wiki]]
* [https://docs.google.com/document/d/e/2PACX-1vTLI9TAODTtBE9j0kQmMSR9y5YDuN_wI5cdgJZn25snYSAgyR07bLW89vxzhCypiK70YgEqschbavf-/pub List of Williams primes]


{{Prime number classes}}
{{Prime number classes}}
Line 398: Line 26:


[[Category:Classes of prime numbers]]
[[Category:Classes of prime numbers]]
[[Category:Mersenne primes]]

Latest revision as of 06:28, 31 May 2024

Not to be confused with Newman–Shanks–Williams prime.

In number theory, a Williams number base b is a natural number of the form for integers b ≥ 2 and n ≥ 1.[1] The Williams numbers base 2 are exactly the Mersenne numbers.

A Williams prime is a Williams number that is prime. They were considered by Hugh C. Williams.[2]

It is conjectured that for every b ≥ 2, there are infinitely many Williams primes for base b.

See also

References

  1. ^ Williams primes
  2. ^ See Table 1 in the last page of the paper: Williams, H. C. (1981). "The primality of certain integers of the form 2 A rn – 1". Acta Arith. 39: 7–17. doi:10.4064/aa-39-1-7-17.


Retrieved from "https://en.wikipedia.org/w/index.php?title=Williams_number&oldid=1226528870"