Magic Cubes

I had a dream some nights ago in which I dreamt of the number 42. I hadn't been reading or thinking about The Hitchhiker's Guide to the Galaxy but I was prompted by the dream to investigate some of the properties of this number. As I discovered, it's a pronic number or a product of consecutive digits, in this case 6 and 7. It's also a partition number since it is equal to the number of partitions of 10. For information about its being the sum of three cubes, see this blog post of mine. The number is also associated with the 3 x 3 x 3 magic cube as shown in Figure 1:

Figure 1: dissection of a 3 x 3 x 3 magic cube
Source: https://mathematicscentre.com/taskcentre/174magic.htm

In such a cube, all the rows and columns in each of the three square "slices" shown in Figure 1 add to 42. It would be the same if we sliced in other similar ways. The long diagonals (19, 14, 9 for example) also add to 42 but the diagonals within the slices do not. Figure 2 shows another possible configuration:

Figure 2: source 

9 rows, such as 1 - 17 - 24, sum to 42.
9 columns, such as 1 - 15 - 26, sum to 42.
9 Pillars, such as 1 - 23 - 18, sum to 42.
4 triagonals, such as 26 - 14 - 2 sum to 42. 

Some of the squares may have diagonals summing to 42, but this is not a requirement. In fact, order-8 is the smallest cube for which it is possible for all the diagonals to sum correctly. 

What is required is that the 4 triagonals or 3-agonals, such as 1 - 14 - 27 sum to 42. 

There are four different basic pure (using numbers 1 to 27) magic cubes. Each of these have 48 equivalents due to rotations and/or reflections.

To quote from Wikipedia:

In mathematics, a magic cube is the 3-dimensional equivalent of a magic square, that is, a number of integers arranged in a \(n × n × n \) pattern such that the sums of the numbers on each row, on each column, on each pillar and on each of the four main space diagonals are equal to the same number, the so-called magic constant of the cube, denoted \(M_3(n)\). It can be shown that if a magic cube consists of the numbers \(1, 2, ..., n^3\), then it has magic constant (sequence A027441 in the OEIS):

$$
M_3(n) = \frac{n(n^3+1)}{2}
$$The OEIS sequence runs:

0, 1, 9, 42, 130, 315, 651, 1204, 2052, 3285, 5005, 7326, 10374, 14287, 19215, 25320, 32776, 41769, 52497, 65170, 80010, 97251, 117139, 139932, 165900, 195325, 228501, 265734, 307342, 353655, 405015, 461776, 524304, 592977, 668185, 750330, 839826, 937099

Of course, the formula above for 3 dimensions can be generalised to any number of dimensions. To quote again from Wikipedia:

In mathematics, a magic hypercube is the k-dimensional generalisation of magic squares, magic cubes and magic tesseracts; that is, a number of integers arranged in an \(n × n × n × ... × n\) pattern such that the sum of the numbers on each pillar (along any axis) as well as the main space diagonals is equal to a single number, the so-called magic constant of the hypercube, denoted \(M_k(n)\). It can be shown that if a magic hypercube consists of the numbers \(1, 2, ..., n^k\), then it has magic number: 

$$
M_k(n) = \frac{n(n^k+1)}{2}
$$For \(n=4\), the OEIS sequence A021003 is:

0, 1, 17, 123, 514, 1565, 3891, 8407, 16388, 29529, 50005, 80531, 124422, 185653, 268919, 379695, 524296, 709937, 944793, 1238059, 1600010, 2042061, 2576827, 3218183, 3981324, 4882825, 5940701, 7174467, 8605198, 10255589, 12150015

This whole topic leads in all sort of interesting directions but I'll have to leave off there and pursue some of these directions at another time.

Factoring Numbers Using Polynomials

Consider a number such as \(45\) and suppose we have no idea how to factor it. Let's convert \(45_{10}\) to its binary equivalent \(101101_2\). From this binary number, let's form a polynomial using the indices of the placeholder values \(2^5, 2^4, 2^3, 2^2, 2^1, 2^0\) as the indices of an associated polynomial, namely \(x^5 + x^3 + x^2 + 1\). This polynomial factorises as follows:$$

x^2(x^2+1)+1(x^2+1) = (x^2+1)(x^3+1) = (x+1)(x^2-x+1)(x^2+1)

$$If we now substitute \(x=2\), the result is 3 * 3 * 5 which are the prime factors of 45. Let's try another number, this time \(111\) that is \(1101111_2\) in binary form. The associated polynomial is \(x^6+x^5+x^3+x^2+x+1\) that factorises to the following:$$

x^5(x+1)+x^2(x+1)+1(x+1) = (x+1)(x^5+x^2+1)

$$Substituting \(x=2\) gives 3 * 37, the prime factors of \(111\).

The useful idea behind such a technique is that it can be applied to factor very large composite numbers. I came across the idea in a Quanta Magazine article titled: Mathematicians Seal Back Door to Breaking RSA Encryption. The article states:

This seems like a complicated way to find the prime factors of a small number like 15, whose factors are easy to spot straightaway. But with very large numbers — numbers with hundreds of digits — this polynomial method gives you a remarkable advantage. There’s no fast algorithm for factoring large numbers. But there are fast algorithms for factoring large polynomials. So once you convert your large number to a large polynomial, you’re very close to finding the number’s prime factors.

Does this mean RSA encryption is in trouble? Actually, no. The reason for this has to do with the new proof about polynomials. The mathematicians Emmanuel Breuillard and Péter Varjú of the University of Cambridge proved that as polynomials with only 0 and 1 as coefficients get longer, they’re less and less likely to be factorable at all. And if a polynomial can’t be factored, it can’t be used to identify the prime factors of the number it’s based on. 

Breuillard and Varjú’s proof effectively slams shut the polynomial back door for breaking RSA encryption. The very large numbers used in RSA encryption correspond to very long polynomials. Breuillard and Varjú proved that it’s nearly impossible to find polynomials of that length that can be factored. Mathematicians and cryptographers alike have long suspected this is the case. But when the cybersecurity of the entire world depends on some mathematical hack not working, it’s good to have proof that it doesn’t. 

Regardless of RSA encryption, the key point for me was the fact that every number can be represented as a unique polynomial. For example:

45 -->  \(x^5 + x^3 + x^2 + 1\) and 111 --> \(x^6+x^5+x^3+x^2+x+1\)

All such polynomials have coefficients that are either 0 or 1. This makes the factorisation, if possible, fairly straightforward as can be seen in examples chosen. Of course, a unique polynomial can be created in any base. In base 3:

45 --> \(x^3+2x^2=x^2(x+2)\) and 111 --> \(x^4+x^3+x=x \,(x^3+x^2+1)\)

Substituting \(x=3\) into the above factorised expressions gives the factorisation as before. However, in some bases, the polynomials do not factorise. For example, in base 5:

45 --> \(x^2+4x=x \, (x+4) \) but 111 --> \(4x^2+2x+1\) which doesn't factorise.

Carmichael Numbers

Before discussing Carmichael numbers, the prelude to my interest in these numbers must be described. On the 29th January 2019, I turned 25503 days old. As always, I started my morning by investigating the mathematical properties of this number, looking firstly for relevant entries in the Online Encyclopaedia of Integer Sequences or OEIS. Nothing much of interest showed up so I moved on to Numbers Aplenty where mention was made that it's a D-number.

The description for a \(D\)-number was:

Also known as \(3\)-Knödel numbers, they are numbers \(n>3\) such that \(n\) divides \(k^{n-2}-k\) for all \(1<k<n\) relatively prime to \(n\). For example, \(9\) is a D-number since it divides all the numbers  \(2^7-2\),  \(4^7-4\), \(5^7-5\), \(7^7-7\) and \(8^7-8\).

D-numbers are listed in the OEIS (A033553) but 25503 does not show up in a search because it's too far down the list of numbers. Only the following numbers are displayed:

9, 15, 21, 33, 39, 51, 57, 63, 69, 87, 93, 111, 123, 129, 141, 159, 177, 183, 195, 201, 213, 219, 237, 249, 267, 291, 303, 309, 315, 321, 327, 339, 381, 393, 399, 411, 417, 447, 453, 471, 489, 501, 519, 537, 543, 573, 579, 591, 597, 633, 669, 681, 687, 693, 699, 717, 723, 753, 771, 789, 807, 813, 819

All of these numbers are odd and composite, with most being divisible by 3. The first term that isn't divisible by 3 is 50963, the 2000\(^{th}\) term. 25503 is the 1092\(^{nd}\) term with neighbours 25401 and 25539.

Just to confuse matters, there are two ways of expressing the condition for a number to be a \(D\)-number or \(3\)-Knödel number. This is because:$$ \frac{k^{n-2}-k}{n}=k \times \frac{k^{n-3}-1}{n} $$We know that \(k\) and \(n\) are coprime, so \(n\) must divide \( k^{n-3}-1 \). This means that:$$\begin{align}
k^{n-3}-1&\equiv 0 \pmod{n} \\
k^{n-3} &\equiv 1 \pmod{n}

\end{align} $$Thus the 3 in the \(3\)-Knödel designation comes from the \(n-3\) index to the \(k\) base and the generalisation follows that a \(n\)-Knödel number for a given positive integer \(n\) is a composite number \(m\) with the property that each \(k < m\) coprime to \(m\) satisfies \( k^{m-n} \equiv 1 \pmod {m}\). The concept is named after Walter Knödel. The set of all \(n\)-Knödel numbers is denoted \(K_n\). The special case \(K_1\) represents the Carmichael numbers.

As can be seen by the initial values in Figure 1, the Carmichael numbers are few and far between:

Figure 1: source 

The Carmichael numbers lead us on to Fermat's Little Theorem which states that if \(p\) is a prime number and \(a\) is a natural number then:$$a^{\,p-1}-1 \equiv 0 \pmod{p} $$There is a proof of this theorem by mathematical induction on WolframMathWorld and the theorem shows that:

if p is prime, there does not exist a base \(a<p\) with \(a\) and \(p\) coprime such that \(a^{\,p-1}-1\) possesses a nonzero residue modulo \(p\). If such base \(a\) exists, \(p\) is therefore guaranteed to be composite. However, the lack of a nonzero residue in Fermat's little theorem does not guarantee that \(p\) is prime. The property of unambiguously certifying composite numbers while passing some primes make Fermat's little theorem a compositeness test which is sometimes called the Fermat compositeness test. A number satisfying Fermat's little theorem for some nontrivial base and which is not known to be composite is called a probable prime. Composite numbers known as Fermat pseudoprimes (or sometimes simply "pseudoprimes") have zero residue for some values of \(a\) and so are not identified as composite. Worse still, there exist numbers known as Carmichael numbers (the smallest of which is 561) which give zero residue for any choice of the base \(a\) relatively prime to \(p\). 

This brings us full circle and though much more could be said, at least I have a firmer grasp of what Carmichael numbers are all about. I have written about Fermat pseudoprimes in an earlier post on Thursday, 30 August 2018. I also make reference to the Carmichael numbers in that post, noting that these numbers have at least three prime factors e.g. 561 = 3 x 11 x 17.

Before finishing up, I should refer to the OEIS A002997 entry for the Carmichael numbers. These are the numbers listed there (note that the majority end in the digit 1):

561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461  

ADDENDUM (added September 7th 2021):

A225509

-5-Knödel numbers.

15, 55, 75, 91, 175, 247, 275, 715, 775, 1275, 1435, 2275, 2635, 3075, 3355, 4615, 6355, 6475, 7975, 8827, 9139, 10075, 10675, 11275, 11935, 13515, 14555, 21775, 26455, 28975, 30415, 31675, 32395, 43615, 46075, 47275, 52195, 59755, 64255, 77275, 78403, 81055

An interesting extension of \(n\)-Knödel numbers to \(n\) negative, in this case \(n= -5\). Composite numbers \(m > 0\) such that if \(1 < a < m\) and gcd(\(m,a\)) = 1 then \(a^{\,m+5} \equiv 1 \pmod {m}\). Permalink.

L-th Order Palindromes

It took me a little time to come to terms with what was meant exactly by an L-th order palindrome but eventually I did. It all started with an entry in the Online Encyclopaedia of Integer Sequences (OEIS) for 25487, my diurnal age on 23rd January 2019. The entry states:

A089381: L-th order palindromes with L>2.

10917, 11907, 11997, 12987, 13977, 14967, 15957, 16947, 17937, 18927, 19917, 20997, 21834, 21987, 22977, 23814, 23967, 23994, 24957, 25497, 25947, 25974, 26487, 26937, 27477, 27927, 27954, 28467, 28917, 29457, 29907, 29934, 30915

$$ P(m) = \begin{cases} m/2 & \quad \text{if } m \text{ is even}\\ m+\text{rev}(m) & \quad \text{if } m \text{ is odd}\\ \end{cases}$$ $$ \text{where rev( \(m \) ) is \(m \)'s base 10 representation reversed}$$ The following explanation is given as to what it's all about:

Let P(m) = m/2 if m is even, m + rev(m) if m is odd, where rev(m) is m's base 10 representation reversed. It is conjectured that any number k eventually cycles when P is repeatedly applied to it. If the cycle has length L, k is called an L-th order palindrome. 

It has not been proved that every number eventually cycles, but all numbers less than a million do. Palindromes of order L>2 seem to be quite rare. 10917 is the smallest and has order 7. There are 263 less than 100000 and 7745 less than 1000000. 

The first number with L>2 that doesn't end in the same cycle as 10917 is 1000353. Other cycles are known, most of them fairly small, but one has length 327 (starting with 1447132589595). 

There are an infinite number of different cycles of length 7 because one can insert any number of 9's in the middle of a number in the 7th order cycle and get a new cycle of length 7 - e.g., taking the number 13748625 from the cycle, one can produce another cycle from 13749998625.

The following example is also provided:

For most numbers, iterating P produces a cycle of length 2:
e.g., 121 -> 242 -> 121 -> ... 

The sequence for 10917 is 10917, 82818, 41409, 131823, 459954, 229977, 1009899, 10998900, 5499450, 2749725, 8029197, 15948405, {66433356, 33216678, 16608339, 109989000, 54994500, 27497250, 13748625} where the numbers in the brackets repeat. There are 7 numbers inside the brackets so 10917 is a 7th-order palindrome. 

 For 25497, the sequence generated is as follows (click here for SageMath permalink):

L-th order palindrome of cycle length 7 

104949
1054350
527175
1098900
549450
274725
802197
15934056637356
3318678
1659339
10998900
5499450
2749725
8029197
15948405
66433356
33216678
16608339
109989000
54994500
27497250
13748625
66433356

I tested the algorithm out with 1447132589595 and a cycle of length 327 is indeed produced. So the previous L-th order palindrome as well as the next two are all permutations of the same digits: 24957, 25497, 25947, 25974

The Mersenne Twister

I stumbled upon the Mersenne Twister after investigating Pseudorandom Number Generators (PRNGs) stimulated by an article about a hacker who had made a speciality of exploiting weaknesses in the PRNGs incorporated into certain types of slot machines.

Here is an excerpt from the article:

In the course of reverse engineering Novomatic’s software, Alex encountered his first PRNG. He was instantly fascinated by the elegance of this sort of algorithm, which is designed to spew forth an endless series of results that appear impossible to forecast. It does this by taking an initial number, known as a seed, and then mashing it together with various hidden and shifting inputs—the time from a machine’s internal clock, for example. Writing such algorithms requires tremendous mathematical skill, since they’re supposed to produce an output that defies human comprehension; ideally, a PRNG should approximate the utter unpredictability of radioactive decay.

The intriguingly named Mersenne Twister is described thus by Wikipedia:

The Mersenne Twister is a pseudorandom number generator (PRNG). It is by far the most widely used general-purpose PRNG. Its name derives from the fact that its period length is chosen to be a Mersenne prime. 

The Mersenne Twister was developed in 1997 by Makoto Matsumoto and Takuji Nishimura. It was designed specifically to rectify most of the flaws found in older PRNGs. 

The most commonly used version of the Mersenne Twister algorithm is based on the Mersenne prime \(2^{19937}−1\). The standard implementation of that, MT19937, uses a 32-bit word length. 

The Mersenne Twister is the default PRNG for the following software systems: Microsoft Excel, GAUSS,  GLib, GNU Multiple Precision Arithmetic Library, GNU Octave, GNU Scientific Library, gretl, IDL, Julia,  CMU Common Lisp, Embeddable Common Lisp, Steel Bank Common Lisp, Maple, MATLAB, Free Pascal, PHP, Python, R, Ruby, SageMath, Scilab, Stata.

I don't want to delve too deeply into the how the Mersenne Twister actually generates its random numbers. However, the following article provides a simple overview of how it works.

How does the Mersenne Twister work?

Posted February 2016

Someone asked that question on reddit, and so I replied with a high level answer that should provide a clear enough view of the algorithm:

From a high level, here's what a PRNG is supposed to look like (DIAGRAM 1):

DIAGRAM 1

You start with a seed (if you re-use the same seed you will obtain the same random numbers), you initialise it into a state. Then, every time you want to obtain a random number, you transform that state with a one-way function \(g\). This is because you don't want people to find out the state out of the random output.

You want another random number? You first transform the state with a one way function
\(f\): this is because you don't want people who found out the state to be able to retrieve past states (forward secrecy). And then you use your function \(g\) again to output a random number.

Mersenne Twister (MT) is like that, except:

• your first state is not used to output any random numbers
• a state allows you to output not only one, but 624 random numbers (although this could be thought as one big random number)
• the \(g\) function is reversible, it's not a one-way function, so MT it is not a cryptographically secure PRNG.

With more details, here's what MT looks like (DIAGRAM 2):

DIAGRAM 2

The \(f\) function is called "twist", the \(g\) function is called "temper". You can find out how each functions work by looking at the working code on the wikipedia page of MT.

*********************************

The slot machine hacking via knowledge of the PRNG within got me thinking about my own gambling on Lotto, a vice I indulge in weekly. How are the lotto numbers selected? Are there physical, numbered balls involved or is a PRNG used? There's no shortage of sites that will generate random numbers for you to enter in any lottery of your choosing but how are the actual winning numbers generated? Well it seems that the numbers are physically selected in Australian lotteries as shown in the following video:

However, Lucky Lotteries is different.

To quote from the website:

Lucky Lotteries is a raffle style jackpot game that guarantees over 10,000 prizes in every draw! Unlike other lottery games, each number is unique so there is no sharing of prizes. 

There are two Lucky Lotteries games – Super Jackpot and Mega Jackpot. 

Each game has a set amount of numbers per draw and once all available numbers are sold, the winning numbers are drawn using a random number generator.

So clearly a PRNG is used in certain lotteries. Of course, I use SageMath extensively and so it's of interest to know about what PRNG it uses. SageMath documentation explains that:

It is possible to select which random number generator drives the sampling as well as the seed. The default is the Mersenne twister. Also available are the RANDLXS algorithm and the Tausworthe generator (see the gsl reference manual for more details). These are all supposed to be simulation quality generators. For RANDLXS use rng = 'luxury' and for tausworth use rng = 'taus': 

sage: T = RealDistribution('gaussian', 1, rng = 'luxury', seed = 10)

The Golden Key

Figure 1: this is the book that mentions the
Golden Key, a description of its contents is
included at the end of this post

The sets of infinite natural numbers and infinite prime numbers are related by a formula given by Euler, which, famously known as the Golden Key, is given by:$$

\prod_{ p} \frac{1}{1-\displaystyle \frac{1}{p^{\,s}}}=\sum_n \frac{1}{n^{\, s}} \text{ where } s>1

$$where the left-hand-side products are carried over all the prime numbers \(p\) and the right-hand-side sum is carried over all the natural numbers \(n\).

For the range of numbers from 1 to 100,000 (with \(k\)=100,000), the results are as follows:$$
\prod_{p=2}^k \frac{1}{1-\displaystyle \frac{1}{p^{\, s}}}=1.64493274720203 \text{ and } \sum_{n=1} ^{k} \frac{1}{n^s}=1.64492406679823

$$The right hand side of Euler's formula is of course the Riemann Zeta function and so the equation can be rewritten as:$$

\zeta(s)=\sum_{n \geq 1}n^{-s}=\prod_p (1-p^{-s})^{-1}

$$

Figure 2

which is an easier form to remember (s can be any complex number with ℜs>1). The relationship at first seems strange, linking as it does a sum involving the reciprocals of the natural numbers and a product involving the reciprocals of the prime numbers. However, as this blog post points out, the formula is nothing but a fancy way of writing out the Sieve of Eratosthenes. The post goes on to derive the formula. I've just taken a screenshot of the working (Figure 2) rather than type it all out using LaTeX (lazy I know). In fact, this post is only the first in a long series of posts (from September 2013 to May 2017) dealing with Understanding the Riemann Hypothesis.

I came across the Golden Key when perusing Kumar Asok Mallik's book The Story of Numbers during his introduction to prime numbers on page 23. This is quite an interesting book that I've added to my Calibre library. The description of the book in the metadata is as follows:

This book is more than a mathematics textbook. It discusses various kinds of numbers and curious interconnections between them. Without getting into hardcore and difficult mathematical technicalities, the book lucidly introduces all kinds of numbers that mathematicians have created. Interesting anecdotes involving great mathematicians and their marvellous creations are included. The reader will get a glimpse of the thought process behind the invention of new mathematics. 

Starting from natural numbers, the book discusses integers, real numbers, imaginary and complex numbers and some special numbers like quaternions, dual numbers and p-adic numbers. Real numbers include rational, irrational and transcendental numbers. Iterations on real numbers are shown to throw up some unexpected behaviour, which has given rise to the new science of "Chaos". Special numbers like e, pi, golden ratio, Euler's constant, Gauss's constant, amongst others, are discussed in great detail.The origin of imaginary numbers and the use of complex numbers constitute the next topic. 

It is shown why modern mathematics cannot even be imagined without imaginary numbers. Iterations on complex numbers are shown to generate a new mathematical object called 'Fractal', which is ubiquitous in nature. Finally, some very special numbers, not mentioned in the usual textbooks, and their applications, are introduced at an elementary level.The level of mathematics discussed in this book is easily accessible to young adults interested in mathematics, high school students, and adults having some interest in basic mathematics. The book concentrates more on the story than on rigorous mathematics.

If I can read an entry a day from this book, I'll soon be a wiser man mathematically. Here is a link to a very useful series of slides explaining the importance of the Riemann zeta function and also mentioning the Golden Key.

on January 16th 2021

mainly improving the look of the mathematical expressions

Derangements

Today I turned 25487 days old and the first OEIS entry for this number is A002467: 

Given \(n\) letters and \(n\) envelopes, how many ways are there to fill the envelopes so that at least one letter goes into its right envelope? 

It took some further investigation to realise that this sequence was closely related to OEIS A000166 the numbers of derangements of \(n\): 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ...

So what is a derangement? According to Wikipedia:

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, derangement is a permutation that has no fixed points. 

The number of derangements of a set of size \(n\), usually written \(Dn\), \(dn\), or \(!n\), is called the "derangement number" or "de Montmort number". (These numbers are generalised to rencontres numbers.) The subfactorial function (not to be confused with the factorial \(n!\)) maps \(n\) to \(!n\). No standard notation for subfactorials is agreed upon; \(n¡\) is sometimes used instead of \(!n\). 

The problem of counting derangements was first considered by Pierre Raymond de Montmort in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time.

To construct the formula, let's consider \(n\) letters and \(n\) envelopes. The first envelope can be filled in \(n-1\) ways and, for the second envelope, there are two possibilities. If the second envelope is filled with the first letter, then the first and second letters are taken care of the problem is reduced to \(n-2\) envelopes and \(n-2\) letters. If this does not happen, then there are now \(n-1\) envelopes and \(n-1 \) letters. This can be written as: $$ !n=(n-1)(!(n-1)+!(n-2))$$From here a formula can be derived to calculate the derangements for \(n\) items, specifically:$$!n=n! \sum_{i=0}^{n} \frac{(-1)^n}{i!}$$For this formula !0=1 and !1=0. In the case of 8 letters and 8 envelopes, we get: !8 = 14833.

One letter has ended up in the right envelope. There are 25487
ways in which at least one letter will end up in the right envelope.

So 14833 is the number of ways that no letters end up in the right envelopes. We are interested in the number of ways that at least one letter will end up in the right envelope. So 14833 needs to be subtracted from 8! = 40320 (the total number of possibilities) to get 25487.

Let's look at how the probability of a derangement changes as the number of elements increases. It can be noted that the Taylor Series for the function \(f(x)=1/e^x\) is given by:$$
\frac{1}{e^x}= \sum_{i=0}^{\infty} \frac{(-1)^i x^i}{i!}
$$So when \(x=1\), it can be seen that \(1/e\) is identical to the formula for the derangements:$$
\frac{1}{e}= \sum_{i=0}^{\infty} \frac{(-1)^i}{i!} \approx 0.3678794412
$$So after about four elements, the probability of a derangement quickly settles down to about 37%, no matter what the number of elements. Here is a link to a paper on derangements that begins:

A group of \(n\) men enter a restaurant and check their hats. The hat-checker is absent minded, and upon leaving, she redistributes the hats back to the men at random. What is the probability \(P_n\) that no man gets his correct hat, and how does \(P_n\) behave as \(n \rightarrow \infty\)?

Here are two Numberphile videos on Derangements with James Grimes presenting. The first is an introduction and the second derives a proof for the formula: