Mathematical Meanderings: July 2021

Tuesday 27 July 2021

Semiprimes that Approximate Whole Numbers

I've written about semiprimes on many occasions dating back to my earliest posts. These posts are:

Thus far however, I've not considered semiprimes that closely approximate whole numbers. However, today I turned 26413 days old and this number is a semiprime with prime factors of 61 and 433. If the smaller factor is divided into the larger, we get:$$\frac{433}{61} \approx 7.09836065573770$$This is fairly close to 7 but I thought I'd investigate the first one million natural numbers, using SageMathCell, to see which semiprimes yielded the closest approximations. I thought $ \pm 0.1$ was a fair distance limit to set and by this criterion 26413 just sneaks in. Figure 1 shows a table with the initial semiprimes that qualified, ranked in order of successively smaller differences between the ratio of prime factors and 7.

Figure 1: permalink to SageMathCell

What struck me as odd about this table is that 25681 and 26413 have identical differences with the ratio of the former being just below 7 and the latter just above. The reason for this becomes clear once we look at the average of these two numbers, 26047, and compare the factorisation of all three:$$ 25681 =61 \times 421\\26047=7 \times 61^2\\26413=61 \times 433$$Let's rewrite the factorisation of the average so that we have:$$ 25681 =61 \times 421\\26047=61 \times 427\\26413=61 \times 433$$Let's divide all three by $61^2$ to get:$$ \begin{align} \frac{25681}{61^2}&=\frac{421}{61}=7-\frac{6}{61}\\ \frac{26047}{61^2}&=7\\ \frac{26413}{61^2}&=\frac{433}{61}=7+\frac{6}{61} \end{align} $$Notice how $ \dfrac{6}{61} \approx 0.0983606557377049 <0.1$. Up to one million, there are the following such pairs of semiprimes that are equidistant from 7 because of the same mechanism. See Figure 2.

Figure 2: permalink to SageMathCell

Getting back to the closest approximations to 7, Figure 3 shows the top contenders. It can be seen that, generally speaking, the approximations get closer as the numbers get larger. We can surmise that for there exists semiprimes $p \times q $ with $p<q$ such that:$$ \lvert \frac{q}{p}-7 \rvert < \epsilon \text{ for any } \epsilon \text{ , no matter how small}$$

Figure 3: permalink to SageMathCell

So in the range up to one million, there are 307 semiprimes $p \times q $ that meet the criterion and they all fit in within the brackets as shown in Figure 4. Infinitely many such semiprime ratios can be fitted into the space between the brackets.

Figure 4

These calculations of course can be carried out for any number, not just 7, and the algorithm I developed in SageMath allows for the number to be changed. For example, Figure 5 shows the semiprimes in the range up to one million that approximate 11 most closely within the range $ \pm 0.1 $:

Figure 5: permalink to SageMathCell

Figure 6 shows that there are again pairs of semiprimes that are equidistant from 11, one above and one below:

Figure 6: permalink to SageMathCell

Let's look at the first row in Figure 6: 946097 and 942581 with an average of 944339. This will serve to give us practice in understanding why such pairs exist.$$ 946097 =293 \times 3229\\944339=11 \times 293^2\\942581=293 \times 3217$$Again rewrite the factorisation of the average so that we have:$$ 946097 =293 \times 3229\\944339=293 \times 3223\\942581=293 \times 3217$$Let's divide all three by $293^2$ to get:$$ \begin{align} \frac{946097}{293^2}&=\frac{3229}{293}=11+\frac{6}{293}\\ \frac{944339}{293^2}&=11\\ \frac{942581}{293^2}&=\frac{3217}{293}=11-\frac{6}{293} \end{align} $$Again we note that $ \dfrac{6}{293} \approx 0.0204778156996587 <0.1$.

Let's designate the whole number that we are interested in as $n$. So far we've looked at 7 and 11 as specific examples. In general, these semiprime pairs occur when there exists a multiple of $n$ of the form $n \times p^2$ where $p$ is a prime. This number can be written as $np \times p$. The two semiprimes, one above and one below, must contain this $p$ as one of their factors with the other factors being $ np-a $ and $ np+a $ respectively, where $a$ is some integer. Thus we have three numbers in arithmetic progression:$$p \times (np-a), np \times p,p \times (np+a)$$Dividing all terms by $p^2$ gives:$$n-\frac{a}{p}, \, n, \, n+\frac{a}{p}$$with $\dfrac{a}{p}$ needing to be less than an agreed size e.g. 0.1.

Monday 26 July 2021

St. Ives

As I was going to St. Ives,
I met a man with seven wives,
Each wife had seven sacks,
Each sack had seven cats,
Each cat had seven kits:
Kits, cats, sacks, and wives,
How many were there going to St. Ives?

The traditional understanding of this rhyme is that only one is going to St. Ives—the narrator. All of the others are coming from St. Ives. The trick is that the listener assumes that all of the others must be totalled up, forgetting that only the narrator is said to be going to St. Ives. If everyone mentioned in the riddle were bound for St. Ives, then the number would be 2,802: the narrator, the man and his seven wives, 49 sacks, 343 cats, and 2,401 kits. Wikipedia.

The progression 7, 49, 343 and 2401 corresponds to successive powers of seven: $7^1, 7^2, 7^3$ and $7^4$. The St. Ives rhyme came to mind because today I turned 26411 days old and this number has the interesting property that it can be written:$$26411=7 \times 7 \times 7 \times 77$$This property qualifies it for membership in OEIS A161145:

A161145

Numbers which can be expressed as the product of numbers made of only sevens.

The members of the sequence, up to 100,000 are:

1, 7, 49, 77, 343, 539, 777, 2401, 3773, 5439, 5929, 7777, 16807, 26411, 38073, 41503, 54439, 59829, 77777

Of course, 7 wives, 49 sacks, 343 cats and 2401 kittens make an appearance in this sequence along with 26411. Clearly, I won't be celebrating number 38073 as this corresponds to Sunday, June 29th 2053 when I would be 104 years old.

I devised a general purpose algorithm in SageMath that will generate not only the seven sequence but sequences for all digits between 2 and 9 inclusive. Here is its permalink. Applying this algorithm, I was able to generate the beginning members of OEIS A161140:

A161140

Numbers which can be expressed as the product of numbers made of only twos.

Unfortunately the calculation timed out for the range up to 100,000 so I needed to restrict the range to 30,000. The members up to that point are:

1, 2, 4, 8, 16, 22, 32, 44, 64, 88, 128, 176, 222, 256, 352, 444, 484, 512, 704, 888, 968, 1024, 1408, 1776, 1936, 2048, 2222, 2816, 3552, 3872, 4096, 4444, 4884, 5632, 7104, 7744, 8192, 8888, 9768, 10648, 11264, 14208, 15488, 16384, 17776, 19536, 21296, 22222, 22528, 28416

Let's take 28416 as an example:$$28416=2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 222$$Applying the algorithm so that all numbers are made up to threes generates OEIS A161141:

A161141

Numbers which can be expressed as the product of numbers made of only threes.

The members, up to 100,000, are:

1, 3, 9, 27, 33, 81, 99, 243, 297, 333, 729, 891, 999, 1089, 2187, 2673, 2997, 3267, 3333, 6561, 8019, 8991, 9801, 9999, 10989, 19683, 24057, 26973, 29403, 29997, 32967, 33333, 35937, 59049, 72171, 80919, 88209, 89991, 98901, 99999

Let's take 35937 as an example:$$35937=33 \times 33 \times 33$$Moving on to all fours (so to speak), we get OEIS A161142:

A161142

Numbers which can be expressed as the product of numbers made of only fours.

The members, up to 100,000, are:

1, 4, 16, 44, 64, 176, 256, 444, 704, 1024, 1776, 1936, 2816, 4096, 4444, 7104, 7744, 11264, 16384, 17776, 19536, 28416, 30976, 44444, 45056, 65536, 71104, 78144, 85184

Let's take 17776 as an example:$$17776=4 \times 4444$$Moving on again to all fives, we get OEIS A161143:

A161143

Numbers which can be expressed as the product of numbers made of only fives.

The members, up to 100,000, are:

1, 5, 25, 55, 125, 275, 555, 625, 1375, 2775, 3025, 3125, 5555, 6875, 13875, 15125, 15625, 27775, 30525, 34375, 55555, 69375, 75625, 78125

Let's take 34375 as an example:$$34375=5 \times 5 \times 5 \times 5 \times 55$$Moving on further to all sixes, we get OEIS A161144:

A161144

Numbers which can be expressed as the product of numbers made of only sixes.

The members up to 100,000, are:

1, 6, 36, 66, 216, 396, 666, 1296, 2376, 3996, 4356, 6666, 7776, 14256, 23976, 26136, 39996, 43956, 46656, 66666, 85536

Let's take 43956 as an example:$$43956=66 \times 666$$Moving on to all eights, we get OEIS A161146:

A161146

Numbers which can be expressed as the product of numbers made of only eights.

The members, up to 100,000, are:

1, 8, 64, 88, 512, 704, 888, 4096, 5632, 7104, 7744, 8888, 32768, 45056, 56832, 61952, 71104, 78144, 88888

Let's use 71104 as an example:$$71104=8 \times 8888$$Moving on to all nines, we get OEIS A161147:

A161147

Numbers which can be expressed as the product of numbers made of only nines.

The members, up to 100,000, are:

1, 9, 81, 99, 729, 891, 999, 6561, 8019, 8991, 9801, 9999, 59049, 72171, 80919, 88209, 89991, 98901, 99999

Let's use 59049 as an example:$$59049=9 \times 9 \times 9 \times 9 \times 9$$

Friday 23 July 2021

Pronic Pandigital Numbers and Beyond

My previous post on Pandigital Numbers Formed From Squares prompted me to investigate other ways of generating pandigital numbers. In July of 2018, I'd posted about Pandigital Numbers Formed From the Product of a Number and its Reversal. It occurred to me: why not consider pronic pandigital numbers. Pronic numbers are formed by multiplying two consecutive integers and are thus of the form $n(n+1) $ where $n$ is any integer.

Let's begin by considering what integers, when multiplied by the next consecutive integer, produce pandigital numbers with digits 1 to 9 occurring only once. It turns out that there are only 11 such numbers:

17846, 19403, 19727, 19871, 24768, 24776, 25568, 28521, 28556, 30878, 31203

Here is a permalink to a SageMath algorithm that will confirm this. This sequence of numbers does not appear in the OEIS and so it afforded me the opportunity to create a new sequence of my own.

S006: Integers $n$ such that the product of $n$ and $n+1$ produce pandigital

numbers in which the digits from 1 to 9 occur only once. These pandigital

numbers are pronic.

If zero is allowed, then there are 52 integers that, multiplied by the next consecutive integer, produce pandigital numbers in which the digits from 0 to 9 occur only once. These numbers are:

38627, 40508, 43065, 44027, 44576, 46565, 48735, 51714, 54269, 54459, 55151, 55152, 55331, 55403, 58454, 59579, 61497, 63072, 65465, 67580, 67662, 70154, 73737, 74906, 75662, 76203, 76337, 76760, 78011, 80631, 82809, 83015, 84555, 86076, 86553, 86688, 86769, 87669, 89064, 90198, 90423, 90909, 91943, 92169, 92268, 93356, 94464, 94617, 96362, 96570, 98702, 99270

Once again, this sequence of numbers does not occur in the OEIS and so I again seized the opportunity to create my own sequence:

S007: Integers $n$ such that the product of $n$ and $n+1$ produce

pandigital numbers in which the digits from 0 to 9 occur only once.

These pandigital numbers are pronic.

What about numbers of the form $n(n+1)(n+2)$? These are sphenic numbers consisting of three consecutive integers. It turns out that there are no such numbers if the digits are to range from 1 to 9. However, there are two such numbers if the digits from 0 to 9 are considered. These two numbers are 1267 and 1332. We find that:$$1267 \times 1268 \times 1269 = 2038719564\\1332 \times 1333 \times 1334 =2368591704$$Going a step further and considering numbers of the form $n(n+1)(n+2)(n+3)$, we find that only 291 satisfies in producing pandigital numbers with digits from 0 to 9:$$291 \times 292 \times 293 \times 294 =7319658024$$There are other variations on this theme. Consider numbers of the form $n \times \text{ prime}(n) $. Here we find there are two numbers that produce pandigital numbers with digits from 1 to 9: 5499 and 7569$$5499 \times \text{ prime}(5499)=5499 \times 53987=296874513\\7569 \times \text{ prime}(7569)=7569 \times 77017 =582941673$$If the digits are to range from 0 to 9, then we find that there are ten possible numbers viz.$$11376, 14562, 15057, 15723, 16659, 20421, 21330, 24867, 28494, 28746$$The corresponding pandigital numbers are respectively:$$1375028496,2308615794,2476108593,2714308659,3064572981,\\4692357801,5147632890,7094281563,9435702618,9612058734$$The fact that there are more than a couple of suitable numbers here justifies another sequence:

S008: Integers $n$ such that the product of $n$ and prime($n$) produce

pandigital numbers in which the digits from 0 to 9 occur only once.

Pandigital Numbers Formed From Squares

As the natural numbers become larger, it's more and more likely that they will contain all of the digits from 1 to 9 at least once. This is why the sequence of numbers containing all the digits from 1 to 9 is said to have an asymptotic density of 1. This is OEIS A294661:

A294661

Numbers whose square contains all of the digits 1 through 9.

The sequence begins:

11826, 12363, 12543, 14676, 15681, 15963, 18072, 19023, 19377, 19569, 19629, 20316, 22887, 23019, 23178, 23439, 24237, 24276, 24441, 24807, 25059, 25572, 25941, 26409, 26733, 27129, 27273, 29034, 29106, 30384, 32043, 32286, 33144, 34273, 35172, 35337, 35713, 35756, 35757, 35772, 35846, 35853, ...

I've marked the first thirty members of this sequence in blue because these numbers constitute OEIS A071519:

A071519

Numbers whose square is a zeroless pandigital number (i.e., use the digits 1 through 9 once).

Beyond 30384 (the 30th and last member of OEIS A071519), some of the digits occur more than once or a zero appears. For example: $$32043^2=1026753849 \text{ and a zero appears}$$There are 362,880 ways of arranging of the digits from 1 to 9 (factorial 9 or 9!). However, only 30 of the resulting numbers are perfect squares and these are listed in OEIS A071519. None of them are prime.

Numbermatics representation of 26409

Today my diurnal age is 26409 and this number is a member of OEIS A071519, which is what drew my attention to the number's property:

If we allow zero and consider possible permutations of the digits from 0 to 9, there are 3,265,920 possibilities (9 x 9!) but only 87 are perfect squares and again, none are prime. All are divisible by 9. These 87 numbers form OEIS A156977:

A156977

Numbers $n$ such that $n^2$ contains every decimal digit exactly once.

The numbers are:

32043, 32286, 33144, 35172, 35337, 35757, 35853, 37176, 37905, 38772, 39147, 39336, 40545, 42744, 43902, 44016, 45567, 45624, 46587, 48852, 49314, 49353, 50706, 53976, 54918, 55446, 55524, 55581, 55626, 56532, 57321, 58413, 58455, 58554, 59403, 60984, 61575, 61866, 62679, 62961, 63051, 63129, 65634, 65637, 66105, 66276, 67677, 68763, 68781, 69513, 71433, 72621, 75759, 76047, 76182, 77346, 78072, 78453, 80361, 80445, 81222, 81945, 83919, 84648, 85353, 85743, 85803, 86073, 87639, 88623, 89079, 89145, 89355, 89523, 90144, 90153, 90198, 91248, 91605, 92214, 94695, 95154, 96702, 97779, 98055, 98802, 99066

On July 9th 2018, I wrote about Pandigital Numbers Formed From the Product of a Number and its Reversal.

Sunday 18 July 2021

Free Fibonacci Sequences

On turning 26404 days, I couldn't help but notice the 404, a number made famous by the experience of everyone who has searched the Internet and failed to find what was being sought.

Apart from containing 404 as a subset of its digits, 26404 has some other interesting properties. Foremost amongst these is the fact that it is a member of OEIS A008892.

A008892

Aliquot sequence starting at 276.

I wrote about aliquot sequences in an eponymous post of December 20th 2017 and again, only recently, in Aliquot Sequences Revisited on June 21st 2021. 276 is the first of a sequence of numbers that are not known to be finite or periodic when the aliquot algorithm is applied. This algorithm takes as its input any integer $n$ and returns the sum of the number's aliquot parts or proper divisors, $ \sigma(n)-n$. This output serves as the new input and the process is repeated until, most commonly, a prime number $p$ is reached. Since $ \sigma(p)-p=1$, this means the process terminates because $ \sigma(1)=0$.

For some numbers, as far as can be determined, the process never terminates. These numbers include:

276, 306, 396, 552, 564, 660, 696, 780, 828, 888, 966, 996, 1074, 1086, 1098, 1104, 1134, 1218, 1302, 1314, 1320, 1338, 1350, 1356, 1392, 1398, 1410, 1464, 1476, 1488, ... and forming OEIS A131884

In the case of 276, the sequence of numbers up to and including 26404 is:

276, 396, 696, 1104, 1872, 3770, 3790, 3050, 2716, 2772, 5964, 10164, 19628, 19684, 22876, 26404

However, this post is mainly about another interesting property of 26404 and that is its membership of OEIS A232666:

A232666

6-free Fibonacci numbers.

The OEIS comment is that:

The sequences of $n$-free Fibonacci numbers were suggested by John H. Conway. $a(n)$ is the sum of the two previous terms divided by the largest possible power of 6. The sequence coincides with the Fibonacci sequence until the first multiple of 6 in the Fibonacci sequence: 144, which in this sequence is divided by 36 to produce 4.

The sequence of numbers leading to 26404 in OEIS A232666 is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 4, 93, 97, 190, 287, 477, 764, 1241, 2005, 541, 2546, 3087, 5633, 8720, 14353, 23073, 37426, 60499, 97925, 26404

Here is the permalink to the generation of this sequence. There is a paper titled Free Fibonacci Sequences by Brandon Avila and Tanya Khovanova that appears in the Journal of Integer Sequences (Vol. 17 (2014), Article 14.8.5) that analyses these sequences in some detail. The authors of the paper write:

Let us denote Fibonacci numbers by $F_k$. We define our indices such that $F_0 = 0$ and $F_1 = 1$. The sequence is defined by the Fibonacci recurrence: $F_{n+1} = F_n + F_{n−1} $ (see OEIS A000045). We call an integer sequence $a_n$ Fibonacci-like if it satisfies the Fibonacci recurrence: $a_k = a_{k−1} + a_{k−2}$. A Fibonacci-like sequence is similar to the Fibonacci sequence, except that it starts with any two integers. The second most famous Fibonacci-like sequence is the sequence of Lucas numbers $L_i$ that starts with $L_0 = 2$ and $L_1 = 1$: $2, 1, 3, 4, 7, 11, \dots $ (see OEIS A000032).

An $n$-free Fibonacci sequence starts with any two integers, $a_1$ and $a_2$, and is defined by the recurrence:$$a_k = \frac{a_{k−1} + a_{k−2}}{n^{ν_n(a_{k−1}+a_{k−2})}}$$where $ν_n(x)$ is the exponent of the largest power of $n$ that is a divisor of $x$. To continue the tradition, we call numbers in the $n$-free Fibonacci sequence that starts with $a_0 = 0$ and $a_1 = 1$ $n$-free Fibonacci numbers.

The authors then go on to look at a variety of $n$-free Fibonacci sequences. They start with 2-free Fibonacci sequences and find that they all end in a cycle of length 1. For example, starting with $a_0=5$ and $a_1=10$ gives:$$5, 10, 15, 25, 5, 15, \overbrace{5}, \dots$$For 3-free Fibonacci sequences, it is suspected that all end in a cycle of $k, k, 2k$ but it has not been proven. For example, starting with $a_0=3$ and $a_1=7$ gives:$$3, 7, 10, 17, 1, 2, \overbrace{1, 1, 2}, \dots$$with 1, 1, 2 repeating. Similarly, taking $a_0=13$ and $a_1=7$, the sequence generated is$$13, 7, 20, 1, 7, 8, 5, 13, 2, 5, 7, 4, 11, 5, 16, 7, 23, 10, 11, 7, 2, \overbrace{1, 1, 2} \dots$$ with 1, 1, 2 again repeating. The authors then go on to say that:

Consider the 4-free Fibonacci sequence starting with 0, 1. This sequence is OEIS A224382: 0, 1, 1, 2, 3, 5, 2, 7, 9, 1, 10, 11, 21, 2, 23, 25, .... It seems that this sequence grows and does not cycle. In checking many other 4-free Fibonacci sequences, we still did not find any cycles. The behaviour of 4-free sequences is completely different from the behaviour of 3-free sequences. For 3-free sequences, we expected that all of them cycle. Here, it might be possible that none of them cycles.

Let us look at the Lucas sequence mod 5: 2, 1, 3, 4, 2, 1, ... and see that no term is divisible by 5. Clearly, no term in the Lucas sequence will require that we factor out a power of 5, and the terms will grow indefinitely. Thus, the Lucas sequence is itself a 5-free Fibonacci sequence. On the other hand, it becomes quickly evident that the sequence of 5-free Fibonacci numbers: 0, 1, 1, 2, 3, 1, 4, 1, 1, 2, ... (see OEIS A214684) cycles. Some sequences cycle, and some clearly do not!

John Conway: 1937 - 2020

At the beginning of the paper, it's said that "John Horton Conway likes playing with the Fibonacci sequence. Instead of summing the two previous terms, he sums them up and then adds a twist: some additional operation." Of course, at that time, John Conway was still alive. He only died on April 11th 2020. That's a good way of thinking about the free Fibonacci sequences: Fibonacci with a twist!

I've posted frequently about Fibonacci sequences:

The Fibonacci Number Base on July 30th 2019
Fibonacci and Finance on April 15th 2019
Random Fibonacci Numbers on March 9th 2020
Dying Rabbits on June 26th 2021
Fibonacci-like Sequences on June 10th 2020
Finding Fibonacci and Tribonacci Seed Numbers on July 12th 2019
Beyond Fibonacci on March 10th 2019
Vishwanath Number on March 8th 2019
Goldbach's Conjecture and Zeckendorf's Theorem on November 15th 2015
Heptagonal Numbers on April 22nd 2019
Metallic Means on March 3rd 2019

The paper contains more detailed information but the takeaway is that there is plenty of scope for further investigation of Fibonacci-like sequences with a twist. Consider this "twist" on the tribonacci sequence with initial terms of 0, 1 and 2. Each successive term is the sum of the previous three terms but (and here's the twist), if the result is a composite number, replace the term with the composite number's highest prime factor. The first terms are:

0, 1, 2, 3, 3, 2, 2, 7, 11, 5, 23, 13, 41, 11, 13, 13, 37, 7, 19, 7, 11, 37, 11, 59, 107, 59, 5, 19, 83, 107, 19, 19, 29, 67, 23, 17, 107, 7, ...

So what's going on. Well, a plot of the first 400 terms reveals the story. See Figure 1.

Figure 1: permalink

This composite number to highest prime factor "twist" is just something that popped into my head and it instantly yielded a most interesting result: a quick spike and then settling into a cycle after 255 terms. Figure 2 shows the first 1000 terms and the cycles are evident.

Figure 2: permalink

The dramatic rise and fall of the terms and their settling into an endless loop, with its own dramatic peak, are unexpected but that is what happens.

Friday 16 July 2021

Kaprekar's Routine

I first encountered the algorithm that Wolfram MathWorld calls Kaprekar's Routine last year and actually made a post about it titled Birth Year Magic. I've created this post because I was reminded of the similarity between Kaprekar's Routine and the Odd-Even Algorithm that I've written about in a number of previous posts:

Dattaraya Ramchandra Kaprekar is something of an inspiration for me because our situations are similar academic-wise.

In Kaprekar's Routine, numbers get mapped to what are called fixed points (attractors in my terminology) or end up in loops (vortices in my terminology). Here is what Wolfram MathWorld has to say about the algorithm:

The Kaprekar routine is an algorithm discovered in 1949 by D. R. Kaprekar for 4-digit numbers, but which can be generalised to $k$-digit numbers. To apply the Kaprekar routine to a number $n$, arrange the digits in descending $ n^{'} $ and ascending $ n^{''} $ order. Now compute $ K(n)=n^{'}-n^{''} $ (discarding any initial 0s) and iterate, where $K(n)$ is sometimes called the Kaprekar function. The algorithm reaches 0 (a degenerate case), a constant, or a cycle, depending on the number of digits in $k$ and the value of $n$. The list of values is sometimes called a Kaprekar sequence, and the result K(n) is sometimes called a Kaprekar number (Deutsch and Goldman 2004), though this nomenclature should be deprecated because of confusing with the distinct sort of Kaprekar number.

In base-10, the numbers n for which $K(n)=n$ are given by 495, 6174, 549945, 631764, ... (OEIS A099009). Similarly, the numbers $n$ for which iterating $K(n)$ gives a cycle of length $k \geq 2$ are given by 53955, 59994, 61974, 62964, 63954, 71973, ... (OEIS A099010).

Iterating the Kaprekar map in base-10, all 1- and 2-digit numbers give 0. Exactly 60 3-digit numbers, namely 100, 101, 110, 111, 112, 121, 122, 211, 212, 221, ... (OEIS A090429), reach 0, while the rest give 495 in at most 6 iterations. Exactly 77 4-digit numbers, namely 1000, 1011, 1101, 1110, 1111, 1112, 1121, 1211, ... (OEIS A069746), reach 0, while the remainder give 6174 in at most 8 iterations. The value 6174 is sometimes known as Kaprekar's constant (Deutsch and Goldman 2004). This pattern breaks down for 5-digit numbers, which may converge to 0 or one of the 10 constants 53955, 59994, 61974, 62964, 63954, 71973, 74943, 75933, 82962, 83952.

I developed an SageMath algorithm (permalink) to determine the behaviour of numbers of any length over a given range. In my earlier post, my algorithms only applied to three and four digit numbers. Here is the behaviour for numbers in the range from 26400 to 26425:

26400 --> [26400, 63954, 61974, 82962, 75933, 63954]
26401 --> [26401, 62964, 71973, 83952, 74943, 62964]
26402 --> [26402, 61974, 82962, 75933, 63954, 61974]
26403 --> [26403, 61974, 82962, 75933, 63954, 61974]
26404 --> [26404, 61974, 82962, 75933, 63954, 61974]
26405 --> [26405, 62964, 71973, 83952, 74943, 62964]
26406 --> [26406, 63954, 61974, 82962, 75933, 63954]
26407 --> [26407, 73953, 63954, 61974, 82962, 75933, 63954]
26408 --> [26408, 83952, 74943, 62964, 71973, 83952]
26409 --> [26409, 93951, 85932, 74943, 62964, 71973, 83952, 74943]
26410 --> [26410, 62964, 71973, 83952, 74943, 62964]
26411 --> [26411, 52965, 70983, 94941, 84942, 73953, 63954, 61974, 82962, 75933, 63954]
26412 --> [26412, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26413 --> [26413, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26414 --> [26414, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26415 --> [26415, 52965, 70983, 94941, 84942, 73953, 63954, 61974, 82962, 75933, 63954]
26416 --> [26416, 53955, 59994, 53955]
26417 --> [26417, 63954, 61974, 82962, 75933, 63954]
26418 --> [26418, 73953, 63954, 61974, 82962, 75933, 63954]
26419 --> [26419, 83952, 74943, 62964, 71973, 83952]
26420 --> [26420, 61974, 82962, 75933, 63954, 61974]
26421 --> [26421, 51975, 81972, 85932, 74943, 62964, 71973, 83952, 74943]
26422 --> [26422, 41976, 82962, 75933, 63954, 61974, 82962]
26423 --> [26423, 41976, 82962, 75933, 63954, 61974, 82962]
26424 --> [26424, 41976, 82962, 75933, 63954, 61974, 82962]
26425 --> [26425, 42966, 71973, 83952, 74943, 62964, 71973]

All the numbers end in a loop of one type or another. Let's compare what happens to today's number (I'm 26402 days old) under the two different algorithms:

Kaprekar's Routine:

26402 --> [26402, 61974, 82962, 75933, 63954, 61974]
Odd Even Algorithm:

26402 -->[26402, 26388, 26367, 26363, 26355, 26360, 26349]

Kaprekar's Routine causes the number to end up in a loop [61974, 82962, 75933, 63954, 61974] while the Odd Even Algorithm leads to an attractor, or fixed point, 26349. Go back to my post Birth Year Magic to find out more about Kaprekar.

Wednesday 14 July 2021

Cut-the-Knot

In my previous post titled Four Fours Representation of 32, I made reference to a site called Cut-the-Knot. In this post, I'll look at the site more closely and I feel it certainly deserves closer attention. Here is what one reviewer wrote about the site.

The Web may contain almost every possible problem, puzzle, and article imaginable, but it’s decentralized nature makes it’s hard to locate good content in a sea of endless tutorials, amusing pictures, and commercial promotions. If you’re trying to find extracurricular mathematical materials you need to know where to look, but more importantly, what to look for. Knowing an erudite guide makes life much easier. Alexander Bogomolny, a professional mathematician and curator of mathematical recreations and other topics, is that guide. His site Cut-the-Knot is an enormous collection of fascinating articles, illustrations, and animations covering a wide range of mostly non-advanced mathematics. One of the defining features of his articles are the interactive Java applets that illustrate a problem or principle. The site has been continuously updated since 1997, which makes it among the most comprehensive such repositories online. Unfortunately, because it was created more than fifteen years ago, its age shows in the design and technology used (Java applets are no longer the preferred delivery mechanism for interactive media). Although Cut-the-Knot has garnered over twenty awards, including one from Scientific American, it is not as well known as it should be. If you’re looking for a source of enrichment for regular math classes this is one of the best places to start.

In this post, I'll just look at the first problem that occurs under the subject of Arithmetic and this is 100 Grasshoppers on a Triangular Board. Here is the problem statement:

A triangular board has been cut into 100 small triangular cells by the lines parallel to its sides. Two cells that share a side are said to be neighbours. In each cell there is a grasshopper. All at once, the grasshoppers hop from their cells to neighboring cells. This happens 9 times. Prove that at least 10 cells are now empty.

The solution is as follows:

The board is naturally coloured into two colours so that the neighbouring cells are coloured differently. Let the colours be red and brown and label the grasshoppers by the colour of their cells. Convince yourself that there are 55 red and 45 brown cells. In one hop, the brown grasshoppers move to the red cells thus emptying 55 cells. On the same hop, the brown grasshoppers move to the red cells thus filling at most 45 red cells. Inevitably, at least 10 red cells will remain empty.

The next time the grasshoppers move, they can move into their original cells, thus filling all of them. The situation will return to the original one, while the argument will apply to every odd hop. Perhaps there may happen a greater mix-up of the red and brown hoppers, but the best that may be claimed is that after every odd hop, there are at least 10 empty cells.

In general, there are $n(n+1)/2$ red cells and $n(n-1)/2$ brown cells. The difference being $n(n+1)/2 - n(n-1)/2 = n$, there are always at least $n$ empty cells after an odd number of hops.

The specific number of hops (9) is nothing but a red herring.

So, an interesting little problem, and of course this site is replete with many more, 244 in fact under the subject heading of Arithmetic. The subject headings are:

Arithmetic with 244 articles
Algebra with 1059 articles
Geometry with 1824 articles
Probability with 204 articles
Trigonometry with 36 (unnumbered) articles
Visual Illusions with 51 (unnumbered) articles

There is a glossary with more articles and links to many more. Unfortunately, the author of the site, Alex Bogomolny, died in 2018 at the age of 70 but he has left behind a treasure trove of mathematical information.

Dr. Alexander Bogomolny, May 2017
(In Costa Rica, holding a sloth)

Here is what his Wikipedia entry had to say:

Alexander Bogomolny (January 4, 1948 – July 7, 2018) was a Soviet-born Israeli American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Mathematics, senior instructor at Hebrew University and software consultant at Ben Gurion University. He wrote extensively about arithmetic, probability, algebra, geometry, trigonometry and mathematical games.

He was known for his contribution to heuristics and mathematics education, creating and maintaining the mathematically themed educational website Cut-the-Knot for the Mathematical Association of America (MAA) Online. He was a pioneer in mathematical education on the internet, having started Cut-the-Knot in October 1996.

Bogomolny attended Moscow school No. 444, for gifted children, then entered Moscow State University, where he graduated with a master's degree in mathematics in 1971.[3] From 1971 to 1974 he was a junior research fellow at the Moscow Institute of Electronics and Mathematics. He emigrated to Israel and became a senior programmer at Lake Kinneret Research Laboratory in Tiberias, Israel (1974 – 1977) and a software consultant at Ben Gurion University in Negev, Be’er Sheva, Israel (1976 – 1977). From 1976 to 1983 he was a Senior Instructor and researcher at Hebrew University in Jerusalem. He received his Ph.D. in mathematics at Hebrew University in 1981. His dissertation is titled, A New Numerical Solution for the Stamp Problem and his thesis advisor was Gregory I. Eskin. From 1981 to 1982 he was also a Visiting Professor at Ohio State University where he taught mathematics.

From 1982 to 1987 he was Professor of Mathematics at the University of Iowa. From August 1987 to August 1991 he was Vice President of Software Development at CompuDoc, Inc.

Cut-the-knot (CTK) was a free, advertisement-funded educational website which Bogomolny maintained from 1996 to 2018. It was devoted to popular exposition of various topics in mathematics. The site was designed for teachers, children and parents, and anyone else curious about mathematics, with an eye to educating, encouraging interest, and provoking curiosity. Its name is a reference to the legend of Alexander the Great's solution to the Gordian knot.

CTK won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003, the Encyclopædia Britannica's Internet Guide Award, and Science's NetWatch award.

The site was remarkably prolific and contained extensive analysis of many of the classic problems in recreational mathematics including the Apollonian gasket, Napoleon's theorem, logarithmic spirals, The Prisoner of Benda, the Pitot theorem, and the monkey and the coconuts problem. Once, in a remarkable tour de force, CTK published 122 proofs of the Pythagorean theorem.

Bogomolny did indeed entertain but his deeper goal was to educate. He wrote a manifesto for CTK in which he said that "Judging Mathematics by its pragmatic value is like judging symphony by the weight of its score."[11] He describes the site as "a resource that would help learn, if not math itself, then, at least, ways to appreciate its beauty." And he wonders why it is acceptable among otherwise well-educated people "to confess a dislike and misunderstanding of Mathematics as a whole."

Many mathematical ideas are illustrated by applets. CTK wiki (powered by PmWiki) extends the main site with additional mathematical content, especially that with more complicated formulae than available on the main site.

Bogomolny had to leave academia because he had an uncorrectable hearing problem and was practically deaf in latter years. He is survived by his wife Svetlana Bogomolny, two sons David (Israel) and Eli (USA) Bogomolny, and granddaughter Liorah Shaindel Bogomolny.

Tuesday 13 July 2021

Four Fours Representation of 32

Let's suppose that $n$, $x$ and $y$ are positive integers such that:$$n^{\, x+y}=x||y$$where $x||y$ represents the concatenation of $x$ and $y$. What values of $n$, $x$ and $y$ satisfy this equation? Well it seems that there is only one set of values, namely $n=2$, $x=3$ and $y=2$ where$$2^{3+2}=32$$This curious fact struck me when looking at the periodicity of conjunctions of Mars and Venus, that occur in almost the same location in the tropical zodiac at intervals 32 years (+0.5 to 4 days). See my post Periodicity of Mars-Venus Conjunctions.

This got me thinking about what other interesting properties the number 32 might possess. Naturally I turned to Numbers Aplenty to find out.

32 can be written using four fours as in $ (4+4)^{\! ^{\frac{\sqrt{\overline{.4}}}{.4}}} $ where:$$\sqrt{\overline{.4}}=\sqrt{\frac{4}{9}}=\frac{2}{3}\\\ \frac{\frac{2}{3}}{.4}=\frac{\frac{2}{3}}{\frac{2}{5}}=\frac{5}{3}\$4+4)^{\! ^{\frac{5}{3}}}=8^{\! ^{\frac{5}{3}}}=\left ( 2^3 \right )^{ \!\frac{5}{3}}=2^5=32$$Actually this is not a property unique to 32. In fact, all the numbers up 112 can be represented thus and 113 is the smallest natural number that cannot be obtained using four fours, the common arithmetic operations, factorial, roots, and the notations$$.4=0.4=\frac{2}{5} \text{ and }\overline{.4}=0.4444\dots=\frac{4}{9}$$The use of the vinculum or overline is potentially confusing because the symbol is also used for the rising factorial as in:$$4^{\overline{4}}=4 \times 5 \times 6 \times 7=840$$I've always used the overdot as in \( 0.\dot{4}=0.4444 \dots$ to represent the repeating decimal.

There are other ways to represent 32 using four fours:$$4!! \times 4 + 4 -4 = 32\\4^{\sqrt{4}}+4^{\sqrt{4}}=32\\4 \times 4+4 \times 4=32$$The use of the double factorial can be noted in the previous example, viz. 4!!= 4 x 2 = 8. When attempting the four fours representation, it needs to be made clear what's allowable. If the simple factorial is allowed (4!= 4 x 3 x 2 = 24), then it needs to be determined whether the double factorial (4!!=4 x2) and subfactorial (!4 = 9) are also permitted. I've written about the various types of factorials in my post Subfactorials, Semifactorials and Others. It's also in this post that I address the problem of representing 10 using three threes, which involves the use of the subfactorial (!3=2).

The key to solving these puzzles is the collect various building blocks. These might include (depending on what's allowed):

$\sqrt{4}=2$
$4!=24$
$4!!=12$
$4^{\overline{4}}=840$
$!4=9 $
$.\dot{4}=0.4444 \dots =4/9 $

Four fours is just one of a variety of mathematical puzzles that attempt to represent the counting numbers in terms of a fixed number of identical digits, according to certain prescribed rules. Here are links to a variety of representations:

Monday 12 July 2021

Digital Roots and Additive Persistence

To quote from my recent post titled SOD ET AL (Sum Of Digits And Other Things) on June 29th 2021:

DIGITAL ROOT
While I've not made a specific post about digital roots, I've nonetheless mentioned them in the following posts:
Heptagonal Numbers
Star Numbers
The Goldbach Conjecture and Lucky Numbers
An Unhappy Family
To quote from Wikipedia:
The digital root (also repeated digital sum) of a natural number in a given radix is the (single digit) value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. In base 10, this is equivalent to taking the remainder upon division by 9 (except when the digital root is 9, where the remainder upon division by 9 will be 0).
Associated with the digital root is the concept of additive persistence defined as:
The additive persistence counts how many times we must sum its digits to arrive at its digital root. For example, the additive persistence of 2718 in base 10 is 2: first we find that 2 + 7 + 1 + 8 = 18, then that 1 + 8 = 9.

Recently I had cause to visit digital roots again in the context of a new sequence that I devised in response to finding a meaningful OEIS sequence associated with the number 26396 which factorises to 2 * 2 * 6599 and that has prime factors of 2 and 6599. I noticed that both of these prime factors have a digital root of 2. This gave me the idea for the following sequence:

S003: Numbers with more than one prime factor such that the digital root of all prime factors is the same.

I developed an algorithm (permalink) to determine all such numbers up to 30,000 and it turned out that there are 1658 numbers in that range, constituting 6.29%. The members of the sequence below 1000 are:

22, 44, 58, 88, 94, 115, 116, 166, 176, 188, 202, 205, 232, 242, 274, 295, 301, 319, 332, 346, 352, 376, 382, 403, 404, 427, 454, 464, 484, 517, 526, 548, 553, 562, 565, 575, 634, 638, 655, 664, 679, 692, 703, 704, 706, 745, 752, 764, 778, 808, 835, 871, 886, 901, 908, 913, 922, 928, 943, 958, 968

It was a short step then to my next sequence where membership is a little more exclusive:

S004: Numbers with more than one prime factor such that the digital root

of all prime factors is the same as the digital root of the number itself.

Here is the permalink to the algorithm that I developed. It turns out that there are 106 numbers in the range up to 30,000 and these constitute 0.402 % of the range. Below 1000, there are only two numbers that satisfy this criterion and interestingly they form a pair.

703 = 19 * 37 where 19, 37 and 703 all have a digital root of 1 and 704 = 2^6 * 11 where 2, 11 and 704 all have a digital root of 2. In the range up to 30,000, there are two other pairs:

14527 and 14528
29503 and 29504

The 106 members of this sequence in the range up to 30,000 are:

[703, 704, 1387, 1856, 2071, 2413, 2701, 3008, 3097, 3439, 3781, 3872, 4033, 4699, 5149, 5312, 5833, 6031, 6464, 6697, 7201, 7363, 7543, 7957, 8227, 8768, 9253, 9271, 9937, 10027, 10208, 10279, 10963, 11072, 11359, 11647, 11899, 11989, 12224, 13213, 13357, 13843, 14023, 14041, 14383, 14527, 14528, 14689, 14749, 15317, 15409, 15751, 16021, 16544, 16777, 16832, 17461, 17767, 17803, 17984, 18019, 18829, 19171, 19351, 19729, 19783, 20017, 20197, 20288, 20519, 20701, 20923, 21223, 21296, 21349, 21691, 21907, 22249, 22411, 22592, 22681, 22987, 23347, 24301, 24643, 24896, 25273, 25721, 26011, 26353, 26912, 27037, 27097, 27343, 27667, 27721, 28009, 28352, 28981, 29089, 29216, 29431, 29503, 29504, 29539, 29773]

Figure 1 shows a plot of these numbers:

Figure 1

I'll make a note about additive persistence. The distribution from 0 to 30,000 is:

10 numbers have a digital persistence of 0 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
1531 have a digital persistence of 1
25292 have a digital persistence of 2
3168 have a digital persistence of 3

The smallest numbers to have persistences of 0, 1, 2 and 3 are 0, 10, 19 and 199 respectively. The first number with an additive persistence of 4 is 19999999999999999999999. Beyond that, the numbers are ridiculously large. Figure 2 shows the relative proportions:

Figure 2