Williams Numbers

One of the properties of the number 26342 (my diurnal age as of Monday, May 17th 2021) is that it is a member of OEIS A204322

A204322

Numbers n such that \( 4 \times 5^n + 1\) is prime.

At first glance, this didn't look all that interesting but further investigation led me to discover that \( 4 \times 5^{26342} + 1\) produces what is called a Williams prime of the second kind. These are primes of the form:$$(b-1)\cdot b^{n}+1 \text{ for integers } b \geq 2 \text{ and } n \geq 1$$In this particular case, \(b=5\) and thus \( 4 \times 5^n + 1\). The sequence begins:

0, 2, 6, 18, 50, 290, 2582, 20462, 23870, 26342, 31938, 38122, 65034, 70130, 245538 

These primes becomes very large indeed with increasing \(n\). Let's consider a small value of \(n\) such as \(n=2\). Here we have \(5 \times 6^2+1 = 181\) which is prime. Numbers of the form \((b-1)\cdot b^{n}+1 \) that are not prime are simply called Williams numbers of the second kind. 

Wikipedia has a list of the bases from 2 to 30 along with the indices that produce primes. The Williams primes of the second kind base 2 are exactly the Fermat primes. As of September 2018, the largest known Williams prime of the second kind base 3 is: $$2×3^{1175232}+1$$So what are Williams numbers and primes of the first kind? A Williams number base \(b\) is a natural number of the form: $$(b-1)\cdot b^{n}-1 \text{ for integers } b \geq 2 \text{ and } n \geq 1$$The Williams numbers base 2 are exactly the Mersenne numbers. A Williams prime is a Williams number that is prime. For base 5, the initial Williams primes of the first kind are:

1, 3, 9, 13, 15, 25, 39, 69, 165, 171, 209, 339, 2033, 6583, 15393, 282989, 498483, 504221, 754611, 864751, ...

Looking at the case of \(n=3\), we see that \(4 \times 5^3-1 = 499\) which is prime. 

A Williams number of the third kind base \(b\) is a natural number of the form:$$(b+1)\cdot b^{n}-1 \text{ for integers } b \geq 2 \text{ and } n \geq 1$$The Williams numbers of the third kind base 2 are exactly the Thabit numbers. 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:$$(b+1)\cdot b^{n}+1 \text{ for integers } b \geq 2 \text{ and } n \geq 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 \(b\equiv 1 \bmod {3}\).

So to summarise, a Williams number of whatever kind will conform to this pattern:$$(b \pm 1)\cdot b^{n} \pm 1 \text{ for integers } b \geq 2 \text{ and } n \geq 1$$

Generalised Fermat Primes

Today I turned 26188 days old and this number happens to be associated with the so-called generalised Fermat primes. Before going further, we should establish what is meant by a Fermat prime and a Fermat number. 

A Fermat number \(F_n\) is a number such that \(F_n=2^{2^n}+1\). 

If the number is prime, then we have a Fermat prime. Currently, only five such primes are known and these are:

 \(F_0=3, F_1=5, F_2=17, F_3=257, F_4=65537\)

A generalised Fermat number is a number of the form \(a^{2^n}+1\) where \(a>2\). Only if \(a\) is even can a generalised Fermat number be prime. Now 1024=\(2^{10}\) and so if we look at numbers of the form \(a^{2^{10}}+1\), we find that the values of \(a\) that produce primes are (up to 26188): 

1, 824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, 18336, 19564, 20624, 22500, 24126, 26132, 26188

These numbers form OEIS A057002. Figure 1 shows a plot of these same numbers:

Figure 1

Many of the largest known prime numbers are generalised Fermat numbers. To date (14th December 2020), the largest such prime is:$$1059094^{2^{20}}+1=1059094^{1048576}+1 \text{ which contains } 6317602 \text{ digits }$$This prime was discovered in 2018 but it pales in comparison to a number of larger Mersenne primes, the largest of which (discovered also in 2018) is:$$2^{82589933-1} \text{ which contains } 24862048 \text{ digits }$$A list of the current largest 100 primes can be found here.

It should be noted that there is another less common definition of a generalised Fermat number and that is:$$F_m(a,b)=a^{2m}+b^{2m} \text{ with gcd(\(a,b\))=1}$$I've looked at generalisations or extensions of other number types in the past, specifically:

• Generalised Cunningham Chains
• Fibonacci-like Sequences
• Beyond Fibonacci
• Root-Mean-Square and other Means

UPDATE on Thursday, February 4th 2021

Today I turned 26240 days old and one of the properties of this number, as with 26188 that is dealt with in this post, is that it is a generalised Fermat prime. Furthermore, both numbers belong to OEIS A057002:

A057002

Numbers n such that n^1024 + 1 is prime (a generalized Fermat prime).

In fact, looking at the members of the sequence, we see that there is a cluster of three numbers (26132, 26188, 26240) and Figure 2 makes this even more apparent:

1, 824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, 18336, 19564, 20624, 22500, 24126, 26132, 26188, 26240, 29074, 29658, 30778, 31126, 32244, 33044, 34016, ...

Figure 2: cluster of generalised Fermat primes

Fermat Primes and Brazilian Numbers

Today I turned \( 25156 \) days old and one of the entries, AO63799, in the OEIS (Online Encyclopaedia of Integer Sequences) for this number states that: \( 25156 \) belongs to the set of numbers \( n \) such that n+3, n+5, n+17, n+257, n+65537 are all primes.

At first the numbers \(3, 5, 17, 257 \text{ and } 65537 \) appeared quite arbitrary but helpfully the comment is made that these numbers are the known Fermat primes. These are primes of the form:$$ 2^{2^k} + 1, \text{ for some k } >= 0 $$ It is conjectured that there are only five values of \( k \) that produce such primes, namely \( 0, 1, 2, 3 \text{ and } 4 \) corresponding to \( 3, 5, 17, 257 \text{ and } 65537 \). It has been confirmed that values of k such that \( 5 \leq k \leq 32 \) produce composite numbers.

Of course, these primes are not be confused with the Mersenne primes that are of the form \( 2^k-1 \) and that are probably infinite in number.

In the comments for OEIS AO63799, it's also stated that no Fermat prime is a Brazilian number which of course immediately prompted me to find what defined a Brazilian number. These numbers are listed in OEIS A125134 and defined as:

Numbers \( n \) such that there is a natural number \( b \) with \( 1 < b < n-1 \) such that the representation of \( n \) in base \( b \) has all equal digits.

All even numbers \( \geq \) 8 are Brazilian numbers because \( 2p=2(p-1)+2 \) is written \( 22 \) in base \(p-1 \text{ if } p-1>2 \), that is true if \(p \geq 4 \). The odd Brazilian numbers are listed in OEIS A257521 and are fairly common, with some being prime numbers:

7, 13, 15, 21, 27, 31, 33, 35, 39, 43, 45, 51, 55, 57, 63, 65, 69, 73, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 127, 129, 133, 135, 141, 143, 145, 147, 153, 155, 157, 159, 161, 165, 171, 175, 177, 183, 185, 187, 189, 195, ...

As an example, take 27 in the above sequence which can be expressed as \(33_8 \). As for the even numbers, take a number like 28. It can be written as 2(14-1)+2 and thus can be represented as \(22_{13} \).

Proth-like Numbers

Today's tweet for my numbered days was as follows:

It turns out that this number is part of a class of numbers of the form \(k \times 2^n-1 \) where \(k\) is any odd integer and \(n\) is a natural number. Here is a link to a website that shows values of \(k\) between 1 and 299 and lists some corresponding values of \(n\) that produce prime numbers. Note the site was updated on February 18th 2021.

This information can then be used to easily generate a very large prime number. For example, for \(k=7\) some initial values of \(n\) are:

1, 5, 9, 17, 21, 29, 45, 177, 18381, 22529, 24557, 26109, 34857, 41957, 67421, 70209, 169085, 173489, 177977, 363929, 372897

The prime number generated from \( k \times 2^n-1 \) when \(k=7\) and \(n=24557\) has 7394 decimal digits. In the case of \(k=1\), the primes generated are Mersenne primes and \( n \) itself must be a prime number. However, for larger values of \( k \), \( n \) does not need to be prime. Here is the list provided for \(k=1\) at the previously mentioned site:

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

Related to numbers of the form \(k \times 2^n-1 \) are the Proth numbers that are of the form \(k \times 2^n+1 \) and that I've written about in a blog post on January 18th 2020.

on Saturday, April 24th 2021

Largest Prime

The news of the discovery of a new, largest known prime broke about a week ago but I've only gotten around to writing about it here. It was of course a Mersenne prime discovered via GIMPS, the Great Internet Mersenne Prime Search. 

The number containing \(22,338,618\) digits is \(2^{74,207,281} - 1\) where \(74,207,281\) itself must be prime of course. It is the 49th known Mersenne prime defined as a prime expressible in the form \(2^p - 1\) where \(p\) is prime. The first Mersenne primes are 3, 7, 31, and 127 corresponding to \(p\) values of 2, 3, 5, and 7 respectively. 

Note that p being prime is not sufficient to ensure that 2^p - 1 will be prime. As a counter example take \(p=11\). The resulting number \(2^{11} - 1 = 2047 = 23 \times 89\) is not prime. Here are links to some more interesting information about Mersenne primes:

• Source 1
• Source 2

on 27th of October 2024

Update: \(2^{136,279,841} - 1\) has \(41,024,320\) digits and is prime! Read all about the new largest prime number ever found: Stand-up MathsYouTube video.