Gaussian Primes

Figure 1

Above is an excerpt from David Well's "Prime Numbers" of which I have an electronic copy as well as a physical copy (in Jakarta). It concerns, as can be seen, Gaussian primes; the pattern described above is shown below:

Figure 2

This pattern would emerge as the primes are plotted on the Argand diagram. The OEIS's associated with Gaussian primes are described below:

Figure 3

\(1949\), the year that I was born, is not a Gaussian prime since it is a \(4n+1\) prime and can be expressed as \(10^2+43^2 =(10+43i)(10-43i)\). The next prime \(1951\) is a \(4n+3\) and hence a Gaussian prime.

Mater Ticket Numbers

Today I received my ticket numbers in the soon-to-be-drawn Mater Prize Home and naturally I scrutinised the fifteen numbers (8539837 to 8539851) that I had been assigned. It turns out that there is one prime number in that range: 8539847. It's too large to show up in the Online Encyclopaedia of Integer Sequences (OEIS) but I discovered the following interesting features of the number:

• the first four digits 8539 form a prime number
• the digit sequence 39847 forms a prime number
• the digit sequence 539 factorises to 7^2×11
• the digit sequence 847 factorises to 7×11^2
• no digit is repeated except for 8 which occurs twice, suggestive of 88

Now 88 is an interesting number. Here is an extract from the Wikipedia entry:

Number 88 symbolises fortune and good luck in Chinese culture, since the word 8 sounds similar to the word Fā (发, which implies 发财, or wealth, in Mandarin or Cantonese). The number 8 is considered to be the luckiest number in Chinese culture, and prices in Chinese supermarkets often contain many 8s. The shape of the Chinese character for 8 (八) implies that a person will have a great, wide future as the character starts narrow and gets wider toward the bottom. The Chinese government has been auctioning auto license plates containing many 8s for tens of thousands of dollars. The 2008 Beijing Olympics opened on 8/8/08 at 8 p.m. In addition, 88 is also used to mean "bye bye (拜拜)" in Chinese-language chats, text messages, SMSs and IMs. 88 can be seen as shorthand for 8181, which when pronounced in standard Mandarin is identical to "bye bye".

Given that the prize draw is on June 30th, it can be assumed that my tickets (purchased yesterday) are amongst the final ones to be issued, so that each ticket has about a 8.5 million to 1 chance of winning. This is approximately the same chance of choosing the six winning numbers on Saturday night's Lotto.

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

Bell Numbers

My tweet for today's numbers was:

24556: 2^2×7×877 with 877 member of OEIS A000110: Bell or exponential numbers, number of ways to partition a set of n labeled elements (n=7)

I had to check on exactly what a Bell number was of course and the Wikipedia entry states:

In combinatorial mathematics, the Bell numbers count the number of partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan, but they are named after Eric Temple Bell, who wrote about them in the 1930s. 

Starting with \(B_0\) = \(B_1\) = 1, the first few Bell numbers are: 

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, ... (sequence A000110 in OEIS). 

The nth of these numbers \(B_n\) counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it. Outside of mathematics, the same number also counts the number of different rhyme schemes for n-line poems. 

As well as appearing in counting problems, these numbers have a different interpretation, as moments of probability distributions. In particular, \(B_n\) is the \(n\)-th moment of a Poisson distribution with mean 1.

The sequence of Bell numbers can be constructed as shown below and the format is analogous to Pascal's Triangle:

 1

 1     2

  2     3     5

   5     7    10    15

   15    20    27    37    52

    52    67    87   114   151   203

    203   255   322   409   523   674   877 

ADDENDUM: reading over this again on 6th February 2019, I was a little confused so I've added the following information (taken from this source) to clarify any possible confusion:

Bell’s Numbers: What they Are and What they Mean

The first Bell numbers are:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.

The \(n\)-th Bell number, \(B_n\), is the number of nonempty subsets a set of size \(n\) can be partitioned into. \(B_0\) is defined as one (i.e. the first number in the above list); There is just one possible partition of the set containing one member, so \(B_1\) = 1.

There are two partitions possible for a set with two elements, so \(B_2\) is just two.

A set with three elements can be partitioned five ways. Taking the set {a, b, c}, the five possible partitions are:

{(a) (b) (c)}, {(a, b), (c)}, {(a, c) (b)}, {(b, c), a}, {(a, b, c)}

There isn’t any simple formula that can give us \(B_n\), but we can find Bell’s numbers in the Bell Triangle, in the next section, or use the following recursive equation to define them:

Bell’s Numbers and the Bell Triangle as a Way to Derive them

The Bell triangle is an easy-to-fill in right triangle which gives us, in the left hand column, all of the Bell numbers.

1. Creating the Triangle

You make the triangle this way:

• On row one, write the number 1
• Begin all other rows with the last number of the previous row. The last number in row 1 was 1, so row 2 also begins with 1.
• All other numbers are found by adding the last number to the one above it. To find out what to write in the second place in row 2, we look at the place before it, place 1. This is just 1, and the digit 1 is above it, so 1 + 1 = 2

The first part of the Bell triangle will therefore be

1

1 2

Following those same rules, we begin the third row with the last number in the previous row, or 2. Then we add that 2 to the number above it to find the next number is 3. Three plus the two above it makes five, so the row finishes with a five.

1

1 2

2 3 5

Row four starts with the last of row three, i.e., 5. Then 5 + 2 = 7, so the next place is 7, and 7 + 3 = 10, so the next digit is ten. Finishing this row and the next in the same manner, we get

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

For any row \(k\), the number that starts the row is \(B_{k-1}\). So the first digit of row 1 is \(B_{1 -1} = B_0\), the first digit of row 4 is \(B_3\), and the first digit of row 55 will be \(B_{54} \).

2. Reading the Triangle

The Bell numbers are given by the far left column, bolded here:

1

1 2

2 3 5

5 7 10 15

15 20 27 37 52

Note that the triangle is sometimes mirrored, so Bell’s numbers appear in the right column, and not the left; Make sure you know the construction of the triangle before attempting to read it.

Remembering Reverse and Add, Palindromes and Trajectories

In an earlier post I commented on the reverse and add operation on numbers that usually leads to a palindrome e.g. 13 --> 31+13 --> 44, 26 --> 62+26 --> 88, 102 --> 201+102 --> 303 etc. However, some numbers (as far as can be determined) do not lead to palindromes under this operation. The first such number is 196. Here is a list of some such numbers taken from the OEIS A063048 entry:

196, 879, 1997, 7059, 10553, 10563, 10577, 10583, 10585, 10638, 10663, 10668, 10697, 10715, 10728, 10735, 10746, 10748, 10783, 10785, 10787, 10788, 10877, 10883, 10963, 10965, 10969, 10977, 10983, 10985, 12797, 12898, 13097, 13197, 13694

I've highlighted 10563 because my number for the day of this entry (24522) is connected to this number because it lies on its trajectory under the reverse and add operation. The list of such numbers defines OEIS A063064 (integers n > 10563 such that the 'Reverse and Add!' trajectory of n joins the trajectory of 10563) and begins thus:

11553, 12543, 13533, 14097, 14523, 15087, 15513, 16077, 16503, 17067, 18057, 18597, 19047, 19587, 20562, 21552, 22542, 24096, 24522, 25086, 25512, 26076, 26502, 27066, 28056, 28596, 29046, 29586, 30561, 31551, 32541, 33531, 34095 

Hence the title of this post. I was reminded about the reverse and add operation and how it mostly results in palindromes except for certain special "seed" numbers (such as 10563) that create seemingly endless "trajectories". It turns out that 24522 lies on the trajectory of 10563.

Below is an excerpt from the WolframMathWorld about what it terms the 196-Algorithm:

Take any positive integer of two digits or more, reverse the digits, and add to the original number. This is the operation of the reverse-then-add sequence. Now repeat the procedure with the sum so obtained until a palindromic number is obtained. This procedure quickly produces palindromic numbers for most integers. For example, starting with the number 5280 produces the sequence 5280, 6105, 11121, 23232. The end results of applying the algorithm to 1, 2, 3,  4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ... are 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 11, 33, 44, 55, 66, 77, 88, 99, 121, ... (OEIS A033865). The value for 89 is especially large, being 8813200023188. The first few numbers not known to produce palindromes, sometimes known as Lychrel numbers (Van Landingham), are 196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, ... (OEIS A023108). 

The Riemann Prime Counting Function

I've been looking back over some of the entries in my Evernote notebook titled "Your Days Are Numbered" that used to be automatically posted to a blog that wanted to charge for the privilege of accessing my posts. However, the entries in the notebook remain and one that caught my attention related to the prime number 24121. OEIS A226473 states:

a(n) is the first prime index where the gap between R(n), Riemann's prime counting function, and Pi(n), the exact prime counting function, is greater than n.

The first terms in the sequence are:

109, 556, 1327, 3296, 5380, 10343, 11767, 19202, 19361, 19371, 24121, 42863 

The example given for 109 is that RiemannR(109) = 27.4664... and PrimePi(109) = 29 give the first gap greater than 1, hence a(1) = 109. 

24121 is the 11th member of the sequence. Pi(24121) = 2686 and RiemannR(24121) = 2674.9424 ... and 11 subtracted from 2686 is 2675. Thus the gap between PrimePi and RiemannR is more than 11 and so a(11) = 24121.

There is a discussion of the Riemann prime counting function on WolframAlpha.

Partitions

As I've been reading "The Man Who Knew Infinity", the topic of partitions came up and I felt impelled to delve a little further into the topic. Wikipedia defines a partition as follows:

In number theory and combinatorics, a partition of a positive integer \(n\), also called an integer partition, is a way of writing \(n\) as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, 4 can be partitioned in five distinct ways: 

4 

3 + 1 

2 + 2 

2 + 1 + 1 

1 + 1 + 1 + 1 

The order-dependent composition 1 + 3 is the same partition as 3 + 1, while the two distinct compositions 1 + 2 + 1 and 1 + 1 + 2 represent the same partition 2 + 1 + 1. 

A summand in a partition is also called a part. The number of partitions of \(n\) is given by the partition function \(p(n) \). So \(p(4)\) = 5. The notation \( \lambda \vdash n \) means that \( \lambda \) is a partition of \( n \). 

Partitions can be graphically visualised with Young diagrams or Ferrers diagrams.

Wolfram Alpha can be used to generate the number of partitions for a given number. An example of the number 5 is shown below, with visualisation using Ferrers diagrams:

 

The OEIS sequence for the number of partitions of the various numbers is A000041 and begins as follows:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754, 147273, 173525

In terms of my numbered days, the last partition number was 21637 and the next will be 26015. This is only the briefest of introductions to the topic and I've not even mentioned the partition-generating function. I'll add it here just for completeness:$$\sum_{n=0}^{\infty} p(n) \, x^n=\prod_{k=1}^{\infty} \left ( \frac{1}{1-x^k} \right )$$

on Thursday April 8th 2021

Golden Semiprimes

Today I am 24534 days old and when checking this number on OEIS I came across the following:

Not having heard of the term before, I investigated what defined a golden semiprime. Below is the OEIS reference:

In today's case of 24534, the sum of the digits is 18 and the factorisation is 2×3^2×29×47, so n/(sum of digits of n) is 29 x 47. Now the absolute value of  29 x ø - 47 is approximately 0.077 and thus the criterion for a golden semiprime is satisfied. As can be seen from the list in OEIS A108542, such semiprimes are relatively sparse.

The significance of the concept is that it identifies that the fact that the two factors making up the semiprime are very nearly in the golden ratio. Of course the factors cannot be in the exact ratio because ø is not rational. Again, I've learned something quite interesting by keeping track of my daily numbers.