Powerful Numbers Revisited

It's been a long time, May 1st 2016 to be precise, since I wrote about powerful numbers. My post on that date was titled Achilles Numbers, Powerful Number and Perfect Powers. It wasn't a deep or lengthy post as Figure 1 demonstrates:

Figure 1

Today I turned 25947 days old and, in my investigation of this number, I was reminded once again of powerful numbers via Numbers Aplenty. Of this number, the site said:

It is a powerful number, because all its prime factors have an exponent greater than 1 and also an Achilles number because it is not a perfect power.

Clicking on the Numbers Aplenty link to powerful numbers, it says that:

In practice, the set of powerful numbers consists of the number 1 plus all numbers in whose factorisations the primes appears with exponents greater than 1. This set coincides with the set of numbers of the form \(a^2b^3\), for \(a,b \ge 1\). 

The powerful numbers up to 25947 are as follows:

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, 121, 125, 128, 144, 169, 196, 200, 216, 225, 243, 256, 288, 289, 324, 343, 361, 392, 400, 432, 441, 484, 500, 512, 529, 576, 625, 648, 675, 676, 729, 784, 800, 841, 864, 900, 961, 968, 972, 1000, 1024, 1089, 1125, 1152, 1156, 1225, 1296, 1323, 1331, 1352, 1369, 1372, 1444, 1521, 1568, 1600, 1681, 1728, 1764, 1800, 1849, 1936, 1944, 2000, 2025, 2048, 2116, 2187, 2197, 2209, 2304, 2312, 2401, 2500, 2592, 2601, 2700, 2704, 2744, 2809, 2888, 2916, 3025, 3087, 3125, 3136, 3200, 3249, 3267, 3364, 3375, 3456, 3481, 3528, 3600, 3721, 3844, 3872, 3888, 3969, 4000, 4096, 4225, 4232, 4356, 4489, 4500, 4563, 4608, 4624, 4761, 4900, 4913, 5000, 5041, 5184, 5292, 5324, 5329, 5400, 5408, 5476, 5488, 5625, 5776, 5832, 5929, 6075, 6084, 6125, 6241, 6272, 6400, 6561, 6724, 6728, 6859, 6889, 6912, 7056, 7200, 7225, 7396, 7569, 7688, 7744, 7776, 7803, 7921, 8000, 8100, 8192, 8281, 8464, 8575, 8649, 8712, 8748, 8788, 8836, 9000, 9025, 9216, 9248, 9261, 9409, 9604, 9747, 9800, 9801, 10000, 10125, 10201, 10368, 10404, 10584, 10609, 10648, 10800, 10816, 10952, 10976, 11025, 11236, 11449, 11552, 11664, 11881, 11907, 11979, 12100, 12167, 12168, 12321, 12348, 12500, 12544, 12769, 12800, 12996, 13068, 13225, 13448, 13456, 13500, 13689, 13824, 13924, 14112, 14161, 14283, 14400, 14641, 14792, 14884, 15125, 15129, 15376, 15488, 15552, 15625, 15876, 16000, 16129, 16200, 16384, 16641, 16807, 16875, 16900, 16928, 17161, 17424, 17496, 17576, 17672, 17689, 17956, 18000, 18225, 18252, 18432, 18496, 18769, 19044, 19208, 19321, 19600, 19652, 19683, 19773, 19881, 20000, 20164, 20449, 20736, 20808, 21025, 21125, 21168, 21296, 21316, 21600, 21609, 21632, 21904, 21952, 22201, 22472, 22500, 22707, 22801, 23104, 23328, 23409, 23716, 24025, 24200, 24300, 24336, 24389, 24500, 24649, 24696, 24964, 25000, 25088, 25281, 25600, 25921, 25947

Some powerful numbers are perfect powers because they can be expressed in the form \(m^k\) for \(m > 1\) and \(k>1\). An example is 9000 that can be expressed as \(30^2\). Powerful numbers that are not perfect powers are referred to as Achilles numbers and my number of the day (25947) is just such a number. This number has the special property that it of the form \(a^2b^3\) where \(a\) and \(b\) are both prime. Powerful numbers of this type form OEIS A143610:

A143610

Numbers of the form \(p^2 \times q^3\), where \(p\) and \(q\) are distinct primes.

Figure 2 shows the code that I wrote to generate this sequence is SageMathCell. There may well be more elegant ways to do this but this is what I came up with:

Figure 2: permalink

The sequence of numbers up to and including 25947 is:

72, 108, 200, 392, 500, 675, 968, 1125, 1323, 1352, 1372, 2312, 2888, 3087, 3267, 4232, 4563, 5324, 6125, 6728, 7688, 7803, 8575, 8788, 9747, 10952, 11979, 13448, 14283, 14792, 15125, 17672, 19652, 19773, 21125, 22472, 22707, 25947

Here is some further interesting information about powerful numbers, taken from Numbers Aplenty:

There are infinite pairs of consecutive powerful numbers, the smallest being (8, 9), but Erdös, Mollin, and Walsh conjectured that there are no three consecutive powerful numbers. 

Heath-Brown has shown in 1988 that every sufficiently large natural number is the sum of at most three powerful numbers. Probably the largest number which is not the sum of 3 powerful numbers is 119. 

The sum of the reciprocals of the powerful numbers converges to:$$ \frac{\zeta(2) \times \zeta(3)}{\zeta(6)} \approx  1.9435964 \dots $$Numbers Aplenty also has some interesting information about Achilles numbers.

There are infinite pairs of consecutive Achilles numbers, the smallest being: \(5425069447 = 7^3 \times 41^2 \times 97^2, 5425069448 = 2^3 \times 26041^2\) 

Actually, Richard B. Stanley has proved that each integer can be expressed in infinite ways as the difference of two coprime Achilles numbers. 

Every number greater that 2370 can be expressed as the sum of Achilles numbers. 

The smallest 3 × 3 magic square of Achilles numbers is shown in Figure 3:

Figure 3

The Achilles numbers, up to 25947, are:

72, 108, 200, 288, 392, 432, 500, 648, 675, 800, 864, 968, 972, 1125, 1152, 1323, 1352, 1372, 1568, 1800, 1944, 2000, 2312, 2592, 2700, 2888, 3087, 3200, 3267, 3456, 3528, 3872, 3888, 4000, 4232, 4500, 4563, 4608, 5000, 5292, 5324, 5400, 5408, 5488, 6075, 6125, 6272, 6728, 6912, 7200, 7688, 7803, 8575, 8712, 8748, 8788, 9000, 9248, 9747, 9800, 10125, 10368, 10584, 10800, 10952, 10976, 11552, 11907, 11979, 12168, 12348, 12500, 12800, 13068, 13448, 13500, 14112, 14283, 14792, 15125, 15488, 15552, 16000, 16200, 16875, 16928, 17496, 17672, 18000, 18252, 18432, 19208, 19652, 19773, 20000, 20808, 21125, 21168, 21296, 21600, 21632, 22472, 22707, 23328, 24200, 24300, 24500, 24696, 25000, 25088, 25947

In saying that "Every number greater that 2370 can be expressed as the sum of Achilles numbers", it should be borne in mind that some numbers may require as many as five Achilles numbers to be added together. For example, 3333 = 200 + 392 + 648 + 968 + 1125 without repetition of numbers or, with repetition allowed, the following:

72 + 200 + 968 + 968 + 1125 = 3333
72 + 392 + 392 + 1125 + 1352 = 3333
108 + 500 + 800 + 800 + 1125 = 3333

For 3333, the minimum number required is thus five but sums can be formed using more than this e.g. 72 + 200 + 392 + 392 + 1125 + 1152 = 3333.

The Doodle Problem

I came across the following problem on this site:

Can you make 100 by interspersing any number of pluses and minuses within the string of digits 9 8 7 6 5 4 3 2 1? You can't change the order of the digits! So what's the least number of pluses and minuses needed to make 100?

The originator of the problem called it a "doodle problem" because he felt it was "one that's best worked on during meetings where you might be doodling otherwise". It's easy enough to come up with a solution but not necessarily one that involves the least number of pluses and minuses. My solution was 9-8+76-5+4+3+21.

Referring to the originator's solution (link), he began:

A lot of trial and error is needed, and, although there are ways to help limit the set of possibilities, there isn’t a surefire method of arriving at a solution in a reasonable amount of time with a pen and paper. 

To start with, we might notice the first two digits make the number 98, which is quite close to 100. So, if we can add and subtract the rest of the single digits to make 2, then we’ll have 100. In fact, there are eight ways to do this: 

98 + 7 + 6 - 5 - 4 - 3 + 2 - 1 

98 + 7 - 6 + 5 - 4 + 3 - 2 - 1 

98 + 7 - 6 + 5 - 4 - 3 + 2 + 1 

98 + 7 - 6 - 5 + 4 + 3 - 2 + 1 

98 - 7 + 6 + 5 + 4 - 3 - 2 - 1 

98 - 7 + 6 + 5 - 4 + 3 - 2 + 1 

98 - 7 + 6 - 5 + 4 + 3 + 2 - 1 

98 - 7 - 6 + 5 + 4 + 3 + 2 + 1 

But we can do better—we can make 100 with fewer than 7 pluses and minuses. 

Here’s one way to make sure we find all possibilities: use a computer simulation. Each pair of digits can be connected by either nothing, a plus sign, or a minus sign. Since there are eight paired connections, there are \(3^8 = 6,561\) possible combinations of pluses and minuses. I simulated each one of these combinations to determine which sum to 100.

So at least my solution involved only six pluses and minuses but this may still not be the least number possible. I was intrigued at the prospect of a computer simulation using SageMathCell to find all possible solutions along with those that contained the minimum number possible. However, I haven't been able to figure out how to do this. I'll keep trying.

The originator succeeded with his computer simulation however, and came up with the following results:

The simulation unearthed that there are seven other ways of making 100: 

98 - 7 - 6 - 5 - 4 + 3 + 21 

9 + 8 + 76 + 5 + 4 - 3 + 2 - 1 

9 + 8 + 76 + 5 - 4 + 3 + 2 + 1 

9 - 8 + 76 + 54 - 32 + 1 

9 - 8 + 76 - 5 + 4 + 3 + 21 

9 - 8 + 7 + 65 - 4 + 32 - 1 

98 - 76 + 54 + 3 + 21 

The bolded solution is the winner. It uses only four pluses and minuses! 

The computer simulation also revealed that it’s possible to make every number from 1 to 100, which could keep you doodling for many meetings. In fact, it’s possible to make every number in more ways than one with one notable exception: 9 + 87 - 65 + 4 - 32 - 1 is the unique way to make 2.

This interesting little problem is similar to the selfie numbers that I posted about recently. The difference is that more operations than just addition and subtraction can be used in creating selfie numbers and the goal with them is always to recreate the original number. Here is a link to that post.

The abc Conjecture and Fermat's Last Theorem

An article appeared in Scientific American's website on April 3rd 2020 titled Mathematical Proof That Rocked Number Theory Will Be Published and which began:

Figure 1: Shinichi Mochizuki

After an eight-year struggle, embattled Japanese mathematician Shinichi Mochizuki has finally received some validation. His 600-page proof of the abc conjecture, one of the biggest open problems in number theory, has been accepted for publication. 

Acceptance of the work in Publications of the Research Institute for Mathematical Sciences (RIMS)—a journal of which Mochizuki is chief editor, published by the institute where he works at Kyoto University—is the latest development in a long and acrimonious controversy over the mathematicians’ proof. 

Two other RIMS mathematicians, Masaki Kashiwara and Akio Tamagawa, announced in Japanese the publication at a 3 April press conference in Kyoto. The paper “will have a big impact”, said Kashiwara. When asked how Mochizuki reacted to news of the paper’s acceptance, Kashiwara said, “I think he was relieved.” 

Mochizuki, who has denied requests for interviews over the years, did not appear and did not make himself available to reporters. 

Eight years ago, Mochizuki posted four massive papers online, claiming to have solved the abc conjecture. The work baffled mathematicians, who spent years trying to understand it. Then, in 2018, two highly respected mathematicians said they were confident that they had found a flaw in Mochizuki’s proof—something many saw as death blow to his claims. 

The latest announcement seems unlikely to move many researchers over to Mochizuki’s camp. “I think it is safe to say that there has not been much change in the community opinion since 2018,” says Kiran Kedlaya, a number theorist at the University of California, San Diego, who was among the experts who put considerable effort over several years trying to verify the proof. Another mathematician, Edward Frenkel of the University of California, Berkeley, says, “I will withhold my judgment on the publication of this work until it actually happens, as new information might emerge.”

The article goes on to describe the abc conjecture in these terms:

The ‘abc conjecture’, the problem Mochizuki claims to have solved, expresses a profound link between the addition and multiplication of integer numbers. Any integer can be factored into prime numbers, its ‘divisors’: for example, 60 = 5 x 3 x 2 x 2. The conjecture roughly states that if a lot of small primes divide two numbers \(a\) and \(b\), then only a few, large ones divide their sum, \(c\). 

Let's look at a different definition now, taken from Wikipedia:

Take three positive integers, \(a\), \(b\) and \(c\) (hence the name) that are relatively prime and satisfy \(a + b = c\). If \(d\) denotes the product of the distinct prime factors of \(a \times b \times c\), the conjecture essentially states that \(d\) is usually not much smaller than \(c\). In other words: if \(a\) and \(b\) are composed from large powers of primes, then \(c\) is usually not divisible by large powers of primes.

What's highlighted in red is essentially saying the same thing and provides an approach to proving Fermat's Last Theorem. To see this, let's look at \(a=13^{22}\) and \(b=11^{22}\) as an example. We know that Fermat's Last Theorem hopes to find a value for \(n>2\) such that:$$a^n+b^n=c^n \text{ for integer values of }a,b,c$$However, the \(abc\) conjecture indicates that for \(13^{22}+11^{22}\) this is highly unlikely. In fact, we have:$$13^{22}+11^{22}=2 \times 5 \times 29 \times 44617 \times 955769 \times 266300690657$$Here is another example:$$101^{19}+197^{19}=2 \times 149 \times 229 \times 1483 \times 110398608667213673 \times 3521300862956110103$$So from those two examples, one gets a glimpse of how a generalised approach using the \(abc\) conjecture might be used to provide a proof of Fermat's Last Theorem.

Of course, neither of the previous two definitions is a formal definition of the conjecture. We'll get to that shortly. In the meantime, here is a Numberphile video that appeared soon after Mochizuki's paper appeared:

In the video, the conjecture is described as follows where rad is the product of the distinct prime factors:

If \(a\) and \(b\) are coprime integers and \(a\)+\(b\)=\(c\) then (in general):$$ \text{rad}(abc)^k>c$$If \(k=1\) there are infinitely many exceptions.

If \(k>1\) there are finitely many exceptions.

He quotes \(3 + 125 =128\) as an example of an exception when \(k=1\). In this case, we have \( \text{rad}(3, 125, 128) = 3 \times 5 \times 2 = 30 < 128\). For the examples that I used earlier however, the opposite is the case. Figure 1 shows a SageMathCell screenshot for \(13^{22}+11^{22}\), with permalink included:

Figure 1: permalink

The definitions can get more technical than those quoted earlier but that's probably enough for now.

Recursive Prime Generating Sequences

If we multiply any number by 2 and add 1, the result is an odd number that may or may not be prime. For example, 2 * 3 + 1 = 7 which is prime but 2 * 3 * 4 + 1 = 25 is not prime. So starting with 2 and multiplying by the next number 3 yields a prime but multiplying by the next number 4 gives a composite number. So let's ignore the 4 and just work with 2 and 3. Now 2 * 3 * 5 + 1 = 31 which is prime. We now have 2, 3 and 5. Continuing on, we find that 2 * 3 * 5 * 6 + 1 = 181 which is prime. Now we have 2, 3, 5 and 6. However, 2 * 3 * 5 * 6 * 7 + 1 = 1261 = 13 * 97 and this is composite. If we continue this process up to 1000, including in our list only those numbers that multiply together to give a prime when 1 is added, we arrive at the following list:

2, 3, 5, 6, 9, 12, 16, 22, 25, 29, 31, 35, 47, 57, 61, 66, 79, 81, 108, 114, 148, 163, 172, 185, 198, 203, 205, 236, 265, 275, 282, 294, 312, 344, 359, 377, 397, 398, 411, 427, 431, 493, 512, 589, 647, 648, 660, 708, 719, 765, 887, 911, 916, 935

Figure 1 shows the SageMath algorithm to produce the list which forms part of OEIS A046966:

Figure 1: permalink

The primes resulting from this multiplication of numbers get large quickly as the following progression shows (OEIS A046972):

2, 3, 7, 31, 181, 1621, 19441, 311041, 6842881, 171072001, 4961088001, 153793728001, 5382780480001, 252990682560001, 14420468905920001, 879648603261120001, 58056807815233920001, 4586487817403479680001

Mathematically if S = {2, 3, 5, 6, 9, 12, 16, ... }, then the resulting primes can be represented as \( 1+\displaystyle \prod_{i=1}^n k_i \) where \(k_i \in \) S and \(k_1=2\), \(k_2=3\), \(k_3=5\) etc.

If we impose the condition that only primes will be used to generate primes, then a different set of numbers arise. Here are the first members of the set, made of primes below 1000: 2, 3, 5, 7, 11, 19, 29, 37, 47, 67, 103, 179, 191, 223, 271, 293, 317, 577, 643, 673, 809, 863 and 877. These numbers form a part of OEIS A039726. Figure 2 shows the modified SageMath code used to generate these numbers:

Figure 2: permalink

Mathematically if T = {2, 3, 5, 7, 11, 19, 29, ... } then the resulting primes can be represented as \( 1+\displaystyle \prod_{i=1}^n p_i \) where \(p_i  \in \) T and \(p_1=2\), \(p_2=3\), \(p_3=5\) etc.

Again the primes arising from this multiplication of primes get large quickly (OEIS A087864):

3, 7, 31, 211, 2311, 43891, 1272811, 47093971, 2213416591, 148298911531, 15274787887591, 2734187031878611, 522229723088814511, 116457228248805635731, 31559908855426327282831

These prime generating sequences provide an easy way to get a sequence of very large primes easily. I stumbled upon OEIS A039726 because 25933 is a member of that sequence and 25933 is the number of days old that I am today on my 71st birthday. Here is the full sequence of primes up to and including 25933:

2, 3, 5, 7, 11, 19, 29, 37, 47, 67, 103, 179, 191, 223, 271, 293, 317, 577, 643, 673, 809, 863, 877, 1049, 1093, 1129, 1151, 1381, 1613, 1637, 2089, 2131, 2311, 2957, 3623, 3833, 4253, 4271, 4423, 4673, 5939, 7717, 8167, 9133, 9533, 9539, 9679, 11059, 11743, 11969, 14759, 15859, 15971, 16139, 17431, 17713, 17761, 19309, 19373, 20747, 20983, 23741, 25261, 25933

 The prime resulting from multiplying 25933 by all the previous primes in the sequence is:

39245917564948194983835869291566473410857839336973406163917903204229432402730189405597557200354010052143063430004924215607042377998480357473041097452582168381147410469490307765855029111404711092751691679691