Monday 26 February 2018

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

Tuesday 20 February 2018

Fundamental Theorem on Sums of Two Squares

Today I achieved some further insights regarding what conditions allow a number to be expressed as a sum of two squares and then, if these conditions are met, to determine the number of ways in which this can be done. This useful site provided clear answers to these two matters. Firstly, the French mathematician Albert Girard had determined in 1632 (according to Leonard Dickson) that the numbers expressible as a sum of two integral squares were:
  • every square
  • every prime \( 4n+1 \)
  • a product formed of such numbers 
  • the double of one of the foregoing
The fundamental theorem on sums of two squares is:

Let \(n=2^kp_1^{a_1} \dots p_r^{a_r}q_1^{b_1} \dots q_s^{b_s}\) , where the \( p_i  \) are distinct primes with \( p_i \equiv 1 \pmod{4} \) and the \( q_i \) are distinct primes with \( q_j \equiv 3 \pmod{4} \). Then \(n \) is the sum of two squares if and only if all the \( b_j \) are even. In that case, the number of distinct solutions is \( \lceil \frac{\scriptstyle{1}}{\scriptstyle{2}} (a_1+1)(a_2+1) \dots (a_r+1) \rceil \), where \( \lceil x \rceil \) is the ceiling function, the smallest integer greater than or equal to \( x \).

What's of particular interest here is that the number of distinct solutions can be calculated. For example, consider the number \( 5^2 \times 13 \times 17 \times 29 = 160225 \) which can be represented as a sum of two squares because all the prime factors are of the form \( 4k+1 \). The number of distinct solutions can be found by adding 1 to all the indices of the factors, multiplying them together and dividing by 2. This gives \( 3 \times 2 \times 2 \times 2 \) divided by 2 which is 12. So there are twelve distinct ways in which this number can be expressed as a sum of two squares. 

The two square calculator provided at the site mentioned earlier displays eleven of these but oddly enough misses out on a twelfth arrangement, namely \( 300^2+265^2 \):

In determining what is the smallest number expressible as the sum of two different squares in two, three, four ways and so on, the \( 4k+1 \) primes are the key. These primes are 5, 13, 17, 29, 37, 41, ... and so the smallest number to be expressible on the sum of two squares in two different ways is 65 = 5 x 13, viz. \( 8^2+1^2 \text{ and } 7^2 + 4^2 \). Of course, I'm ignoring 25 which can be written as \( 3^2+4^2 \text{ and }0^2+5^2 \) because I'm only considering positive integers here. Similarly, the smallest number expressible as the sum of two squares in three different ways is 325 = 5 x 5 x 13:


Throwing 2's or 4k+3 primes into the factorisation doesn't increase the number of ways in which the number can be written as a sum of two squares. For example, 650 = 2 x 5 x 5 x 13 = 2 x 325 is still only expressible in three different ways:


It follows of course that every 4k+1 prime is expressible as a sum of two squares in one way only. For example, my birth year is \( 1949=10^2+43^2 \). My most recent prime day was \( 25153=57^2+148^2 \) and so it goes.

Friday 16 February 2018

Goldbach's Conjecture Revisited

I touched on Goldbach's Conjecture in a post from November of 2015 but I was reminded of it once again when I celebrated my 25156th day on Earth. Here is my tweet for the day:


For any given number, WolframAlpha will return the prime decomposition with the lowest prime. It doesn't say so explicitly but a few test numbers reveal that this is what's happening e.g. 100 returns 3 and 97. Here is a screenshot of what happens to 50312 which is 25156 x 2:


Let's remember that the Goldbach conjecture states that every even number can be expressed as the sum of two primes. OEIS sequence A001031 shows how many compositions are possible for numbers up to 10,000. For 10,000 there are 231 possible compositions and WolframAlpha as said will quickly return the one involving the smallest primes, namely 59 and 9941. 

A plot of the number of compositions against the even integers themselves, sometimes called Goldbach's comet, is shown below for numbers up to 2000:


While there is clearly a general trend toward larger numbers of compositions as the numbers increase in size, there is little evidence of this at the local level. For example, here is a sample of the number of compositions for odd and even integers between 9975 and 10,000 (even integers have their number of compositions marked in bold type):

9975 559, 9976 165, 9977 183, 9978 338, 9979 175, 9980 217, 9981 330, 9982 215, 9983 174, 9984 357, 9985 225, 9986 165, 9987 331, 9988 187, 9989 213, 9990 454, 9991 164, 9992 163, 9993 335, 9994 180, 9995 219, 9996 435, 9997 192, 9998 167, 9999 366, 10000 231

Of course, what OEIS A208662 is saying is that 25156 is the smallest number in which it's double (50312) has the prime number 181 appearing for the first time as one of the two primes whose sum is equal to 50312. This is not so easy to show unless all the compositions less than 50312 are tested. OEIS A002373 provides a list of the smallest prime number in the composition of all integers up to 20,000 but that falls a little short of 25156. Scanning through the list, it's clear that most of the primes are quite small and the bigger primes make only relatively rare appearances. For example, 89 doesn't make an appearance until 19828. I'll leave off here as I've already spent a lot of time dithering around with this.

ADDENDUM: added on November 24th 2019

It's embarrassingly easy to find the minimal Goldbach composition for a number using only a table of primes. The smaller of the two primes is generally very small and so only needs to be subtracted from the number. If the result of the subtraction is a prime number, then you have your minimal Goldbach decomposition. In the case of 50312, you only need to test up to 181 before you succeed. Here is some SageMath code that does this:

Click here for Permalink

Monday 12 February 2018

Chess960


Currently an unofficial world championship is underway in Oslo pitting Hikaru Nakamura against Magnus Carlsen. However, the two are not playing traditional chess but instead so-called Chess960 described as follows in Wikipedia:
Chess960, also called Fischer Random Chess (originally Fischerandom), is a variant of chess invented and advocated by former world chess champion Bobby Fischer, publicly announced on June 19, 1996, in Buenos Aires, Argentina. 
It employs the same board and pieces as standard chess, but the starting position of the pieces on the players' home ranks is randomised. The random setup renders the prospect of obtaining an advantage through the memorisation of opening lines impractical, compelling players to rely on their talent and creativity. 
Randomising the main pieces had long been known as Shuffle Chess; however, Chess960 introduces restrictions on the randomisation, "preserving the dynamic nature of the game by retaining bishops of opposite colours for each player and the right to castle for both sides".[3] The result is 960 unique possible starting positions. 
White's pieces (not pawns) are placed randomly on the first rank, with two restrictions:
  • The bishops must be placed on opposite-color squares.
  • The king must be placed on a square between the rooks.
  • Black's pieces are placed equal-and-opposite to White's pieces. (For example, if the white king is randomly determined to start on f1, then the black king is placed on f8.) Pawns are placed on the players' second ranks as in standard chess.
It is the number 960 that is of interest in this mathematics blog and this is explained as follow:
Each bishop can take one of four squares; for each position of two bishops, the queen can be placed on six different squares; and then the two knights can assume five and four possible squares, respectively. This leaves three open squares which the king and rooks must occupy, per setup stipulations, without choice. This means there are 4×4×6×5×4 = 1920 possible starting positions if the two knights were different in some way; however, the two knights are indistinguishable during play (if swapped, there would be no difference), so the number of distinguishable possible positions is half of 1920, or 1920÷2 = 960. (Half of the 960 positions are left–right mirror images of the other half; however, the Chess960 castling rules preserve left–right asymmetry in play.) 
There is another variant called Double Fischer Random Chess which is the same as Chess960, except the White and Black starting positions do not mirror each other. In this form of the game, the number of possible starting positions is 960 x 960 = 921600. In Shuffle Chess, the parent variant of Chess960, there are no restrictions on the back-rank shuffles, with castling possible only when king and rook are on their traditional starting squares. In the case, the number of permutations is 8! but division by 8 is necessary because the pairs of Knights, Bishops and Rooks are indistinguishable. This means 7! or 5040 arrangements are possible.

Sunday 11 February 2018

The Mathematics of Chess Pairings

There was a recent article is ChessBase regarding a problem that had arisen last year involving the world's highest ranked woman player, Hou Hifan. The article began:
The Gibraltar Masters wrapped up Thursday, with Levon Aronian in first place. This year Round Ten passed without incident, in contrast to 2017 when, on February 2nd, the story of the day was a rare scandal involving women's World Champion Hou Yifan deliberately losing a game in protest of the high number of women she was paired against. She was further confounded when a similarly unlikely string of pairings happened in October at the Isle of Man Open. Johannes Meijer looks at the odds in detail. Hou did not return to Gibralter in 2018, but instead competed in the Tata Steel Chess Masters.
Imagine, you are at a tournament with 255 players of which 43 are female. You are to play ten rounds. How many female opponents would you expect to face? Three? Five? I am pretty sure you wouldn't say seven. Yet, this was exactly the number of female players Hou Yifan faced at the Gibraltar Open 2017 when, a year ago today, she threw her last game in protest of these seemingly odd pairings.
The article goes on to ask the question: How probable is such a pairing? Could it have happened by chance at all? Well, the approach to solving this problem involves the hypergeometric distribution, a discrete probability distribution commonly covered in high school probability and statistics courses. Wikipedia describes it thus:


Thus to find how likely, or unlikely, Hou's pairings were we only have to replace "green marbles" with women and "red marbles" with men. So k=7, K=43, N=255, n-10, n-k=3 and N-K=212. Substituting into the formula we get:$$P(X=7)=\frac{^KC_k \text{ . } ^{N-K}C_{n-k}}{^NC_n}=\frac{^{43}C_7 \text{ . } ^{212}C_{3}}{^{255}C_{10}}\approx 0.000188 $$Thus it seen that the likelihood is very small that this could happen and yet the pairings were allegedly arranged using a computer draw. The quoted article carries out similar calculations but follow a somewhat different approach.

To be strictly accurate, since possible pairings with Hou Hifan are under consideration, we should make K=42 and thus N=254. This gives a slightly lower probability of 0.000164 and so even more unlikely. It means that out of 10,000 random pairings of a woman with ten competitors, the result of being paired with another woman in seven out of the ten rounds would be expected to occur less than twice. On the other hand, the probability of not being paired with any women is nearly 16% and is given by:$$P(X=0)=\frac{^KC_k \text{ . } ^{N-K}C_{n-k}}{^NC_n}=\frac{^{42}C_0 \text{ . } ^{212}C_{10}}{^{254}C_{10}}\approx 0.158251 $$

Saturday 3 February 2018

The Permutations of {1, 2, 3, 4, 5}

Today I am 25143 days old, a permutation of the digits 1, 2, 3, 4 and 5. There are 5! or 120 possible ways to arrange these digits and they are as follows:

{1, 2, 3, 4, 5} | {1, 2, 3, 5, 4} | {1, 2, 4, 3, 5} | {1, 2, 4, 5, 3} | {1, 2, 5, 3, 4} | {1, 2, 5, 4, 3} | {1, 3, 2, 4, 5} | {1, 3, 2, 5, 4} | {1, 3, 4, 2, 5} | {1, 3, 4, 5, 2} | {1, 3, 5, 2, 4} | {1, 3, 5, 4, 2} | {1, 4, 2, 3, 5} | {1, 4, 2, 5, 3} | {1, 4, 3, 2, 5} | {1, 4, 3, 5, 2} | {1, 4, 5, 2, 3} | {1, 4, 5, 3, 2} | {1, 5, 2, 3, 4} | {1, 5, 2, 4, 3} | {1, 5, 3, 2, 4} | {1, 5, 3, 4, 2} | {1, 5, 4, 2, 3} | {1, 5, 4, 3, 2} | {2, 1, 3, 4, 5} | {2, 1, 3, 5, 4} | {2, 1, 4, 3, 5} | {2, 1, 4, 5, 3} | {2, 1, 5, 3, 4} | {2, 1, 5, 4, 3} | {2, 3, 1, 4, 5} | {2, 3, 1, 5, 4} | {2, 3, 4, 1, 5} | {2, 3, 4, 5, 1} | {2, 3, 5, 1, 4} | {2, 3, 5, 4, 1} | {2, 4, 1, 3, 5} | {2, 4, 1, 5, 3} | {2, 4, 3, 1, 5} | {2, 4, 3, 5, 1} | {2, 4, 5, 1, 3} | {2, 4, 5, 3, 1} | {2, 5, 1, 3, 4}

TODAY | {2, 5, 1, 4, 3} | 

{2, 5, 3, 1, 4} | {2, 5, 3, 4, 1} | {2, 5, 4, 1, 3} | {2, 5, 4, 3, 1} | {3, 1, 2, 4, 5} | {3, 1, 2, 5, 4} | {3, 1, 4, 2, 5} | {3, 1, 4, 5, 2} | {3, 1, 5, 2, 4} | {3, 1, 5, 4, 2} | {3, 2, 1, 4, 5} | {3, 2, 1, 5, 4} | {3, 2, 4, 1, 5} | {3, 2, 4, 5, 1} | {3, 2, 5, 1, 4} | {3, 2, 5, 4, 1} | {3, 4, 1, 2, 5} | {3, 4, 1, 5, 2} | {3, 4, 2, 1, 5} | {3, 4, 2, 5, 1} | {3, 4, 5, 1, 2} | {3, 4, 5, 2, 1} | {3, 5, 1, 2, 4} | {3, 5, 1, 4, 2} | {3, 5, 2, 1, 4} | {3, 5, 2, 4, 1} | {3, 5, 4, 1, 2}

JUST BEFORE | {3, 5, 4, 2, 1} | 97th BIRTHDAY

{4, 1, 2, 3, 5} | {4, 1, 2, 5, 3} | {4, 1, 3, 2, 5} | {4, 1, 3, 5, 2} | {4, 1, 5, 2, 3} | {4, 1, 5, 3, 2} | {4, 2, 1, 3, 5} | {4, 2, 1, 5, 3} | {4, 2, 3, 1, 5} | {4, 2, 3, 5, 1} | {4, 2, 5, 1, 3} | {4, 2, 5, 3, 1} | {4, 3, 1, 2, 5} | {4, 3, 1, 5, 2} | {4, 3, 2, 1, 5} | {4, 3, 2, 5, 1} | {4, 3, 5, 1, 2} | {4, 3, 5, 2, 1} | {4, 5, 1, 2, 3} | {4, 5, 1, 3, 2} | {4, 5, 2, 1, 3} | {4, 5, 2, 3, 1} | {4, 5, 3, 1, 2} | {4, 5, 3, 2, 1} | {5, 1, 2, 3, 4} | {5, 1, 2, 4, 3} | {5, 1, 3, 2, 4} | {5, 1, 3, 4, 2} | {5, 1, 4, 2, 3} | {5, 1, 4, 3, 2} | {5, 2, 1, 3, 4} | {5, 2, 1, 4, 3} | {5, 2, 3, 1, 4} | {5, 2, 3, 4, 1} | {5, 2, 4, 1, 3} | {5, 2, 4, 3, 1} | {5, 3, 1, 2, 4} | {5, 3, 1, 4, 2} | {5, 3, 2, 1, 4} | {5, 3, 2, 4, 1} | {5, 3, 4, 1, 2} | {5, 3, 4, 2, 1} | {5, 4, 1, 2, 3} | {5, 4, 1, 3, 2} | {5, 4, 2, 1, 3} | {5, 4, 2, 3, 1} | {5, 4, 3, 1, 2} | {5, 4, 3, 2, 1}

Humans will only experience up to 35421 because 35421/365.25 = 96.98 or about 8 days short of one's 96th birthday. The next number 41235 is only reached a little short of one's 113th birthday. There's nothing deeply mathematical about any of this and of course it's specific to the number system being used. For example, in an octal base 25143 becomes 61067\(_8 \). Primeness of course is different and transcends number systems. 61067\(_8 \) and 25143\(_{10} \) are both prime!

Friday 2 February 2018

The Mathematics of Music

The musical notes between one octave on the next are set up so that the ratio between the frequency of one note and the frequency of the next higher note is the same. Let's call this ratio \(r \) and so we have, starting with the notes \(G_1, Ab, A \):$$ \frac{f_{Ab}}{f_{G_1}} = r \text{ and } \frac{f_A}{f_{Ab}}=r \text{  and so   } f_A=r^{\scriptscriptstyle{2}} \times f_{G_1} \text{ etc.} $$In the end, we'll have the following crucial relationship between one octave and the next:$$ f_{G_2}=r^{\scriptscriptstyle{12}} \times f_{G_1} \text{ but because }f_{G_2}=2 \times f_{G_1} \text{ we have } r^{\scriptscriptstyle{12}}=2 \text{  or } r=\sqrt[12]{2}$$The perfect fifth, which according to Pythagoras should be exactly halfway between the two octaves (or seven semitones) giving a frequency of: $$ \frac{\scriptstyle{3}}{\scriptstyle{2}} \times f_{G_1} \text{ compared to the actual } 2^{\scriptscriptstyle{7/12}} \times f_{G_1} \approx 1.498307077 \times f_{G_1}$$Thus the two are almost identical but of course Pythagoras applied his 1.5 method to determine all the other notes but this is not the method that the equal temperament scale uses.