Golomb's Tromino Theorem

When reading this Quanta article about the Fields Medal recipient Yu Deng, I came across this paragraph:

On some of those hikes, his father gave him math problems to solve. He still remembers one: You have a square grid divided into a certain number of cells. Prove that if you remove any one cell from the grid — it doesn’t matter which — you can always perfectly divide the rest of the grid into L-shaped pieces made from three cells each. The solution, which Deng figured out, required a concept known as induction, usually taught in high school. Deng was 7 years old.

I asked Gemini about its solution and this was its response:

This classic tiling puzzle is formally known as Golomb’s Tromino Theorem. For this division to be guaranteed regardless of which cell you remove, the grid must specifically be a square of dimensions \(2^n \times 2^n\), where \(n\) is any positive integer (\(2 \times 2\), \(4 \times 4\), \(8 \times 8\), and so on).

Before diving into the mechanics, notice the foundational arithmetic that makes this possible: a \(2^n \times 2^n\) grid contains \((2^n)^2 = 4^n\) total cells. When you remove any one cell, you are left with \(4^n - 1\) cells. Because \(4^n \equiv 1 \pmod 3\) for all positive integers \(n\), the quantity \(4^n - 1\) is always perfectly divisible by \(3\). This guarantees that the remaining area at least has the potential to be covered by \(3\)-cell L-shaped tiles (trominoes) without any left-over space.

The Mathematical Induction Proof

The beauty of the induction approach lies in a clever divide-and-conquer strategy that reduces any large grid down to simple \(4\)-cell squares.

Step 1: The Base Case (\(n = 1\))

Consider the smallest possible power-of-two grid: a \(2^1 \times 2^1 = 2 \times 2\) square containing \(4\) cells. If you remove any one cell from a \(2 \times 2\) grid, the remaining \(3\) cells naturally form an L-shape. A single L-tromino covers this remaining area perfectly. The base case holds.

Step 2: The Inductive Hypothesis

Assume that for some arbitrary positive integer \(k\), any \(2^k \times 2^k\) grid with a single cell removed can be tiled completely by L-trominoes without overlapping or hanging off the edges.

Step 3: The Inductive Step (\(n = k + 1\))

Now consider a larger grid of size \(2^{k+1} \times 2^{k+1}\). We must prove it can also be tiled if any single cell is removed.

1. Divide into Quadrants: Slice the \(2^{k+1} \times 2^{k+1}\) grid horizontally and vertically through its center. This divides the board into four equal quadrants, each of size \(2^k \times 2^k\).
   
   
2. Locate the Missing Cell: The single removed cell must lie inside exactly one of these four quadrants. We will call this the deficient quadrant. Because this deficient quadrant is a \(2^k \times 2^k\) grid missing exactly one cell, our inductive hypothesis guarantees that we can tile it completely with L-trominoes!
   
   
3. The Center Trick: We are now left with three intact \(2^k \times 2^k\) quadrants that have no missing cells. To apply our hypothesis to them, take one single L-tromino and place it squarely at the exact center intersection of the overall board. Orient this tile so that it covers exactly one corner cell of each of the three non-deficient quadrants—specifically, the three innermost corners that meet at the center of the board.
   
   
4. Recurse: By placing that one central tromino, we have effectively "removed" one cell from each of the three remaining quadrants. Now, all four quadrants are independent \(2^k \times 2^k\) grids that are each missing exactly one cell!
   
   
5. By our inductive hypothesis, all four quadrants can now be tiled perfectly by L-trominoes. Therefore, the entire \(2^{k+1} \times 2^{k+1}\) grid minus one cell is successfully tiled.

Figure 1 shows the 8 x 8 case:

Figure 1

28224: An Interesting Number

28224 has 194 entries in the OEIS which is extraordinarily high for a five digit number. In this post I'll be discussing some of this number's most interesting properties but not all of them. There are just too many. It's prime factorisation is:$$28224=2^6 \times 3^2 \times 7^2$$FIRST INTERESTING PROPERTY

Numbers that are perfect squares are quite rare in the range up to 40000. There are only 200 of them and 28224, my diurnal age today, is one of them. It has the property that:$$28224=168^2$$The number of days between my experience of them is a little less than a year. There is a gap of exactly 365 days between \(183^2\) and \(182^2\) since:$$ \begin{align} 183^2-182^2 &= (183 + 182)(183-182) \\ &=365 \times 1 \\ &=365 \end{align}$$I'll be \(33124\) or \(182^2\) days when I'm over \(90\) years old so I may not get to experience the transition from this square to the next.

28224 is also a Loeschian number since it is equal to \(72^2+ 72 \times 120 + 120^2\).

28224 also has a product of digits (256) that is a perfect square since \(256=16^2\).

SECOND INTERESTING PROPERTY

Numbers that are the sum of two positive cubes are relatively rare in the range up to 40000. In fact, there are only 378 numbers in the range up to 40000 and 28224 is one of them because:$$28224=22^3 + 26^3$$These numbers form OEIS A004999.

THIRD INTERESTING NUMBER

Energetic numbers are numbers that can be broken into two or more substrings and expressed as a sum of (possibly different) positive powers of those substrings. They form OEIS  A055480. 28224 is one such number because:$$28224=28^3 + 2^{11} + 2^7 + 4^6$$I discuss this category of numbers in my blog post Energetic Numbers.

FOURTH INTERESTING NUMBER

Friedman numbers are positive integers which can be written in some non-trivial way using its own digits, together with the symbols + – × / ^ ( ) and concatenation. 28224 is one such number because:$$28224 = (2 + 82)^2 × 4$$It is said to be a "nice" Friedman number because the digits are in the same order as the number. These numbers are listed on my blog post Narcissistic, D-Powerfull and Friedman Numbers.

FIFTH INTERESTING NUMBER

28224 has the property that certain of its factors (not necessarily prime) can be arranged to form a palindrome. Specifically:$$2 \times 2 \times 2 \times 882 \times 2 \times 2 = 22288222$$I've written about these sorts of numbers in a post titled Why Is 313131 An Interesting Number?

SIXTH INTERESTING PROPERTY

28224 is a concatenation of powers of 2 since:$$28224= 2^1 \; || \; 2^3 \; || \; 2^1 \; || \; 2^1 \; || \; 2^2$$I've written about numbers that can be formed in this way in a blog post titled Nothing New Under The Sun. It is also a concatenation of multiples of 7 since:$$28224= (7 \times 4) \, || \, (7 \times 32)$$I posted about these sorts of concatenations in my blog post More Numbers as Concatenations.

SEVENTH INTERESTING PROPERTY

28224 is a member of OEIS A253824 where$$ \text{numbers } m = s \, || \, t \text{ such that } m = \sigma(s) \times \sigma(t)$$where || represents concatenation. In the case of 28224 we have:$$ \begin{align} 28224 &= 28 \, || \, 224 \\ &= \sigma(28) \times \sigma(224) \\ &= 56 \times 504 \\ &=28224 \end{align}$$28224 is only the third such number in the range up to 40000. The two earlier numbers are 540 and 2352.

EIGHTH INTERESTING PROPERTY

28224 has a digit sum of 18 and when this is added to the number the result is 28242 which has the same digits as 28224 but in a slightly different order. This property makes it a member of OEIS A246420.

A246420

Numbers \(n\) such that \(n\)  + digit sum of \(n\) is a permutation of the decimal digits of \(n\) .

Numbers Within Numbers

Let's formalise the concept of internal digits. Take a number like 28211. It's prime but if we remove the leftmost digits (2) and the rightmost digit (1), we are left with the number 821. This is the number within a number and it happens to be prime also. It is thus a member of OEIS A069686:

 A069686: primes whose internal digits form a prime.

The members of this sequence from 28000 to 40000 are (permalink):

28097, 28099, 28111, 28211, 28219, 28277, 28279, 28297, 28393, 28537, 28571, 28573, 28579, 28591, 28597, 28631, 28771, 28813, 28817, 28837, 28871, 28879, 29077, 29191, 29297, 29411, 29473, 29531, 29537, 29671, 29717, 29833, 29837, 29917, 30029, 30059, 30071, 30113, 30119, 30133, 30137, 30139, 30197, 30293, 30313, 30319, 30431, 30539, 30593, 30671, 30677, 30713, 30839, 30893, 30971, 30977, 31013, 31019, 31033, 31039, 31079, 31091, 31139, 31271, 31277, 31319, 31379, 31391, 31393, 31397, 31511, 31513, 31517, 31573, 31793, 31799, 31817, 31973, 31991, 32117, 32119, 32233, 32237, 32297, 32299, 32411, 32413, 32573, 32579, 32633, 32693, 32713, 32717, 32719, 32771, 32779, 32831, 32833, 32839, 32933, 32939, 33071, 33073, 33113, 33119, 33179, 33311, 33317, 33377, 33479, 33493, 33533, 33599, 33679, 33739, 33791, 33797, 33893, 34019, 34211, 34213, 34217, 34313, 34319, 34337, 34439, 34499, 34613, 34631, 34673, 34679, 34871, 34877, 34913, 34919, 35099, 35419, 35573, 35771, 35879, 35933, 35993, 35999, 36011, 36013, 36017, 36073, 36131, 36137, 36191, 36313, 36319, 36433, 36473, 36479, 36599, 36739, 36779, 36833, 36913, 36919, 37013, 37019, 37097, 37199, 37273, 37277, 37337, 37339, 37397, 37511, 37517, 37571, 37573, 37579, 37619, 37691, 37693, 37699, 37871, 37879, 38113, 38119, 38219, 38231, 38237, 38239, 38273, 38299, 38393, 38593, 38639, 38833, 38839, 38873, 39079, 39113, 39119, 39191, 39199, 39293, 39371, 39373, 39419, 39671, 39679, 39719, 39779, 39839, 39971, 39979

We can modify the algorithm to search for square numbers within square numbers. For example, \(144 = 12^2\) and its internal digit \(4 = 2^2\) and so it is a member of OEIS A069701:

 A069701: squares with internal digits also forming a square > 0.

The members up to 40000 are few and far between: 

144, 196, 441, 841, 1369, 3364, 4096, 5041, 8649, 10816, 11449, 20164, 38416.

So the takeaway from this is that every \(n\) digit number has an (\(n-2\)) digit number inside of it provided \(n>2\) and sequences can be developed by relating this internal number to the larger number of which it forms a part.

Let's consider numbers that are biprime and whose internal digits also form a biprime. Take 28189 as an example:$$ \begin{align} 28189 &= 7 \times 4027 \\ 818 &= 2 \times 409 \end{align}$$These sorts of numbers are not listed in the OEIS. 

Similarly for triprimes. Take 28055 as an example:$$ \begin{align} 28055 &= 5 \times 31 \times  181\\805 &= 5 \times 7 \times 23 \end{align}$$Of course we could consider numbers within numbers within numbers etc. but given that I'm mainly examining five digit numbers less than 40000, I'll leave off at numbers within numbers. Of course, these relationships between numbers and their respective internal numbers only apply with certainty in the number base under consideration (base 10 so far in this post). Take our earlier example of 28211 and its internal number of 821. Both are prime. Let's change to base 9:$$ \begin{align} 28211_{10} &= 42625_9 \rightarrow 265_9 \text{ as its internal number} \\ 265_9 &= 218_{10} \text{ which is clearly not prime} \end{align} $$Primeness is base independent and if a number is not prime in a certain base then it is not prime in any base. However, the inner number while not prime in base 10 may be prime if regarded as a number in another base. Let's illustrate this with 28019. It is a prime in base 10 where the inner number, 801, is divisible by 3. However, we can note the following:$$ \begin{align} 801_{12} &= 1153_{10} \text{ which is prime}\\801_{15} &= 1801_{10} \text{ which is prime} \end{align} $$I've incorporated the search for the following types of numbers into my number analysis algorithm so that the following types of numbers can be identified:

• prime number whose internal number is also prime in any base from 2 to 16
• biprime number whose internal number is also prime using base 10 only
• triprime number whose internal number is also triprime using base 10 only
• square number whose internal number is also square using base 10 only

888 Revisited

In November of 2021, I posted about 888 from a mathematical and non-mathematical perspective. Mathematically, I noted that:

• 888 is the smallest cube in which each digit occurs exactly three times. The list up to one million of such numbers is (permalink):

888, 56592, 58524, 65577, 70869, 78183, 496941, 512427, 516267, 517461, 557949, 565920, 581421, 585558, 661959, 711828, 713772, 723627, 724983, 733053, 739563, 764472, 781830, 877242, 988458

• 888 is the only cube in which three digits occur three times. For example, the next number in the previous sequence (56592) has a cube of 181244621426688 but there are four digits that occur three times.
  
  
• 888 the smallest multiple of 24 whose digit sum is 24 and, as well as being divisible by its digit sum, it is divisible by all of its digits.
  
  
• 888 and 24 show up again in the former's membership of OEIS 236661 where 888 counts the number of partitions of 24 that have a standard deviation greater than 2. Permalink.
  
  
• Other properties of 888 include its being a happy, Harshad, Moran, nude, strobogrammatic, modest, congruent, amenable, practical, abundant, pseudoperfect and Zumkeller number (see Numbers Aplenty).
  
  
• The 8's are involved in 888 again thanks to its membership of OEIS A127335.
  
  

A127335

Numbers that are the sum of 8 successive primes.

 The sequence runs:

77, 98, 124, 150, 180, 210, 240, 270, 304, 340, 372, 408, 442, 474, 510, 546, 582, 620, 660, 696, 732, 768, 802, 846, 888

The eight successive primes in the case of 888 are 97, 101, 103, 107, 109, 113, 127 and 131 with an average of 111. Both 111 and 888 are of course repdigits along with the infamous 666 or number of the beast.

• 888 arises in the context of aliquot sequences via OEIS A014360:
  
  

A014360

Aliquot sequence starting at 552.

The sequence begins:

552, 888, 1392, 2328, 3552, 6024, 9096, 13704, 20616, 30984, ...

To quote from Wolfram Alpha:

It has not been proven that all aliquot sequences eventually terminate and become periodic. The smallest number whose fate is not known is 276. There are five such sequences less than 1000, namely 276, 552, 564, 660, and 966, sometimes called the "Lehmer five". 

In this post, I'll revisit 888 but I'll be doing so via 28192, the number associated with my diurnal age today. This number has the interesting property that its square and cube both contain the digit sequence 888:$$ \begin{align} 28192^2 &= 7947\textbf{888}64 \\ 28192^3 &= 22406687653\textbf{888} \end{align} $$There are only four such numbers in the range up to 40000 and they are 3192, 28192, 31920 and 33878. One of these, 31920, is simply a derivative of 3192. Of these four numbers, it is only 28192 that contains three eights when expressed in terms of its prime factors:$$2\textbf{8}192 = 2^5 \times \textbf{88}1$$It could even be written as \(2^2 \times \textbf{8} \times \textbf{88}1 \) so it is very giving in terms of its eightness!

What about other numbers in the range up to 40000 that display three digit repdigits when squared and cubed? Here are the numbers that satisfy:

For repdigit \( \textbf{111}\), there is only one number that satisfies:

• \(10558^2= \textbf{111}471364 \text{ and } 10558^3 =117691466\textbf{111}2\)

For repdigits \( \textbf{222} \) and \( \textbf{333} \), no numbers satisfy but for repdigit \( \textbf{444}\) we have:

• \(6962^2 = 48469\textbf{444} \text{ and } 6962^3 = 337\textbf{444}269128\)
• \(12038^2 = 144913\textbf{444} \text{ and } 12038^3 = 17\textbf{444}68038872\)
• \(21081^2 = \textbf{4444}08561 \text{ and } 21081^3 = 936857687\textbf{444}1\)
• \(32538^2 = 1058721\textbf{444} \text{ and } 32538^3 = 3\textbf{444}8678344872\)
• \(37808^2 = 1429\textbf{444}864 \text{ and } 37808^3 = 540\textbf{444}51418112\)

For repdigit \( \textbf{555} \), again only one number satisfies:

• \(38152^2 =14\textbf{555}75104 \text{ and } 38152^3 = \textbf{555}33101367808\)

For the famous repdigit \( \textbf{666} \), we have two numbers that satisfy with some extra 6's thrown in for the case of \(30605\):

• \(17767^2 = 315\textbf{666}289 \text{ and } 17767^3 = 560844295\textbf{666}3\)
• \(30605^2 = 93\textbf{6666}025 \text{ and }30605^3 = 28\textbf{66666}3695125\)

For the repdigit \( \textbf{777} \), again two numbers satisfy:

• \( 18924^2 = 35811\textbf{777}6 \text{ and }18924^3= 6\textbf{777}020793024 \)
• \( 34753^2 =120\textbf{777}1009 \text{ and } 34753^3 = 41973665875\textbf{777} \)

For the repdigit \( \textbf{999} \) we have a bonanza so I'll just list the numbers and show one example:

\( 9997, 9998, 9999, 19998, 19999, 29999, 38729, 39999 \)

• \(9997^2 = \textbf{999}40009 \text{ and } 9997^3 = \textbf{999}100269973\)

Digit Manipulation

Video created by NotebookLM based on blog content

DIGITS TO SQUARES

Yesterday I turned 28113 days old and this number is a member of OEIS A048383: numbers \(k\) such that replacing each nonzero digit \(d\) with the \(d\)-th prime (replacing each 0 digit with a 1) yields a square. So this means that:$$28113 \rightarrow 319225 = 5^2 \times 113^2$$The members of this sequence are few and far between and in the range up to 40000 only the following numbers satisfy (permalink):$$ \begin{align} 0 &\rightarrow 1 = 1\\13 &\rightarrow 25 = 5^2\\113 &\rightarrow 225 = 3^2 \times 5^2\\2410 &\rightarrow 3721 = 61^2\\4113 &\rightarrow 7225 = 5^2 \times 17^2\\6113 &\rightarrow 13225 = 5^2 \times 23^2\\8210 &\rightarrow 19321 = 139^2\\14113 &\rightarrow 27225 = 3^2 \times 5^2 \times 11^2\\23410 &\rightarrow 35721 = 3^6 \times 7^2\\28113 &\rightarrow 319225 = 5^2 \times 113^2\\33113 &\rightarrow 55225 = 5^2 \times 47^2\\34010 &\rightarrow 57121 = 239^2\\35113 &\rightarrow 511225 = 5^2 \times 11^2 \times 13^2\\\end{align}$$DIGITS TO PRIMES

A variation on this theme is OEIS A048381:

A048381: numbers \(k\) such that replacing each nonzero digit \(d\) with the \(d\)-th prime (replacing each 0 digit with a 1) yields a prime.

Members of this sequence are far more numerous with 5629 in the range up to 40000. An example is 28112 since:$$28112 \rightarrow 319223 \text{ which is prime} $$Some upcoming members are:

28124, 28146, 28152, 28155, 28202, 28210, 28214, 28216, 28226, 28228, 28230, 28234, 28235, 28236, 28247, 28265, 28270, 28277, 28289, 28294, 28295, 28298, 28300, 28317, 28319, 28328, 28329, 28344, 28359, 28360, 28368, 28388, 28392, 28397, 28414, 28418, 28422, 28429, 28434, 28449, 28458, 28464, 28470, 28474, 28485, 28490, 28498, 28502, 28504, 28515, 28524, 28525, 28529, 28546, 28562, 28575, 28592, 28599, 28606, 28612, 28614, 28622, 28630, 28652, 28658, 28665, 28667, 28674, 28684, 28686, 28706, 28717, 28724, 28744, 28752, 28772, 28786, 28807, 28810, 28814, 28825, 28827, 28838, 28854, 28868, 28870, 28876, 28886, 28888, 28890, 28928, 28929, 28932, 28948, 28955, 28960, 28966, 28979, 28984, 28988, 28995, 28997

One way to thin the numbers when there are so many in a given range is to require that the numbers come in pairs that are consecutive integers. If this requirement is imposed then the 5629 reduces to 580. Imposing the restriction that the numbers are triplets that are consecutive integers reduces the 580 further to a manageable 103:

1, 2, 3, 4, 5, 6, 7, 24, 25, 144, 166, 167, 414, 474, 506, 674, 897, 898, 1026, 1027, 1176, 1177, 1398, 1516, 1824, 2035, 2074, 2094, 2146, 2544, 3316, 4044, 5247, 5248, 5286, 5514, 6044, 6484, 7116, 7117, 7118, 7264, 7918, 8008, 8127, 8444, 8665, 10016, 11046, 11047, 11404, 13068, 13445, 14224, 14584, 15886, 16055, 16346, 16347, 16505, 16945, 18306, 18497, 19276, 19465, 20044, 20124, 21797, 21798, 22167, 22416, 22417, 22586, 22694, 22767, 23336, 23774, 24726, 24727, 24845, 25934, 26608, 26844, 26885, 28234, 29376, 29377, 29714, 29715, 29917, 30145, 30705, 32244, 32248, 33807, 35405, 35647, 36018, 36635, 37888, 38097, 39067, 39527

Let's take 28234 as an example where:$$ \begin{align} 28234 &\rightarrow 319357\\28235 &\rightarrow 3193511\\28236 &\rightarrow 3193513 \end{align}$$There is of course an initial run of seven numbers (1 to 7) and after that there are runs of four numbers beginning with:

24, 166, 897, 1026, 1176, 5247, 7116, 7117, 11046, 16346, 21797, 22416, 24726, 29376, 29714

Finally there is only one run of five numbers and it starts with 7116.

DIGITS TO PALINDROMES

Another variation, using this same method of digit manipulation, is to ask what non-palindromic number become palindromes. Well, in the range up to 40000, it turns out that 333 numbers satisfy this condition (permalink). The numbers from 28113 onwards are:

28086, 28586, 28686, 28786, 28802, 28886, 29029, 29069, 29129, 29199, 29212, 29229, 29329, 29429, 29529, 29569, 29612, 29669, 29769, 29869, 29912, 29999, 30053, 30553, 30653, 30753, 30853, 32063, 32193, 32563, 32663, 32763, 32863, 32993, 34073, 34573, 34673, 34773, 34873, 35003, 35503, 36203, 36603, 36903, 37403, 37703, 38803, 39213, 39613, 39913

Let's use 28086 as an example:$$28086 \rightarrow 31911913$$Clearly there are many possible variations using just this particular type of digit manipulation and in this post I've shown examples of three of them where the digits \(d\) are manipulated as follows:$$ \begin{align} d &\rightarrow \text{ prime}(d) \text{ if } d \neq 0 \\0 &\rightarrow 1 \end{align} $$However, other manipulations are limited only by your imagination. An example of different type of manipulation would be:$$ d \rightarrow d^{ \, \small{2}}$$We can ask how many non-palindromic numbers become palindromes when their digits are manipulated in this manner (squared). In the range up to 40000, the answer is that there are 96 suitable numbers and they are (permalink):

19, 28, 37, 41, 72, 199, 288, 327, 377, 441, 461, 732, 772, 1191, 1281, 1371, 1411, 1721, 1919, 1999, 2192, 2282, 2372, 2412, 2722, 2828, 2888, 3193, 3207, 3217, 3227, 3237, 3283, 3373, 3413, 3723, 3737, 3777, 4141, 4441, 4661, 7032, 7132, 7232, 7272, 7332, 7772, 11991, 12881, 13271, 13771, 14411, 14611, 17321, 17721, 19019, 19119, 19219, 19319, 19999, 21992, 22882, 23272, 23772, 24412, 24612, 27322, 27722, 28028, 28128, 28228, 28328, 28888, 31993, 32007, 32117, 32197, 32227, 32287, 32337, 32377, 32417, 32727, 32883, 33273, 33773, 34413, 34613, 37037, 37137, 37237, 37277, 37323, 37337, 37723, 37777

An example is 28028 where$$28028 \rightarrow 4640464$$

Prime Sum of Divisors

Surprisingly, for me at least, there are not many numbers whose sum of divisors is prime. However, the number associated with my diurnal age today, \( \textbf{27889}\), is one such number. The numbers up to 40000 are 2, 4, 9, 16, 25, 64, 289, 729, 1681, 2401, 3481, 4096, 5041, 7921, 10201, 15625, 17161, 27889, 28561 and 29929. These are the initial terms of OEIS A023194. Here is the breakdown (with 2 excluded - permalink):

number   square root   sigma

  4        2             7

  9        3             13

  16       4             31

  25       5             31

  64       8             127

  289      17            307

  729      27            1093

  1681     41            1723

  2401     49            2801

  3481     59            3541

  4096     64            8191

  5041     71            5113

  7921     89            8011

  10201    101           10303

  15625    125           19531

  17161    131           17293

  27889    167           28057

  28561    169           30941

  29929    173           30103

The members of this sequence are all square numbers with the exception of 2. Some are powers of 2 as well such as 16, 64 and 4096. The OEIS comments contain the following observations (that I'm not sure I understand):

All terms except the first are squares. Why? 

 

Answer from Gabe Cunningham (gcasey@mit.edu): "From the fact that the sigma (the sum-of-divisors function) is multiplicative, we can derive that the \( \sigma(n)\) is even except when \(n\) is a square or twice a square. 

 

"If \(n = 2 \times (2 \times k + 1)^2\), that is, \(n\) is twice an odd square, then:$$ \sigma(n) = 3 \times \sigma((2 \times k + 1)^2)$$If \(n = 2 \times (2 \times k)^2 \), that is, \(n\) is twice an even square, then \( \sigma(n)\) is only prime if \(n\) is a power of 2; otherwise we have:$$ \sigma(n) = \sigma(8 \times 2^m) \times \sigma(k/2^m)$$ for some positive integer \(m\). 

 

"So the only possible candidates for values of n other than squares such that \( \sigma(n)\) is prime are odd powers of 2. But:$$ \begin{align} \sigma(2^{(2 \times m + 1)}) &= 2^{(2 \times m + 2)} - 1 \\ &= (2^{m + 1} + 1) \times (2^{m + 1 }- 1) \end{align}$$which is only prime when \(m = 0\), that is, when \(n = 2\). So 2 is the only nonsquare \(n\) such that \( \sigma(n)\) is prime."

I looked to Gemini to explain what the above means by asking the following question;

What does it mean to say that "the sigma function is multiplicative" where sigma is the sum of divisors function? The fuller quote is as follows: 

... I just included the quote above ...

The quote is taken from the comments to OEIS A023194 (https://oeis.org/A023194). Can you break this down for me as I simply don't understand what the author is on about?

Here was the response (link):

Of course. Let's break down this number theory argument step by step. It's a great example of how a single property of a function can lead to a powerful conclusion.

What does "Multiplicative" Mean?

First, let's tackle the main concept. In number theory, a function f(n) is called multiplicative if, for any two coprime integers a and b, the following equation holds true:

f(a * b) = f(a) * f(b)

Coprime means that the two numbers share no common factors other than 1. For example, 4 and 9 are coprime, but 6 and 9 are not (they share a common factor of 3).

The sigma function, written as σ(n), calculates the sum of all the positive divisors of a number n.

Let's test the multiplicative property with an example, n = 12.

We can split 12 into the coprime factors 3 and 4.

• σ(12): The divisors of 12 are 1, 2, 3, 4, 6, and 12. Their sum is 1 + 2 + 3 + 4 + 6 + 12 = 28.

• σ(3): The divisors of 3 are 1 and 3. Their sum is 1 + 3 = 4.

• σ(4): The divisors of 4 are 1, 2, and 4. Their sum is 1 + 2 + 4 = 7.

Now let's check if the property holds:

σ(3) * σ(4) = 4 * 7 = 28

It works! σ(12) = σ(3) * σ(4). This property is incredibly useful because it allows us to find σ(n) by first finding the prime factorization of n. If n = p₁^a₁ * p₂^a₂ * ..., then σ(n) = σ(p₁^a₁) * σ(p₂^a₂) * ....

---

Deconstructing the Argument

Now, let's walk through the author's logic for finding the non-square numbers n where σ(n) is prime. The goal is to eliminate all possibilities until only one remains.

Part 1: When is σ(n) an odd number?

The author starts with the fact that σ(n) is almost always even. For σ(n) to be a prime number (other than 2), it must be an odd prime. So, when is σ(n) odd?

σ(n) is odd only if all the factors in its prime decomposition, σ(p₁^a₁), σ(p₂^a₂), ..., are also odd.

• For powers of 2 (p=2): σ(2^a) = 1 + 2 + 4 + ... + 2^a = 2^(a+1) - 1. This sum is always odd. (e.g., σ(4) = 7, σ(8) = 15).⁶

• For powers of an odd prime (p is odd): σ(p^a) = 1 + p + p² + ... + p^a. This sum of numbers is odd only if there is an odd number of terms. The number of terms is a+1. For a+1 to be odd, a must be even.

So, for σ(n) to be odd, any odd prime factor in n must have an even exponent. This means n must be of the form:

n = 2^k * (an odd number that is a perfect square)

This leads to two cases:

1. k is even: n is a perfect square (e.g., 2² * 3² = 6²).

2. k is odd: n is twice a perfect square (e.g., 2³ * 5² = 2 * (2*5)² = 2 * 10²).

The author states: σ(n) is odd only when n is a square or twice a square. This is the conclusion. Since we are looking for non-square values of n, this immediately tells us we only need to check numbers that are twice a square.

Part 2: Analyzing n as "Twice a Square"

We've narrowed our search to n = 2k². The author now splits this into two sub-cases based on whether k is odd or even.

• Case A: n is twice an odd square. (n = 2 * m², where m is odd).

  Since 2 and m² are coprime, we can use the multiplicative property:

  σ(n) = σ(2 * m²) = σ(2) * σ(m²) = 3 * σ(m²)

  For this result (3 * σ(m²)) to be a prime number, it must be equal to 3. This is only possible if σ(m²) = 1. The only number whose sum of divisors is 1 is the number 1 itself. So m² = 1, which means m = 1.

  This gives us our first candidate: n = 2 * 1² = 2.

  Let's check: σ(2) = 1 + 2 = 3, which is a prime number. And n=2 is not a square. So, 2 is a solution.

• Case B: n is twice an even square. (n = 2 * m², where m is even).

  Let the even number m = 2^j * s, where s is an odd number and j ≥ 1.

  Then n = 2 * (2^j * s)² = 2 * 2^(2j) * s² = 2^(2j+1) * s².

  This n is composed of an odd power of 2 (2^(2j+1)) and an odd square (s²). These two parts are coprime.

  σ(n) = σ(2^(2j+1)) * σ(s²)

  As we established, both σ(power of 2) and σ(odd square) are odd numbers greater than 1 (assuming s > 1). When you multiply two integers that are both greater than 1, the result is a composite (non-prime) number.

  Therefore, for σ(n) to have any chance of being prime, the s² part must not exist. This means s must be 1.

Part 3: The Final Elimination

The previous step forces us to conclude that the only possible candidates left are when s=1. This means n must be an odd power of 2.

n = 2^(2m+1) for m ≥ 0.

Let's find the sigma of this number:

σ(n) = σ(2^(2m+1)) = 2^((2m+1)+1) - 1 = 2^(2m+2) - 1

The author then uses a standard algebraic factorization for a difference of squares (a² - b² = (a-b)(a+b)):

2^(2m+2) - 1 = (2^(m+1))² - 1² = (2^(m+1) - 1) * (2^(m+1) + 1)

For this product to be a prime number, one of its factors must be equal to 1.

• The second factor, (2^(m+1) + 1), is clearly larger than 1.

• Therefore, the first factor must be 1:

  2^(m+1) - 1 = 1

  2^(m+1) = 2

  m+1 = 1

  m = 0

Plugging m=0 back into our formula for n:

n = 2^(2*0 + 1) = 2¹ = 2.

This confirms that the only possible candidate that survived this entire process of elimination is the number 2.

Summary

The author brilliantly uses the multiplicative nature of σ(n) to prove that 2 is the only non-square number whose sum of divisors is a prime number. 

I'm not sure I'm any the wiser but we definitely all such numbers are squares!

Anyway, by contrast, numbers for which the sum of the \( \textbf{proper}\) divisors is prime are far more common. There are 3771 of them in the range up to 40000.