Thursday 27 May 2021

The p-adics

In a post on January 17th 2019 title The Golden Key, I wrote:

I came across the Golden Key when perusing Kumar Asok Mallik's book The Story of Numbers during his introduction to prime numbers on page 23. This is quite an interesting book that I've added to my Calibre library ... If I can read an entry a day from this book, I'll soon be a wiser man mathematically.

Well it's no surprise that I didn't read an entry a day and in fact I only stumbled upon the post and its reference to Mallik's book when searching for posts related to \(p\)-adic numbers (which he discusses in his book). There is a good article on the \(p\)-adics in Quanta Magazine titled An Infinite Universe of Number Systems. Figure 1 shows a visualisation of 3-adic numbers:


Figure 1

The diagram makes sense when the following diagrams are considered in Figures 2, 3 and 4. The tube-like structures arise when\(\mod{3^n}\) with \(n=1, 2, 3, ... \) is applied progressively to the natural numbers. The natural numbers become grouped in an entirely new way.

Figure 2

Figure 3



Figure 4

Looking at Figure 4, it's clear in this system that 37 is closer to 10 than it is to 36. As the quanta article explains it:
The size of a \(p\)-adic number is determined by the prevalence of \(p\) in its prime factorisation. Numbers with more \(p\)s are smaller. For example, in the 3-adics, \(486_{10}=200000_3\) is “small” because it has many 3s in its prime factorisation (486 = 2 x 3 x 3 x 3 x 3 x 3). Another way to think about size is to think about which numbers are close to 0. In the \(p\)-adics, integers are closer together when they share a room at higher levels of the tower. The numbers 0 and 486 share a room up to the fifth level, whereas 0 and 6 share a room on only the first level — indicating that 0 is closer to 486 than to 6 and thus 486 is smaller than 6.
Mallik uses the 7-adic number system for illustration purposes. Here he talks about negative numbers in such a system:
A surprising fact is that for \(p\)-adic integers we do not need any negative sign to indicate negative integers. We determine the negative of a positive integer by determining what needs to be added to this positive integer to yield zero, i.e., by subtracting this number from 0. For example 7-adic expansion of −1 can be written as an integer . . . 6 6 6 6 with infinitely many 6’s on the left. We can verify this result by adding 1 to this 7-adic integer: 
· · · 6 6 6 6 + · · · 0 0 0 1 = · · · 0 0 0 0
Thus we can write that \(-1 = 6  +6 \times 7 + 6 \times 7^2 + 6 \times 7^3 + ... \) which seems odd but if 1 is added to both sides we see that it is in fact true. He goes on to say that:
Now we show that some \(p\)-adic integers also represent rational fractions like, say, 1/2. The 7-adic integer · · · 3 3 3 4 with infinitely many 3’s represents 1/2, as can easily verified by multiplying this number by 2 or by adding this number to itself:

 · · · 3 3 3 4  x  2 = · · · 0 0 0 1  

Mallik goes on to mention that \( \sqrt{2} = · · · \text{ 6 2 1 3 } \) because:

· · · 6 2 1 3  x  · · · 6 2 1 3 = · · · 0 0 0 2

Figure 5 shows how 5-adic numbers can be equal to \( \sqrt{-1} \):


Figure 5: source

It's easy to get confused by the above and perhaps this paper is a better introduction to the mechanics of the topic as it details how to add, subtract, multiply and divide p-adic numbers. Furthermore, it points out the difference between the p-adic representation of a number and the p-ary. See Figure 6.


Figure 6: source

The p-adic numbers pop up everywhere in higher Mathematics. For example, consider this article is Quanta Magazine titled Mathematicians Find Long-Sought Building Blocks for Special Polynomials. Figure 7 features a photo of "Benedict Gross (who) was the first to use p-adic numbers to look for the numerical building blocks that Hilbert’s 12th problem asks for. The approach proved successful, decades later."


Figure 7

SageMath can be adapted to help us in changing decimal integers and fractions into p-adic form. Figure 9 shows the conversion of 26353 into its 7-adic form:


Figure 9: permalink

To change a decimal fraction into a so-called "basimal" is not difficult. Using 1/2 and base 7 as an example, here is the SageMath code in blue with output in red:

ring=RealField(30)
ring(1/2).str(base=7)

'0.333333333333'

The 30 just indicates the degree of precision. We see that the 7-ary form of 1/2 is \(0.\overline{3} \). However, this now needs to changed in 7-adic form and to this we need to reverse the order of the digits and place everything to the left of the decimal point. Additionally, 1 must be added to the right-most digit when in the p-adic form:$$0.333333 \dots \rightarrow \dots 333333.0 \rightarrow \dots 333334.0 \rightarrow \overline{3}4.0$$If we multiply this number by 2, the result is 1 and so the representation is correct.

If there is a decimal part in addition to the integer then both parts can be processed together:

n=12.5
n.str(base=7)

'15.333333333333333333'

Changing from 7-ary form to 7-adic form we get: \( \overline{3}4.51 \).

Monday 17 May 2021

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$$

Prime Semi-Magic Squares

 I've posted about magic squares (and cubes) before, specifically:

Yesterday, I turned 26339 days old and one of the properties of this prime number is that it's a member of OEIS A270865:


 A270865

Smallest primes of 4 X 4 semi-magic squares formed from consecutive primes. 
 

A semi-magic square has all its rows and columns adding to a constant number, but not its diagonals. Up to 26339, the OEIS sequence runs:
5, 19, 29, 31, 37, 47, 53, 79, 397, 409, 599, 787, 1229, 1381, 1439, 1993, 2087, 2767, 4003, 4159, 4931, 5791, 5981, 8117, 9293, 9349, 9833, 10939, 10979, 11213, 12553, 12907, 14557, 16361, 18047, 21089, 21557, 21577, 25903, 26339

In the OEIS comments for the sequence, examples are shown for 5 and 19:$$\begin{array}{|c|c|c|c|}

\hline 5 & 7 & 53 & 59 \\

\hline 29 & 61 & 23 & 11\\

\hline 43 & 37 & 31 & 13\\

\hline 47 & 19 & 17 & 41 \\

\hline

\end{array}$$ $$\begin{array}{|c|c|c|c|}

\hline 19 & 23 & 79 & 83 \\

\hline 53 & 67 & 37 & 47\\

\hline 61 & 41 & 59 & 43 \\

\hline 71 & 73 & 29 & 31 \\

\hline


\end{array}$$In the magic square beginning with 5, the 16 primes (5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61) total 496 and every row and column totals 496 ÷ 4 = 124 which is the magic constant of the square. The sum total of the primes must always be a multiple of 4. We know the next set of primes starts with 19 so what happens if we use a set of primes starting with 7, 11, 13 and 17:

  • 7 gives a total of 558 which is not divisible by 4
  • 11 gives a total of 662 which is not divisible by 4
  • 13 gives a total of 684 which is divisible by 4 to give 171
  • 17 gives a total of 750 which is not divisible by 4
From this we can see that divisibility of the prime sum by 4 is a necessary but not sufficient condition for ensuring that a semi-magic square can be created. 13 serves as a reminder of this. A little thought reveals that for an \(n \times n \) magic square, not only must the sum of the terms be divisible by \(n\), the quotient must be even when \(n\) is even and odd when \(n\) is odd. As can be seen, if we start with 13 as the first consecutive prime, the quotient is odd. The reason is that in the case of a 4 x 4 magic square, each column and row consists of four odd primes that when added together must produce an even total.

In the case of 26339, the primes are:

26339, 26347, 26357, 26371, 26387, 26393, 26399, 26407, 
26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489

These primes total 422584 and thus the magic constant is 105646. The problem is how to arrange these primes into a semi-magic square. As can be seen, the pattern of the placement of primes is different between the semi-magic square beginning with 5 and the one beginning with 19. It seems as if each arrangement of numbers might be unique. I tried using the same pattern as found in Durer's famous 4 x 4 magic square but no luck. There are a staggering 20,922,789,888,000 or over twenty trillion ways to form a 4 x 4 grid of 16 numbers  and even SageMathCell cannot search through all these possibilities. What I'm looking for is a method to populate a 4 x 4 semi-magic square with 16 non-consecutive elements.

The number of groups of primes making up the 4 x 4 semi-magic squares are relatively rare. 26339 marks the first member of the 40th such group. Not surprisingly, the number of groups of primes making up 4 x 4 fully magic squares are ever rarer. The following sequence begins 31, 37, 1229, 4931, 12553, 3259909, 3324329, 9291521, ...


 A260673

Smallest primes of 4 X 4 magic squares formed from consecutive primes.   


Here is the magic square of consecutive primes beginning with 37. It has a magic constant of 258:$$\begin{array}{|c|c|c|c|}\hline 37 & 83 & 97 & 41 \\
\hline 53 & 61 & 71 & 73\\

\hline 89 & 67 & 59 & 43\\

\hline 79 & 47 & 31 & 101 \\

\hline

\end{array}$$This of course doesn't solve my problem of how to arrange the primes in my 4 x 4 semi-magic square with its magic constant of 105646. One thing to consider would be the gaps between the primes. These average of these gaps is 10 and the actual gaps are:

26339 to 26347 is a gap of 08 with total of 008
26347 to 26357 is a gap of 10 with total of 018
26357 to 26371 is a gap of 14 with total of 032
26371 to 26387 is a gap of 16 with total of 048
26387 to 26393 is a gap of 06 with total of 054
26393 to 26399 is a gap of 06 with total of 060
26399 to 26407 is a gap of 08 with total of 068
26407 to 26417 is a gap of 10 with total of 078
26417 to 26423 is a gap of 06 with total of 084
26423 to 26431 is a gap of 08 with total of 092
26431 to 26437 is a gap of 06 with total of 098
26437 to 26449 is a gap of 12 with total of 110
26449 to 26459 is a gap of 10 with total of 120
26459 to 26479 is a gap of 20 with total of 140
26479 to 26489 is a gap of 10 with total of 150

The reason I've listed these gaps between the primes is that a lot of importance seems placed on numbers been in arithmetic progression. At this location on Quora, there is a method shown for filling the traditional 4 x 4 magic square with the numbers from 1 to 16. See Figure 1.

Figure 1: source

I tried this using my prime numbers with 26339 replacing 1, 26347 replacing 2 etc. but it didn't work. So my search continues but along the way I've discovered new types of magic squares. For example, bimagic means a magic square remaining magic after each of its numbers have been squared. The smallest possible 4×4 semi-bimagic square of prime numbers begins with 29 and is shown in Figure 2:
Figure 2: source

For this magic square, the magic constant is 1190 and when the terms are squared, the magic constant becomes 549100. Lots of interesting information on magic squares to be found at the source site listed in Figure 2.

The knight's tour often comes up in the construction of magic squares as can be seen in this initial populating of the squares in Figure 3. A knight's tour is only possible on a board with an even number of squares. However, it is apparently not possible on a 4 x 4 board. In fact, the 5 x 6 and 3 x 10 boards are the smallest rectangular boards that have knight's tours. Source.

Figure 3: source

From the same source as listed in Figure 3, the method shown in Figure 4 is suggested as a way to arrange 16 elements into a 4 x 4 magic square:

Figure 4: source

I'm wondering if this strategy might be successful if used with the gaps that I've listed between the primes. I don't have four of every \(a,b,x,y\) but my magic square only needs to be semi-magic. In Figure 2, the knight moves can be seen in the path between \(a\) and \(a+x\), \(b\) and \(b+x\) etc. So far though no luck. I'll keep trying and add to this post when I succeed.

It can be noted that 26339, the first prime in the set of 16 primes that I'm trying to arrange into a semi-magic square, is a Luhn prime of the first order because 26339 + 93362 = 119701 which is a prime number. This is the property that defines a Luhn prime, namely that the prime number itself when added to its reverse, produces a new prime. I posted about Luhn Primes in a post on my birthday, April 3rd 2021. However, this property of 26339 doesn't seem to help in solving my problem.

One approach is to subtract 26339 from every term so that the sequence starts with zero. This gives: 0, 8, 18, 32, 48, 54, 60, 68, 78, 84, 92, 98, 110, 120, 140, 150 and these terms have a median of 73. If we subtract 73 from each we get:

-73, -65, -55, -41, -25, -19, -13, -5, 5, 11, 19, 25, 37, 47, 67, 77

The magic constant for this set of numbers is -2. If I subtract 72, the magic constant is 2, so a magic constant of zero isn't possible. Perhaps it will be easier to work with these smaller numbers. If I come up with a semi-magic square for these numbers, then I simply need to add 26339 + 73 = 21412 to the numbers above.

Thursday 13 May 2021

The Search for Patterns

Today I turned 26338 days old and a search of the OEIS turned up only two entries, neither of them meaningful to me. Further searching didn't turn up anything more. The factorisation of the number is \(2 \times 13 \times 1013\) and of course it struck me that \(2 \times 13 = 26\) which represents the first two digits of the number. It was some time later that I considered the last three digits and realised that \(338 = 2 \times 13^2\).

Suddenly there was a pattern and where there's a pattern, there's a sequence. The pattern is to concatenate \(2n\) and \(2n^2\). After that, it didn't take too long to create the sequence. See Figure 1.


Figure 1: permalink

Thus the sequence of terms up to 26338 is: 

22, 48, 618, 832, 1050, 1272, 1498, 16128, 18162, 20200, 22242, 24288, 26338

There is a similar sequence in the OEIS viz. A053061


 A053061

a(\(n\)) is the decimal concatenation of \(n\) and \(n^2\).                        


The terms in this sequence run:
1, 24, 39, 416, 525, 636, 749, 864, 981, 10100, 11121, 12144, 13169, 14196, 15225, 16256, 17289, 18324, 19361, 20400, 21441, 22484, 23529, 24576, 25625, 26676, 27729, 28784, 29841, 30900, 31961, 321024, 331089, 341156, 351225, 361296, 371369, 381444, 391521 

So my new sequence would appear as:


 A******

a(\(n\)) is the decimal concatenation of \(2n\) and \(2n^2\).                       

I could submit it for consideration by the OEIS arbiters but I probably won't as I find dealing with them rather tedious. However, I might change my mind. The sequence could be generalised of course to something like:


 A******

a(\(n\)) is the decimal concatenation of \(kn\) and \(kn^2\) where \(k = 2\)      
                 

I was happy to discover the concatenation of \(2n\) and \(2n^2\) in regard to 26338 as it shows that there are often patterns lurking in numbers that at first sight are not apparent. The list of terms, up to \(n=100\) is:
22, 48, 618, 832, 1050, 1272, 1498, 16128, 18162, 20200, 22242, 24288, 26338, 28392, 30450, 32512, 34578, 36648, 38722, 40800, 42882, 44968, 461058, 481152, 501250, 521352, 541458, 561568, 581682, 601800, 621922, 642048, 662178, 682312, 702450, 722592, 742738, 762888, 783042, 803200, 823362, 843528, 863698, 883872, 904050, 924232, 944418, 964608, 984802, 1005000, 1025202, 1045408, 1065618, 1085832, 1106050, 1126272, 1146498, 1166728, 1186962, 1207200, 1227442, 1247688, 1267938, 1288192, 1308450, 1328712, 1348978, 1369248, 1389522, 1409800, 14210082, 14410368, 14610658, 14810952, 15011250, 15211552, 15411858, 15612168, 15812482, 16012800, 16213122, 16413448, 16613778, 16814112, 17014450, 17214792, 17415138, 17615488, 17815842, 18016200, 18216562, 18416928, 18617298, 18817672, 19018050, 19218432, 19418818, 19619208, 19819602, 20020000

Of course, there can be no primes in this sequence because \(2 \times n\) will always be a factor and this is most easily seen when \(n\) is prime e.g. for \(n=83\), the sequence term is 16613778 which factorises to \(2 \times 83 \times 3 \times 73 \times 457\).

Sunday 9 May 2021

Collaboration between Integration and Summation

When it is permissible, it is often convenient when evaluating certain integrals to interchange the order of a summation and an integration. Let's use the following definite integral as an example to illustrate this technique:$$\int_0^{\infty}\frac{x}{e^x-1} \mathrm{d}x$$The graph is as shown in Figure 1.


Figure 1: created in GeoGebra

Let's begin the integration:$$\begin{align} \int_0^{1}\frac{x}{e^x-1} \mathrm{d}x&=\int_0^{1}\frac{x}{\dfrac{1}{e^{-x}}-1} \mathrm{d}x\\
&=\int_0^{1}\frac{x \, e^{-x}}{1-e^{-x}}\mathrm{d}x\\
&=\int_0^{1} x \, e^{-x} \left ( \dfrac{1}{1-e^{-x}} \right ) \mathrm{d}x\\
&=\int_0^{1} x \, e^{-x} \sum_{n=0}^{\infty} e^{-nx} \, \mathrm{d}x\\
&=\sum_{n=0}^{\infty} \int_0^{1} x \, e^{-x(n+1)} \, \mathrm{d}x\\
&=\sum_{n=1}^{\infty} \int_0^{1} x \, e^{-nx} \, \mathrm{d}x \\
\text{Now } \int x \, e^{-nx} \, \mathrm{d}x &= \int x \frac{\mathrm{d}}{\mathrm{d}x} \left (\frac{e^{-nx}}{-n} \right ) \, \mathrm{d}x\\
&=\frac{-x \, e^{-nx}}{n}+\frac{1}{n} \int e^{-nx} \, \mathrm{d}x\\
&=\frac{-x \, e^{-nx}}{n}- \frac{e^{-nx}}{n^2} +C\\
\text{So }\int_0^{1}\frac{x}{e^x-1} \mathrm{d}x&=\sum_{n=1}^{\infty} \left [ \frac{-x \, e^{-nx}}{n}- \frac{e^{-nx}}{n^2} \right ]_0^1\\
&=\sum_{n=1}^{\infty} \left ( \frac{-e^{-n}}{n}-\frac{e^{-n}}{n^2}+\frac{1}{n^2} \right )\\
&=\sum_{n=1}^{\infty} \frac{1}{n^2} -\sum_{n=1}^{\infty}\frac{e^{-n}}{n} -\sum_{n=1}^{\infty} \frac{e^{-n}}{n^2}\\
\text{Now }\sum_{n=1}^{\infty} \frac{1}{n^2} &=\zeta(2)\\
&=\frac{\pi^2}{6}\\
\sum_{n=1}^{\infty}\frac{e^{-n}}{n} &= 1-\ln(e-1) \\
\sum_{n=1}^{\infty}\frac{e^{-n}}{n^2} &= \text{Li}_2 \left (\dfrac{1}{e} \right )\\
\text{Hence } \int_0^{1}\frac{x}{e^x-1} \mathrm{d}x&=\frac{\pi^2}{6}+\ln(e-1) -\text{Li}_2 \left (\dfrac{1}{e} \right )-1\\
&\approx 0.777505

\end{align}$$Looking at Figure 1, it can be seen that this result looks just about right. I'm thankful to Mathematics M1's YouTube video for detailing the steps required to reach this result. I'm reproducing the steps here as a means of practising my LaTeX skills but it's also to remind me how interesting the integration technique is, specifically the way in which the integral and the summation are swapped around. Li is the Eulerian Logarithmic Integral and deserves a blog post of its own.$$ \mathrm{Li}(x)=\int_2^x \dfrac{\mathrm{d}t}{\ln t }= \mathrm{li}(x)-\mathrm{li}(2) \text{ where } \mathrm{li}(x)=\int_0^x \dfrac{\mathrm{d}t}{\ln t }$$

Friday 7 May 2021

The Egg Drop Numbers

It's always a delight to suddenly come across a new category of numbers that I haven't heard of before. Today I turned 26332 days old and discovered that this number is a member of OEIS A116082


 A116082

a(n) = C(n,7) + C(n,6) + C(n,5) + C(n,4) + C(n,3) + C(n,2) + C(n,1).


The sequence members, up to 26332, are as follows:

0, 1, 3, 7, 15, 31, 63, 127, 254, 501, 967, 1815, 3301, 5811, 9907, 16383, 26332

What caught my attention however, was a reference in the OEIS comments to The Egg Drop Numbers. This led to an interesting investigation, beginning with the so-called Two Egg Problem that is clearly stated on this site:

Egg Dropping Puzzle (2-egg, 100-floor version)
“Figure out the highest floor of a 100-floor building an egg can be dropped without breaking,  given two eggs”. The Egg Dropping Puzzle is a mathematical puzzle that has been around the internet for some time now, which is known to be adopted in interviews of major companies like Google, Microsoft, Accenture and even Hewlett Packard. You are to determine the minimum number of attempts required in the worst case scenario to find the critical floor.

 Assumptions in the Egg Dropping Puzzle:
  • The two eggs are identical.
  • If an egg does not break by dropping from a certain floor, it will not break dropping from any floor below that.
  • If an egg breaks by dropping on a certain floor, it will break dropping from any floor above that.
  • An egg may break by dropping on the 1st floor.
  • An egg may not break by dropping even on the 100th floor.
I won't repeat the explanation of how to solve this problem here, because that's provided on the site, but I will display the formula that is established viz.:
With \(x\) eggs and \(m\) trials, the maximum number of floors of a building we can test is given by: $$\binom {m}{1} +\binom {m}{2} + \dots + \binom {m}{x}$$

The site provides a spreadsheet that lists a wide range of results for different values of \(x\) and \(m\). Figure 1 shows an excerpt from the spreadsheet with some annotations added.


Figure 1

The members of OEIS A116082 appear as the entries in far right column under 7 eggs. Thus it is seen that:$$26332=\binom {16}{1} +\binom {16}{2} + \binom {16}{3}+\binom {16}{4} + \binom {16}{5} + \binom {16}{6} + \binom {16}{7}$$Thus, armed with 7 eggs, we can, with at most 16 trials, find the critical floor in a building with as many as 26332 floors. This is rather remarkable I think. 

Without the egg dropping association, OEIS A116082 would be rather bland but now I've become aware of a whole new category of numbers, The Egg Drop Numbers. On June 6th, 2025 (the anniversary of D-Day by the way), I will enjoy the next egg drop number, 27823, which is the maximum number of floors for which someone, armed with 9 eggs, will be able to determine the critical floor with at most 15 trials.

One last point to make is that, in the unlikely event that the number of eggs \(x\) exceeds the number of trials \(m\), then the formula becomes:$$\binom {m}{1} +\binom {m}{2} + \dots + \binom {m}{\min(x, m)}$$

Sunday 2 May 2021

Home Primes

I first mentioned Home Primes in a post from Sunday, March 8th 2020, titled Prime Weeks. As the Wikipedia entry states regarding this class of primes:

Investigations into home primes make up a minor side issue in number theory. Its questions have served as test fields for the implementation of efficient algorithms for factoring composite numbers, but the subject is really one in recreational mathematics.

So let's put serious mathematics aside and delve into this corner of recreational mathematics. Let's begin with the definition, from the same source, that runs:

In number theory, the home prime HP(\(n\)) of an integer \(n\) greater than 1 is the prime number obtained by repeatedly factoring the increasing concatenation of prime factors including repetitions. 

Using SageMath, I was able to create an algorithm to determine the home prime for any composite integer. See Figure 1 with permalink attached.


Figure 1: permalink

As can be seen, the number 26327 (my diurnal age on the day of this post's creation) leads, after eight steps, to its home prime of 3325112912503. Apart from the fact that it represents my diurnal age, the reason that I chose 26327 as my example above is that it factorises to 7 x 3761 and the latter number has an important connection to home primes because it is a member of OEIS A118756:


 A118756

a(\(n\)) = smallest prime \(p\) such that \(p\) is the home prime of exactly \(n\) natural numbers.


The sequence begins: 2, 23, 211, 379, 773, 3389, 23251, 3761, ... and so 3761 is in the position corresponding to \(n=8\). This means that there are seven composite numbers whose home prime is 3761. These are listed in the OEIS comments section for the sequence. The eight numbers are:

140, 332, 514, 566, 1281, 2257, 2283, 3761

Let's now consider OEIS A037274 that lists the home primes (if known) for all the natural numbers:


 A037274



Home primes: for n >= 2, a(n) = the prime that is finally reached when you start with n, concatenate its prime factors (A037276) and repeat until a prime is reached (a(n) = -1 if no prime is ever reached).


Here is the sequence up to \(n=48\):
1, 2, 3, 211, 5, 23, 7, 3331113965338635107, 311, 773, 11, 223, 13, 13367, 1129, 31636373, 17, 233, 19, 3318308475676071413, 37, 211, 23, 331319, 773, 3251, 13367, 227, 29, 547, 31, 241271, 311, 31397, 1129, 71129, 37, 373, 313, 3314192745739, 41, 379, 43, 22815088913, 3411949, 223, 47, 6161791591356884791277

Looking at the terms in this sequence, it can be seen that the home prime for \(n=8\) is a staggering 3331113965338635107. The progression is as follows:

8 -> 2 * 2 * 2 

222 -> 2 * 3 * 37 

2337 -> 3 * 19 * 41 

31941 -> 3 * 3 * 3 * 7 * 13 * 13 

33371313 -> 3 * 11123771 

311123771 -> 7 * 149 * 317 * 941 

7149317941 -> 229 * 31219729 

22931219729 -> 11 * 2084656339 

112084656339 -> 3 * 347 * 911 * 118189 

3347911118189 -> 11 * 613 * 496501723 

11613496501723 -> 97 * 130517 * 917327 

97130517917327 -> 53 * 1832651281459 

531832651281459 -> 3 * 3 * 3 * 11 * 139 * 653 * 3863 * 5107

3331113965338635107 is prime, so a(8) = 3331113965338635107

However, upon reaching \(n=49\), we encounter the first number that has no known home prime. The composite numbers deriving from 49 and that so far do not lead to a prime are listed in OEIS A056938:


 A056938

Concatenate all the prime divisors in previous term (with repetition), starting at 49.

The initial terms are:

49, 77, 711, 3379, 31109, 132393, 344131, 1731653, 71143523, 11115771019, 31135742029, 717261644891, 11193431873899, 116134799345907, 3204751189066719, 31068250396355573, 62161149980213343, 336906794442245927, 734615161567701999, 31318836286194043641 

IMPORTANT RESOURCES

This site provides a list of numbers up to 10000 together with the progressions to their respective home primes (if known). 

This site lists the 471 numbers less than 10000 for which there are no known home primes. In TABLE 1 below I've copied and pasted the first column. The numbers with backgrounds shaded in green may have home primes but not those unshaded (as far as is known). For example, 669 leads to a home prime after 46 steps. I developed a modified algorithm to take into account numbers that don't end in a prime after a certain number of cycles (50 seems to be about the limit for SageMathCell). See Figure 2 that uses 669 as an example. Permalink attached.


Figure 2: permalink

TABLE 1

49
112
146
234
242
284
300
312
320
322
326
328
336
352
363
372
412
460
495
548
556
576
596
663
665
669
670
693
712
714
715
744
749
762
768
782
796
845
847
858
861
867
896
925
973
978
984
992
1008
1030
1053
1067
1138
1139
1220
1248
1298
1314
1315
1316
1328
1370
1394
1408
1416
1444
1448
1452
1455
1456
1467
1515
1519
1521
1529
1539
1552
1565
1568
1595
1596
1610
1628
1672
1681
1726
1734
1751
1757
1772
1781
1782
1846
1855
1897
1908
1915
1956
1964
1980
1985
2008
2021
2025
2040
2048
2068
2071
2104
2105
2112
2114
2117
2138
2147
2148
2172
2189
2206
2248
2252
2262
2265
2280
2316
2320
2321
2360
2390
2410
2432
2436
2442
2465
2480
2484
2510
2520
2558
2560
2581
2594
2611
2618
2637
2642
2658
2660
2662
2684
2686
2745
2774
2784
2796
2800
2802
2812
2816
2842
2848
2888
2922
2965
2993
3006
3016
3024
3036
3038
3056
3068
3102
3108
3110
3136
3158
3168
3172
3192
3200
3208
3210
3215
3238
3250
3252
3262
3270
3278
3285
3286
3288
3296
3304
3332
3336
3363
3368
3370
3386
3388
3393
3408
3429
3451
3454
3466
3470
3475
3489
3492
3495
3498
3520
3586
3604
3606
3662
3675
3685
3720
3721
3755
3766
3776
3782
3790
3800
3806
3813
3816
3835
3836
3852
3858
3867
3868
3879
3894
3905
3909
3916
3955
3966
3968
3970
4012
4020
4036
4046
4048
4050
4060
4065
4067
4097
4108
4109
4122
4145
4172
4186
4188
4203
4205
4224
4225
4230
4240
4257
4260
4300
4301
4318
4320
4352
4436
4440
4442
4454
4470
4480
4494
4497
4500
4532
4541
4556
4557
4559
4574
4580
4581
4582
4632
4687
4695
4719
4746
4776
4777
4790
4791
4836
4852
4883
4884
4887
4890
4891
4911
4927
4930
4936
4941
4944
4946
4980
4986
4992
5010
5029
5037
5055
5060
5090
5110
5115
5116
5145
5152
5154
5160
5180
5182
5185
5187
5194
5214
5256
5278
5280
5284
5301
5312
5320
5324
5368
5370
5377
5400
5403
5406
5416
5432
5460
5465
5488
5494
5496
5536
5551
5564
5608
5620
5621
5632
5652
5668
5670
5674
5680
5692
5698
5708
5720
5736
5740
5756
5760
5778
5792
5800
5845
5856
5858
5866
5871
5874
5882
5905
5910
5912
5916
5931
5949
6013
6024
6063
6069
6077
6078
6084
6094
6100
6102
6138
6146
6149
6154
6175
6176
6205
6210
6212
6223
6227
6244
6256
6294
6314
6328
6332
6333
6336
6351
6366
6384
6386
6400
6405
6409
6414
6436
6444
6445
6448
6452
6454
6467
6495
6516
6533
6541
6548
6550
6561
6572
6612
6615
6666
6670
6671
6680
6710
6729
6785
6811
6812
6816
6819
6820
6836
6840
6859
6864
6873
6877
6906
6919
6932
6944
6972
6985
6989
7009
7017
7024
7032
7048
7049
7056
7059
7065
7072
7089
7091
7092
7096
7119
7128
7168
7188
7194
7203
7204
7210
7248
7267
7282
7316
7343
7345
7360
7385
7394
7395
7403
7465
7494
7506
7540
7554
7562
7615
7628
7648
7654
7668
7686
7696
7707
7714
7720
7749
7765
7770
7776
7824
7826
7832
7864
7865
7872
7880
7896
7902
7904
7923
7965
7972
7987
8000
8008
8020
8049
8085
8112
8114
8120
8127
8134
8155
8170
8178
8189
8193
8222
8250
8255
8262
8277
8324
8349
8375
8382
8393
8398
8448
8449
8457
8475
8506
8516
8540
8546
8558
8560
8562
8569
8575
8585
8592
8603
8608
8610
8618
8624
8635
8668
8670
8680
8696
8704
8709
8710
8729
8734
8736
8739
8740
8757
8763
8784
8790
8793
8806
8824
8846
8873
8874
8890
8909
8932
8934
8940
8943
8949
8960
9002
9012
9025
9027
9048
9075
9080
9086
9088
9095
9104
9119
9120
9130
9141
9145
9158
9189
9262
9266
9273
9282
9295
9316
9328
9339
9350
9373
9412
9446
9448
9449
9458
9482
9486
9487
9495
9499
9502
9513
9524
9529
9570
9577
9585
9588
9591
9594
9595
9600
9603
9620
9624
9630
9644
9648
9651
9659
9667
9685
9688
9690
9702
9724
9732
9740
9747
9761
9773
9780
9792
9812
9815
9836
9863
9874
9877
9881
9890
9900
9922
9937
9951
9961
9964
9965
9975
9978
9983
9998
10014
10018
10024
10031
10045
10048
10050
10052
10058
10064
10081
10090
10094
10098
10132
10136
10158
10179
10200
10203
10208
10218
10234
10240
10244
10266
10270
10272
10302
10304
10305
10312
10332
10335
10353
10374
10380
10395
10409
10411
10415
10424
10437
10467
10478
10485
10490
10492
10496
10523
10530
10538
10541
10542
10566
10572
10577
10579
10580
10595
10609
10610
10616
10620
10624
10640
10650
10659
10668
10676
10683
10700
10703
10748
10755
10764
10773
10825
10829
10830
10832
10836
10845
10850
10863
10864
10865
10872
10895
10913
10914
10948
10956
10969
10971
10972
10976
10982
10991
11000
11011
11024
11040
11067
11080
11130
11133
11136
11168
11183
11187
11189
11244
11247
11254
11256
11275
11280
11286
11293
11334
11370
11378
11440
11476
11496
11500