Pentominoes

Today I turned 25900 days old and one of the OEIS entries for this number states:

A248102

Number of tilings of a 5 X 2n rectangle using 2n pentominoes of shapes N, Y.

So 25900 is a member of this sequence, specifically for the case where n=8 and so, when there is a 5 x 16 rectangle (with area 80 square units), it can be tiled with 16 pentominoes (each with an area of 5 square units) in 25900 different ways. The pentominoes must be of type N or Y. Of course, I then had to look up what was meant by a pentomino of type N and type Y. Figure 1 shows the twelve types of free pentominoes, lettered according to the shapes that approximate those letters.

Figure 1: the 12 types of free pentominoes (source)

By free pentominoes, it is meant that chiral versions are not considered distinct. For example, the F pentomino can be lifted out of the plane and turned into its mirror image. If chiral versions are considered distinct, then there are 18 different types. See Figure 2.

Figure 2: The 12 pentominoes can form 18 different shapes,
with 6 of them (the chiral pentominoes) being mirrored. (source)

To quote from Wikipedia:

A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20. 

Figure 3 shows some of the possible configurations:

Figure 3

There are many websites where puzzles of this sort can be solved. Figure 4 is a screenshot of one of these sites. Link

Figure 4: link to website

In the screenshot in Figure 4, the 6 x 10 rectangle is to be tiled. There are 2339 ways in which this can be done. For the 5 x 12 case, there are 1010 ways. For the 4 x 15 case, there are 368 ways and for the 3 x 20 case there are just 2 ways. 

There's a lot more that could be said about pentominoes but I'll go on and make some comments about pentacubes which are polycubes made out of five cubes. There are 29 possible pentacubes of which twelve are flat (corresponding to the twelve pentominoes extruded to a depth of 1 unit). Figure 5 shows one of the non-flat pentacubes:

Figure 5: source 

To quote again from Wikipedia:

A standard pentomino puzzle is to tile a rectangular box with the pentominoes, i.e. cover it without overlap and without gaps. Each of the 12 pentominoes has an area of 5 unit squares, so the box must have an area of 60 units. Possible sizes are 6×10, 5×12, 4×15 and 3×20.

Figure 6

The diagrams in Figure 6 do require a little scrutiny but the shapes of the various polycubes do reveal themselves. Obviously, the topics of pentominoes and pentacubes form a rich vein of recreational Mathematics and I'm just grazing the surface in this post. There are other puzzles that involve pentacubes. I'll mention one such puzzle and that is the Bedlam Cube, named after its inventor Bruce Bedlam. To quote from Wikipedia:

The puzzle consists of thirteen polycubic pieces: twelve pentacubes and one tetracube. The objective is to assemble these pieces into a 4 x 4 x 4 cube. There are 19,186 distinct ways of doing so, up to rotations and reflections. The Bedlam cube is one unit per side larger than the 3 x 3 x 3 Soma cube, and is much more difficult to solve. See Figures 7 and 8.

Figure 7: an assembled Bedlam Cube

Figure 8: a disassembled Bedlam Cube 

There are many more puzzles and much more to say about polyominoes and polycubes but I'll leave it at that for the moment. Meanwhile, I've not been idle. My trophy cabinet is shown in Figure 9 with my trophy for attaining Level 4 in Pentominoes.

Figure 9

House Numbers

When turning 25884 days old today, I discovered that 25884 is a house number. This was new to me and not surprising because the previous such number was 23101. I turned 23101 days old over 7.6 years ago. So I needed to discover what house numbers are. They are named not after some mathematician named House but because they can be represented as houses. A diagram is helpful at this point. See Figure 1.

Figure 1

Clearly such numbers are figurate but consist of two conjoined shapes: a cube on top of which sits a square-based pyramid. Here a definition from Numbers Aplenty:

The \(n\)-th house number \(h_n\) is a figurate number made by a cube of side \(n+1\), surmounted by a square pyramidal number with side \(n\), thus:$$h_n = (n+1)^3 + \sum_{k=1}^nk^2$$An alternative way of representing this is as: $$h_n=\frac{8n^3+21n^2+19n+6}{6}$$The generating function for this sequence is:$$\frac{1+5x+2x^2}{(x-1)^4}$$In Figure 2, the SageMath code is shown that makes use of this function to generate the coefficients of the polynomial that are the terms of the sequence (the output is truncated for display purposes):

Figure 2: permalink

Figure 3 shows the SageMath code to generate the coefficients by themselves, removed from the polynomial. The output has been truncated to fit the display. These are the house numbers. The sequence of house numbers forms  OEIS A051662. Below is the list of terms, up to and including 25884:

1, 9, 32, 78, 155, 271, 434, 652, 933, 1285, 1716, 2234, 2847, 3563, 4390, 5336, 6409, 7617, 8968, 10470, 12131, 13959, 15962, 18148, 20525, 23101, 25884, ...

Figure 3: permalink

The next house number is 28882, so it's quite some way off. There's nothing very deep about house numbers but they form an interesting variation on the figurate numbers that I'm familiar with. They are the sum of two different and independent figurate numbers that have been combined to form a composite shape, in this case a house. There's no reason that one couldn't combine other shapes together from these or different components.

For example, adding a square-based triangular pyramid to each of the six faces of the cube would produce a sort of stellated cube. The formula would be:$$h_n = (n+1)^3 + 6 \sum_{k=1}^nk^2$$ADDENDUM: May 7th 2020

Today I turned 25967 days old and this number turns out to be a 24-hedral number with formula:$$(2n + 1)(8n^2 + 14n + 7) \text{ where }n=11$$It can be considered as being made up out of a central cube and six square pyramids. The central cube number is given by OEIS A016755:$$CCub(n) = (2n + 1)^3$$The figurate number represented by the square pyramids is given by OEIS A000447:$$ P^{(4)}(n) = \frac{(1 + n)(1 + 2n)(3 + 2n)}{3}$$Therefore, for our 24-hedral number, we have:$$24H(n) = CCub(n) + 6P^{(4)}(n)$$ $$24H(n)=(2n+1)^3 + \frac{6(1+n)(1+2n)(3+2n)}{3}$$ $$24H(n)= (2n+1)(8n^2 +14n+7)$$Figure 4 shows the example for when \(n=11\):

Figure 4: link

The Möbius Function and Mertens Function

I had come across the Möbius function before but didn't see it as all that important. However, I was reminded of it recently when I encountered a Numberphile video on Mertens conjecture (uploaded 23rd January 2020).

In number theory, we define the Mertens function as:$$M(n) = \sum_{1\le k \le n} \mu(k)$$where \( \mu (k)\) is the Möbius function. The Mertens conjecture is that for all \(n > 1\): $$\left| M(n) \right| < \sqrt { n }$$To quote from Wikipedia:

In mathematics, the Mertens conjecture is the disproven statement that the Mertens function \(M(n)\) is bounded by \( \sqrt {n}\), which implies the Riemann hypothesis. It was conjectured by Thomas Joannes Stieltjes in an 1885 letter to Charles Hermite (reprinted in Stieltjes (1905)) and Franz Mertens (1897), and disproved by Andrew Odlyzko and Herman te Riele (1985). It is a striking example of a mathematical proof contradicting a large amount of computational evidence in favour of a conjecture.

I set about writing a program in SageMath to plot the first million values of the Mertens function. I managed to execute it in SageMathCell but the code was clunky as I had to get the program to determine the values of -1, 0 and 1 based on the factorisation. Later I realised that the Möbius function would replace the need for this. In SageMath, the spelling is moebius and moebius(1) --> 1 etc. So let's define the Möbius function:

For any positive integer n, \(μ(n)\) has values in {−1, 0, 1} depending on the factorisation of \(n\) into prime factors:$$\mu(n) =
  \begin{cases}
    1       & \quad \text{if } n \text{ is a square-free positive integer with an even number of prime factors}\\
   -1  & \quad \text{if } n \text{ is a square-free positive integer with an odd number of prime factors}\\
0  & \quad \text{if } n \text{ has a squared prime factor}
  \end{cases}$$Figure 1 shows the results of plotting the first one million values of the Möbius function. Here is the permalink to the SageMathCell calculation.

Figure 1

The square root of \( \pm \) 1,000,000 is \( \pm \) 1,000 and as can be seen the function is well within those bounds. However, as mentioned earlier, the bounds are eventually exceeded. Sometimes, instead of \(M(n) \), the function \(m(n) \) is used where:$$m(n)=\frac{M(n)}{\sqrt{n}}$$For the Mertens conjecture to hold, the following condition would be necessary: \(-1 <m(n)<1\). However, for enormously large values of \(n\), it has been shown that \(m(n)<-1.837625 \) and \(m(n)>1.826054\) are possible.

Proth Numbers

Today I turned 25857 days old and was surprised to come across a number property in Numbers Aplenty that I hadn't encountered before. Or so I thought. The property referred to Proth Numbers and the previous such number was 25601 that occurred on May 7th 2019. On that occasion, I'd chosen to ignore it for whatever reason.

Proth numbers are named after a French mathematician François Proth (1852–1879). He was a French self-taught mathematician farmer who lived near Verdun, France. He doesn't earn an entry in the MacTutor History of Mathematics archive. However, David Wells mentions him in his book Prime Numbers: The Most Mysterious Figures in Math. Figures 1 and 2 contain the reference:

Figure 1

He continues on the next page:

Figure 2

In the case of 25857, the number can be represented as \( 101 \times 2^8 + 1 \) but it is not prime because it factorises to \( 3^2 \times 13^2 \times 17 \). The previous Proth number 25601 however, is a Proth prime and can be represented as \( 25 \times 2^{10}+1 \). I downloaded the proth.exe program referred to in Wells' book and ran it on my Mac using Wine. The program hasn't been updated since May of 2004 but it still does the job. A result, identifying 25601 as a prime, is shown in Figure 3:

Figure 3

The \( a =19\) refers to the fact that when N is prime, then:$$ a^{\frac{N-1}{2}}+1 \equiv 0 \mod{N}$$So when \(N = 25601\) we have:$$ 19^{\frac{25601-1}{2}}+1 \equiv 0 \mod{25601}$$The Wikipedia page on Proth primes has some interesting references including the following in reference to the primality test:

This test is a Las Vegas algorithm: it never returns a false positive but can return a false negative; in other words, it never reports a composite number as "probably prime" but can report a prime number as "possibly composite".

The Wikipedia link to the Las Vegas algorithm states that:

Las Vegas algorithms were introduced by László Babai in 1979, in the context of the graph isomorphism problem, as a dual to Monte Carlo algorithms. Babai introduced the term "Las Vegas algorithm" alongside an example involving coin flips: the algorithm depends on a series of independent coin flips, and there is a small chance of failure (no result). However, in contrast to Monte Carlo algorithms, the Las Vegas algorithm can guarantee the correctness of any reported result.

The next Proth number after today's 25857 is 26113 and it is also a Proth prime with \(a=7\). This will occur on Wednesday, September 30th 2020. Thus:$$7^{\frac{26113-1}{2}}+1 \equiv 0 \mod{26113}$$

The Original Taxi Cab Number in a New Light

Today I turned 25829 days old and, amongst the number's many different properties, one in particular caught my eye. The property was that it is a member of OEIS A262054: Euler pseudoprimes to base 7: composite integers such that:$$ |7^{(n-1)/2}| \equiv 1 \pmod {n}$$Now there's no sign of 1729, the original taxi cab number, but we'll get there. Firstly however, how did 1729 earn its sobriquet? Here an excerpt from Wikipedia:

The name is derived from a conversation in about 1919 involving mathematicians G. H. Hardy and Srinivasa Ramanujan. As told by Hardy: 

"I remember once going to see him [Ramanujan] when he was lying ill at Putney. I had ridden in taxi-cab No. 1729, and remarked that the number seemed to be rather a dull one, and that I hoped it was not an unfavourable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two [positive] cubes in two different ways."

Figure 1

The two different ways are: \(1^3 + 12^3\) and \(9^3 + 10^3\).

I won't go further into taxicab numbers here as the Wikipedia article explains things well enough. What I want to do is cast a new light on 1729, the number that Hardy originally thought was a rather dull number. The light I'm casting comes from the Euler pseudoprimes. 

I've already discussed pseudoprimes in two earlier posts: Fermat Pseudoprimes and Carmichael Numbers. I did make make passing mention of Euler pseudoprimes in the former post but didn't go into the matter further. Figure 1 shows a screenshot of part of what Wikipedia has to say about Euler pseudoprimes. 

The excerpt in Figure 1 concludes with the observation that:

The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.

It's surprising then that a mathematician of Hardy's calibre should not have recognised 1729 as having quite some claim to fame. In fact, the Online Encyclopaedia of Integer Sequences (OEIS) has 794 entries for the number so it is far from dull. Let's consider some of the other entries for 1729 in the OEIS. 

One entry is not surprising when the factorisation of 1729 is considered and the factors are arranged in descending order: 19 x 13 x 7. Let's add a 1 to give 19 x 13 x 7 x 1. The numbers 19, 13, 7 and 1 form an arithmetic sequence and this shows 1729 to be a so-called sextuple factorial. This can be written as 19!!!!!! or 19!6.

1729 counts the ways that a 2 x 2 matrix can be populated with integers from -7 to +7 in such a way that every matrix is singular (that is has a determinant of zero). It thus forms part of OEIS A209981. 

Figure 2: 35 points in a body-centered cubic lattice, 
forming two cubical layers around a central point

In the realm of figurate numbers, 1729 is a centred cube number. These are numbers of the form:\((n+1)^3+n^3\) and of course 1729 can be written as \(10^3+9^3\). Figure 2 shows the example of the centred cube number 35 and Wikipedia explains:

A centred cube number is a centred figurate number that counts the number of points in a three-dimensional pattern formed by a point surrounded by concentric cubical layers of points, with \(i^2\) points on the square faces of the \(i\)-th layer. Equivalently, it is the number of points in a body-centred cubic pattern within a cube that has \(n + 1\) points along each of its edges. 

The first few centred cube numbers are:

1, 9, 35, 91, 189, 341, 559, 855, 1241, 1729, 2331, 3059, 3925, 4941, 6119, 7471, 9009, ... (sequence A005898 in the OEIS).

1729 is also an heptagonal number, a 12-gonal or dodecagonal number, a 24-gonal or icosotetragonal number but that's probably enough for the moment.

Mathematics in Everyday Life

How many times have I opened a box of tissues by removing the elliptical cover on the top of the box? Every time I do it, I'm aware of its elliptical shape but I never paused to consider the resulting ellipse of cardboard that I held in my hand. It would be discarded as rubbish. Today however, I paused and really looked at what I had in my hand (see Figure 1).

Figure 1

There's even a little semi-circular tab on the right that can be depressed to facilitate the removal of the cover. I'd never noticed that before. Turning the cardboard ellipse over reveals blank cardboard on which I marked in the major and minor axes and measured their lengths, to the nearest millimetre (see Figure 2).

Figure 2

These measurements enable calculation of the eccentricity \(e\) of the ellipse and so in this case, with \(a=28\) and \(b=62.5\) where \(a\) and \(b\) are the lengths of the semi-minor and semi-major axes respectively, we have:$$e=\sqrt {1-\frac{a^2}{b^2}}=\sqrt {1-\frac{28^2}{62.5^2}} \approx 0.894$$This of course is highly elliptical, especially if it's compared with the eccentricities of the planets of the solar system (see Figure 3).

Figure 3

As can be seen in Figure 3, Mercury and Pluto have the most eccentric orbits but much less eccentric than my cardboard ellipse. The other planets have elliptical orbits that would be hard to distinguish from circles if their proportions were displayed on a cardboard cut-out similar to that shown in Figure 2. Coincidentally, there is a centaur with an eccentricity of 0.894 as the table shown in Figure 4 reveals. The academic paper that the table was taken from is quite an interesting but I won't go into here but this is the link, the same as the one shown in Figure 4.

Figure 4

As explained in Figure 4, centaurs are planetesimals with perihelia (closest distance to the Sun) exterior to the orbit of Jupiter and aphelia (farthest distance from the Sun) interior to the orbit of Neptune. The most famous of the centaurs in Chiron, the first to be discovered in 1977 but the somewhat less famous C/2012 H2 (McNaught) does have an orbit that exactly matches that of the cardboard ellipse shown in Figures 1 and 2. Figure 5 provides a little more information about this object.

Figure 5

To calculate the length \(F\) from the centre of the ellipse to the two foci, the following formula can be used involving once again the lengths of the semi-minor and semi-major axes:$$F=\sqrt{b^2-a^2}=\sqrt{62.5^2-28^2} \approx 55.9$$These foci for the cardboard ellipse are shown in Figure 6.

Figure 6

The mathematics in this post is very basic but that was my intention. Though basic, the shape of the cardboard ellipse is nonetheless reflected in the shape of a particular centaur's orbit and it's pretty cool to find a connection between an everyday household item and the solar system in which we are immersed.

The Goldbach Conjecture and Lucky Numbers

I've written before about Lucky Numbers (Generating Lucky Numbers in Python and Lucky Numbers) as well as the Goldbach Conjecture (Goldbach's Conjecture and Zeckendorf's Theorem and Goldbach's Conjecture Revisited) but now it's time to combine the two topics. The reason we can do this is that primes and lucky numbers have similar distributions. The table in Figure 1 attests to this:

Figure 1: source URL

As stated on the site from which the table was taken:

What's most interesting about lucky numbers is the fact that they share a lot of properties with primes. As can be seen from the next table the density of the lucky numbers is close to the density of the primes. This seems also be true for the density of the twin luckies and the twin primes. In addition a lot of conjectures about primes seem also to be true for the luckies. For example one of the most famous ones, the Goldbach conjecture, stating that each even integer is the sum of at most two primes seems also to be true.

Goldbach decompositions are numerous and so, as with the decomposition into primes, we are interested in the minimal decomposition but first let's state the Goldbach conjecture for lucky numbers:

Every even number can be expressed as a sum of two lucky numbers

The smallest even number is 2 and that can expressed as 1 + 1. This is a little different to the primes where 1 is not regarded as a prime. Thus the Goldbach Conjecture for primes requires the even number to be greater than 2. The next even number is 4 and that can be expressed as 1 + 3 and so on. Let's take a number like 25800 and find it's minimal decomposition using SageMath. Figure 2 depicts the results using a screenshot from SageMathCell (permalink).

Figure 2: permalink

An interesting observation made on the website is that "no lucky number can have a digital root of 2, 5 and 8. This fact can sometimes be used to determine quickly that a given number is not lucky." I was able to find an explanation of why this is so thanks to a reference in Gardner's Workout by Martin Gardner. This is shown in Figure 3.

Figure 3

To see this, consider \(\frac{3k+2}{9}\). If \(k=1\) then the remainder is 5, if \(k=2\) then the remainder is 8, if \(k=3\) then the remainder is 2 and so on. The only remainders that can occur are 2, 5 and 8.

1 2 3 4 5 6 7 8 9
1 x 3 x 5 x 7 x 9 : first step of sieving process, all multiples of 2 are removed
1 x 3 x x x 7 x x : second step of sieving process, all multiples of 5 are removed

It is this sieving process, similar to the Sieve of Eratosthenes that causes the lucky numbers to have properties similar to the primes.

There are lots more "extensions" to the original Goldbach conjecture. One such one is the ternary Golbach conjecture described in the following abstract of a 79 page paper presented in 2014:

THE TERNARY GOLDBACH CONJECTURE IS TRUE

H. A. HELFGOTT 

Abstract. The ternary Goldbach conjecture, or three-primes problem, asserts that every odd integer n greater than 5 is the sum of three primes. The present paper proves this conjecture. 

Both the ternary Goldbach conjecture and the binary, or strong, Goldbach conjecture had their origin in an exchange of letters between Euler and Goldbach in 1742. We will follow an approach based on the circle method, the large sieve and exponential sums. Some ideas coming from Hardy, Littlewood and Vinogradov are reinterpreted from a modern perspective. While all work here has to be explicit, the focus is on qualitative gains. 

The improved estimates on exponential sums are proven in the author’s papers on major and minor arcs for Goldbach’s problem. One of the highlights of the present paper is an optimized large sieve for primes. Its ideas get reapplied to the circle method to give an improved estimate for the minor-arc integral.

A certain Zoltan Galantai has also investigated generalisations to the Goldbach conjecture at this site.