The Euler Polynomial

I've made mention of the Euler polynomial \(n^2+n+41\) before in a post titled Prime Producing Linear Polynomials back in August 28th 2018, that contained the snippet shown in Figure 1. This polynomial is quadratic and not linear of course.

Figure 1

I was reminded of this polynomial again today because my diurnal age of 26447 days featured in OEIS A228183:

A228183

Semiprimes generated by the Euler polynomial \(n^2 + n + 41\).

The sequence runs:

1681, 1763, 2021, 2491, 3233, 4331, 5893, 6683, 6847, 7181, 7697, 8051, 8413, 9353, 10547, 10961, 12031, 13847, 14803, 15047, 15293, 16043, 16297, 17071, 18673, 19223, 19781, 20633, 21797, 24221, 25481, 26123, 26447, ...

This reminded me that the Euler polynomial is not only an excellent producer of primes, at least initially, but also an excellent generator of semiprimes. Up until \(n=420\), the polynomial produces only primes and semiprimes: 280 primes and 138 semiprimes or 67% and 33%. This ratio is very close to 2/3 and 1/3 and so primes are produced twice as often as semiprimes. In this range, it should be noted that \(n=40\) produces 1681 which is \(41^2\) and thus not technically a semiprime because both factors are the same.

If we extend our range to one million, these percentages alter significantly. We find that there are 261080 primes and 458947 semiprimes and thus primes constitute 26.1% while semiprimes constitute 45.9%. About 28% of the numbers generated clearly have three or more factors and, as mentioned earlier, the run of primes and semiprimes stops with \(n=420) because here we encounter the first sphenic number, that is a number with three distinct prime factors. See Figure 2.

Figure 2

Looking at Figure 2, it can be seen that while the primes and semiprimes still abound, the first two sphenic numbers make their appearance when \(n=420\) and \(n=431\). In fact, up to \( n=1000\), there are only 22 sphenic numbers. See Figure 3.

Figure 3

The first number with four distinct prime factors occurs with \(n=2911\) where the generated number of 8476873 = 41 x 47 x 53 x 83. In the range up to 10,000, there are only 21 such numbers. See Figure 4.

Figure 4

The first number with five distinct prime factors does not occur until \(n=38913\) where the generated number 1514260523 = 43 x 47 x 61 x 71 x 173. In the range up to 100,000, there are only 18 such numbers. See Figure 5.

Figure 5

The first number with six distinct prime factors does not occur until \(n=707864\) generates the number 501072150401 = 41 x 43 x 47 x 53 x 71 x 1607. In the range up to one million, there are only five such numbers. See Figure 6.

Figure 6

Up to one million, there is a total of 6627 numbers containing squares e.g. for \(n=999786\), the number generated is 999573045623 = 47 x 47  x 97 x 4664951. These sorts of numbers constitute only 0.6627% of the total. 

In the range up to 100,000, the breakdown is as follows (permalink):

• 31984 prime numbers
• 47937 semiprimes
• 17741 sphenic numbers
• 1661 numbers with four distinct prime factors
• 18 numbers with five distinct prime factors
• 659 numbers that are not square free.

Figure 7 compares these 100,000 numbers which range from \(43\) to \(100000^2+100000+41\) to the first 100,000 numbers which is perhaps not entirely fair but it does provide some basis for comparison. The striking difference in the proportions of numbers containing squares is clearly evident.

Figure 7

As can be seen in Figure 7, the Euler polynomial does a great job in churning out primes and semiprimes.

Random Walks

Suppose an ant starts at the origin or (0,0) in the Cartesian coordinate system and moves one unit at a time upwards or sideways but only to the right. This binary choice is made randomly. Figure 1 illustrates the situation and shows that the ant will end up after three moves at either P, Q, R or S.

Figure 1

Suppose a boundary is imposed beyond with the ant cannot proceed. This boundary is marked by the lines \(x=100\) and \(y=100\). If the ant reaches this boundary, its motion stops. In effect, the ant's path is confined to 100 x 100 grid of squares. The four central squares are (50, 50), (50, 51), (51, 50) and (51, 51). The ant's movement also stops if it reaches any of these central squares. With its current movement constraints, it can only reach the first three of these central squares.

I thought that I'd write a program in SageMath to simulate the ant's journey whose path will terminate either at the boundary or at one of the four central squares. Figure 2 shows a journey at ends at the boundary.

Figure 2: permalink

Figure 3 shows a journey that ends at one of the four central squares.

Figure 3: permalink

It's easy enough to modify the program that different restraints are imposed on the ant's movements. For example, as well as moving upwards or to the right, it could also be allowed to move diagonally upwards. The resulting motion is similar but tends to drive it more toward the line \(y=x\) as shown in Figures 4 and 5 where the path reaches the boundary and the central squares respectively.

Figure 4: permalink

Figure 5: permalink

My simple programming activity was stimulated by watching a YouTube video that simulated lightning strikes and was more complex and written in Mathematica.

It is interesting to explore the probability that the ant will be stopped in the centre of the grid. Over 10,000 trials, I found that when the ant has three possible movements (up, right and diagonally up), the likelihood of being stopped in the centre is a little under 8.5% and never below 8% in my testing. Permalink. When only up and right movement is allowed, the likelihood is definitely lower with percentages ranging a little above and a little below 8%. Permalink.

It's interesting to experiment with different types of movements. An example is a restricted knight move where the ant can move two up and one to the right or one up and two to the right. Figures 6 and 7 show examples of the two possible paths. The likelihood of the ant's journey being stopped in the centre is fairly tightly centred on 8%.

Figure 6: permalink

Figure 7: permalink

There's plenty of scope for further experimentation but I'd best leave off there.

Recursion involving the Divisor Function

Interesting results arise when we consider the following iterative process involving a starting number \(n\):$$ \begin{align} n&=\frac{n}{\sigma(n,0)} \text{    if } n \equiv 0  \! \! \! \mod \sigma(n,0)\\ n&=n+\sigma(n,0) \text{    if } n \not \equiv 0 \! \! \! \mod \sigma(n,0) \end{align}$$This has the effect of quickly reducing the size of the number when it is divisible by the number of its divisors and increasing the number slightly in the case where it is not divisible before trying again.

Let's consider what happens to the number 42 under this recursive process:

• 42 has 8 divisors [1, 2, 3, 6, 7, 14, 21, 42]
  42 isn't divisible by 8, so 42 --> 42 + 8 = 50
  
  
• 50 has 6 divisors [1, 2, 5, 10, 25, 50]
  50 isn't divisible by 6 so 50 --> 50 + 6 = 56
  
  
• 56 has 8 divisors [1, 2, 4, 7, 8, 14, 28, 56]
  8 does divide into 56 to give 7
  
  
• 7 has 2 divisors [1, 7]
  7 isn't divisible by 2 so 7 --> 7 + 2 = 9
  
  
• 9 has 3 divisors [1, 3, 9]
  3 does divide into 9 to give 3
  
  
• 3 has 2 divisors [1, 3]
  3 isn't divisible by 2 so 3 --> 3 + 2 = 5
  
  
• 5 has 2 divisors [1, 5]
  5 isn't divisible by 2 and so 5 --> 5 + 2 = 7

Thus the trajectory of 42 ends in a loop because 5 takes us back to 7. The trajectory is thus 42, 50, 56, 7, 9, 3, 5. All trajectories end in this loop as far as I can determine. In this case, the number of steps is 6 and the trajectory has 7 members when including the starting number.

As usual, it's interesting to look for those numbers that have trajectories of record length. What I found in the range up to 30,000 was the following (SageMathCell permalink):

1, 2, 3, 4, 6, 11, 27, 216, 224, 227, 425, 815, 1641, 13244, 19305, 19317 

These numbers corresponded to trajectories of the following lengths:

1, 2, 4, 5, 8, 16, 75, 77, 78, 105, 275, 282, 951, 952, 1393, 1396

Figure 1 shows these results in tabular format. 

Figure 1

What's surprising is that a relatively small number like 19317 can have a trajectory length of 1396. It's interesting to look at the trajectory of this number. Figure 2 is a plot of the trajectory lengths.

Figure 2

Looking at Figure 2, we see how there is steady buildup until a number (27252) that is divisible by its number of divisors (18) and then there is a precipitous drop to 1514 and the same process is repeated on a smaller scale for what looks like two more times. 

We can see the same process at work a little more clearly for 27 that has a record length of 75. See Figure 3.

Figure 3

Here is the full trajectory of 27 that ends in the 7, 9, 3, 5 loop:

27, 31, 33, 37, 39, 43, 45, 51, 55, 59, 61, 63, 69, 73, 75, 81, 86, 90, 102, 110, 118, 122, 126, 138, 146, 150, 162, 172, 178, 182, 190, 198, 210, 226, 230, 238, 246, 254, 258, 266, 274, 278, 282, 290, 298, 302, 306, 318, 326, 330, 346, 350, 362, 366, 374, 382, 386, 390, 406, 414, 426, 434, 442, 450, 25, 28, 34, 38, 42, 50, 56, 7, 9, 3, 5

Polydivisible or Magic Numbers

Today I turned 26440 days old and discovered a new type of number, one termed polydivisible or magic. Here is a definition from Wikipedia:

In mathematics a polydivisible number (or magic number) is a number in a given number base with digits \(abcde \dots \) that has the following properties:

• Its first digit \(a\) is not 0.
• The number formed by its first two digits \(ab\) is a multiple of 2.
• The number formed by its first three digits \(abc\) is a multiple of 3.
• The number formed by its first four digits \(abcd\) is a multiple of 4.
• etc.

To put it in formal mathematical terms, we have:

Let \(n\) be a natural number, and let \(k = \lfloor \log_{b}{n} \rfloor + 1\) be the number of digits in \(n\) written in base \(b\). The number \(n\) is a polydivisible number if for all \(0 \leq i < k\):$$\frac{n - (n \bmod b^{k - i - 1})}{b^{k - i - 1}} \equiv 0 \pmod i$$Using the initiall less formal, definition it can be seen that 26440 qualifies because:

• the first digit 2 is not 0
• the number formed by its first two digits 26 is a multiple of 2
• the number formed by its first three digits 264 is a multiple of 3
• the number formed by its first four digits 2644 is a multiple of 4
• the number formed by its first five digits 26440 is a multiple of 5

The polydivisible numbers in base 10 form OEIS A144688 and though defined differently, it amounts to the same thing:

A144688

"Magic" numbers: all numbers from 0 to 9 are magic; a number >= 10 is magic if it is divisible by the number of its digits and the number obtained by deleting the final digit is also magic.

The OEIS comments tell us that there are exactly 20457 terms, the largest of which is the 25-digit number 3608528850368400786036725. For any given base \(b\), there are only a finite number of polydivisible numbers. After 26440, the next polydivisible number is 26445 followed by 26480, 26485 and then a relatively large gap to 26720. In the range up to 26440, about 2.7% of numbers are polydivisible.

Figure 1 shows the distribution of the number of polydivisible numbers with \(n\) digits. These numbers form OEIS A143671.

Figure 1: permalink

From Wikipedia we learn that:

Polydivisible numbers represent a generalisation of the following well-known problem in recreational mathematics:

Arrange the digits 1 to 9 in order so that the first two digits form a multiple of 2, the first three digits form a multiple of 3, the first four digits form a multiple of 4 etc. and finally the entire number is a multiple of 9.

The solution to the problem is a nine-digit polydivisible number with the additional condition that it contains the digits 1 to 9 exactly once each. There are 2,492 nine-digit polydivisible numbers, but the only one that satisfies the additional condition is:

381 654 729

Numberphile made a video about this polydivisible number.

Wikipedia also list the following problems associated with polydivisible numbers:

• Finding polydivisible numbers with additional restrictions on the digits - for example, the longest polydivisible number that only uses even digits is 48000688208466084040.
  
  
• Finding palindromic polydivisible numbers e.g. the longest palindromic polydivisible number is 30000600003.
  
  
• A common, trivial extension of the aforementioned example is to arrange the digits 0 to 9 to make a 10 digit number in the same way, the result is 3816547290. This is a pandigital polydivisible number that includes 0.

Recursion involving the Totient Function

With plenty of time on my hands and my mind being lately obsessed with recursive processes, I contemplated what might happen if I took a number and added its totient plus one to it, repeating the process with the new number and only terminating when a prime number was reached. Put mathematically and applied to a number \(n\), we have:$$n \rightarrow n+\phi(n)+1$$The first thing to realise is that for any prime number \(p\), this process will yield:$$p \rightarrow p+\phi(p)+1=p+p-1+1=2p$$and so any prime is initially doubled by this process. Remember the totient \( \phi(n) \) of \(n\) is the number of coprime integers less than \(n\), including 1.

Using SageMathCell, I was able to quickly determine the trajectories for all numbers up to 6000  and the distribution is shown in Figure 1. The vertical axis shows the trajectory length while the horizontal axis shows the number. Some of the record trajectories are shown in Figure 1 as well e.g. (97, 152) indicates that the number 97 sets a new trajectory record length of 152.

Figure 1: permalink

Below are shown the numbers that produce trajectories of record length, together with those lengths:

•       1  has a trajectory of record length      1
•       2  has a trajectory of record length      2
•       3  has a trajectory of record length      8
•     31  has a trajectory of record length     10
•     42  has a trajectory of record length     31
•     97  has a trajectory of record length   152
•  1907  has a trajectory of record length   166
•  2130  has a trajectory of record length   217
•  3067  has a trajectory of record length   224
•  5243  has a trajectory of record length   232
•  7355  has a trajectory of record length   302
•  7604  has a trajectory of record length   307
• 10956 has a trajectory of record length >344

SageMathCell timed out for 10956 because the composite numbers were becoming unwieldingly large. See Figure 2.

Figure 2

The final number is the list shown in Figure 2 is:

128273423043384555138014803867139463949464184741011497767099217473602278 

It was at this point that SageMathCell gave up. Presumably the trajectory of 10956 does terminate but so far I've not been able to determine its exact length, although we know it's larger than 344. The average number of iterations is slightly over 14 in the range up to 6000.

I may have more to add on this recursive process at a later date.

Analysis of a Recursive Process

Today I turned 26438 days old and one of the properties of this number is that it's a member of OEIS A048128:

A048128

Becomes prime or 4 after exactly 6 iterations of f(x) = sum of prime factors of x.

Approximately 10.7% of the numbers in the range up to 26438 satisfy this criterion. The sum of the prime factors is calculated with multiplicity. I was encouraged to investigate how this percentage changed as the number of iterations decreased and increased from six. I decided to increase the range up to 100,000. In this range, the percentage increases to 12.63%. Here is a permalink to the algorithm that I developed in SageMathCell to calculate these percentages.

The results for the various iterations were as follows:

• 0:   09.59%
• 1:   12.29%
• 2:   15.21%
• 3:   15.24%
• 4:   13.44%
• 5:   15.31%
• 6:   12.63%
• 7:   04.89%
• 8:   01.18%
• 9:   00.21%
• 10: 0.020%
• 11: 0.020%

No number between 1 and 100,000 survives 12 iterations. Only two numbers survive 11 iterations and these are 27933 and 55694. Let's look at the trajectory of these two numbers. 

• 27933, 9314, 4659, 1556, 393, 134, 69, 26, 15, 8, 6, 5
• 55694, 27849, 9286, 4645, 934, 469, 74, 39, 16, 8, 6, 5

As can be seen, both end in the prime number 5. The key to 55694's longevity is its repeated factorisation into biprimes with one small and one large factor. These are the factorisations:

• 55694 = 2 * 27847
• 27849 = 3 * 9283
• 9286 = 2 * 4643
• 4645 = 5 * 929
• 934 = 2 * 467
• 469 = 7 * 67
• 74 = 2 * 37
• 39 = 3 * 13
• 16 = 2 * 2 * 2 * 2
• 8 = 2 * 2 * 2
• 6 = 2 * 3
• 5 is prime

Here is a permalink to an algorithm that will calculate the trajectory of any number under this recursive process. Figure 1 shows a graph of the trajectory of 55694.

Figure 1

How do things change when we consider only the prime factor without multiplicity? Here are the results:

• 0:   09.59%
• 1:   11.81%
• 2:   14.78%
• 3:   26.51%
• 4:   21.27%
• 5:   11.08%
• 6:   3.955%
• 7:   0.899%
• 8:   0.093%
• 9:   0.006%
• 10: 0.000%
• 11: 0.000%

Because the sum of the prime factors without multiplicity is always equal to or smaller than the sum with multiplicity, the numbers will in general reach 4 or a prime more quickly.

More About 366

My previous post was about Compositions of 365 and 366 but just tonight, while playing around with numbers, I came across an interesting property of the number 366. It started out by considering a variation on my odds and evens algorithm that I've written about extensively in previous posts. In that algorithm, starting with any number, the odd digits of the number are added to it and the even digits subtracted to form a new number (unless the odd and even digits cancel out). This process is continued with the new number until a fixed point is reached or a loop is entered.

I thought about what would happen if the product of the digits of a number were added to the number to form a new number and the process repeated until some sort of resolution was reached. The process will clearly terminate once a zero digit appears. I wondered how many repetitions might be required. My investigations of the first 1000 numbers revealed that the maximum number of repetitions was 27 and this occurred with three numbers: 187, 248 and 264.

Here are their trajectories:

187, 243, 267, 351, 366, 474, 586, 826, 922, 958, 1318, 1342, 1366, 1474, 1586, 1826, 1922, 1958, 2318, 2366, 2582, 2742, 2854, 3174, 3258, 3498, 4362, 4506

248, 312, 318, 342, 366, 474, 586, 826, 922, 958, 1318, 1342, 1366, 1474, 1586, 1826, 1922, 1958, 2318, 2366, 2582, 2742, 2854, 3174, 3258, 3498, 4362, 4506

264, 312, 318, 342, 366, 474, 586, 826, 922, 958, 1318, 1342, 1366, 1474, 1586, 1826, 1922, 1958, 2318, 2366, 2582, 2742, 2854, 3174, 3258, 3498, 4362, 4506

Each sequence consists of 28 members and the members of the sequences are identical from 366 onwards. The sequences beginning with 264 and 248 differ only in the initial term but the trajectory of 187 does not meet up with them until 366 and the first four terms are odd (187, 243, 267, 351). After 23 steps, all leading to even numbers, 366 reaches a dead end.

Thus 366 forms a sequence consisting of 24 terms:

366, 474, 586, 826, 922, 958, 1318, 1342, 1366, 1474, 1586, 1826, 1922, 1958, 2318, 2366, 2582, 2742, 2854, 3174, 3258, 3498, 4362, 4506

366 is the first number to generate a sequence of length 24. Up to 1,000,000, the numbers that produce a sequence of this length are:

366, 393, 426, 442, 24567, 24627, 124567, 124627, 158637, 174219, 184441, 273867, 419976, 441136, 441232, 513411, 581746 

Six of the resulting sequences are subsets of the sequences containing 28 terms, described earlier. Getting back to the sequences of maximal length, the numbers up to ten million that lead to sequences of length 28 are:

187, 248, 264, 386776, 874423, 1386776, 3169526, 3175571, 3241862, 3795455, 3829475, 3843299, 4213657, 4241417, 4293567, 4322139, 4446651, 4449531, 4452571, 5113891, 5114811

Thus 187, 243, 248, 264, 267, 312, 318, 342, 351 all lead (directly or indirectly) to 366 on the way to 4506, under the add product of digits to number recursive process. See Figure 1.

Figure 1

Why the maximum length of the sequences should be 28 (consisting of 27 steps leading to a dead end) remains a mystery to me. There's clearly something of significance in the number 27 and maybe I'll dig deeper at a later date.