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.
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.
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%.
Index of first occurrence of n appearing twice in succession in Van Eck's sequence (A181391), or 0 if it never occurs.
I was naturally curious about how Van Eck's sequence was generated and I found this helpful Numberphile video narrated by Mr. Sloane himself:
The value of \(n\) that occurs twice in succession, for the first time, is 29 and so 26146 refers to the the index position (counting the first zero of the sequence as term 1) of the second 2 in the digit sequence 2929 (marked in bold red). Here are the early terms of the Van Eck sequence showing the situation for 0, 2 and 3 (11 doesn't appear in the sequence):
The first four terms of the A308782 sequence are 2, 0, 8, 50 corresponding to \(n\) = 0, 1, 2, 3. I was interested in generating the Van Eck sequence using SageMath and below is the code that I came up with (permalink):
Here is a link to two different Python 3 algorithms that generate the Van Enk sequence. Figure 1 shows the plot for these first 100 values:
Figure 1
Here is the Van Eck sequence represented as a melody:
Of course, as with the Fibonacci sequence, a starting value other than 0 will produce a different but similar sequence to the Van Eck. My SageMath algorithm is easily modified to investigate such sequences. For example, let's make the first term 1 (permalink):
The Fibonacci sequence is the most famous example of a generalised sequence that begins with two seed numbers \( a \) and \( b \) and then proceeds as follows:$$ G_n=\begin{cases}a&\mbox{if }n=0;\\b&\mbox{if }n=1;\\G_{n-1}+G_{n-2}&\mbox{otherwise.}\end{cases} $$So \(G_3=b+a \), \(G_4=a+2b \) etc. It can be shown that the \(n\)-th term in the Fibonacci sequence is given by \( [ \phi ]^n/ \sqrt 5 \) (where the square brackets denote rounding to the nearest whole number) and so the question could be asked is there a general formula for calculating the \(n\)-th term of the generalised sequence \(a, b, a+b, a+2b, ... \)? Well, after watching this Numberphile video, it turns out that there is:
The formula is:$$G_n=\bigg [ \phi ^n \times \frac{(3 \sqrt 5 - 5) \, a + (5 - \sqrt 5) \, b}{10} \bigg ] $$When \(a=1\) and \(b=1\), we get \( [ \phi ]^n/ \sqrt 5 \) so all is well. When \(a=1 \) and \(b=3 \), we get simply \( [ \phi ]^n \) and this generates the Lucas numbers: 1, 3, 4, 7, 11, ...
The Numberphile video makes the point that it is the number \( \sqrt 5 \) that is at the heart of this formula and thus underlies all these Fibonacci-like sequences that are generated from two seed numbers.
We can also consider not two but three seed numbers and this leads to what is called the Tribonacci sequence defined by:$$
T_n=\begin{cases}0&\mbox{if }n=0\\1&\mbox{if }n=1\\1&\mbox{if }n=2\\T_{n-1}+T_{n-2}+T_{n-3}&\mbox{if }n \geq 3\end{cases}
$$This leads to 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ... and, just as the closed-form formula for the Fibonacci sequence involved the roots of the polynomial \(x^2-x-1\), it is reasonable to expect that the analogous formula for the tribonacci sequence involves the polynomial \(x^3-x^2-x-1\) and this is indeed the case. This polynomial has one real root:$$ \frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929 $$ called the tribonacci constant and this is the ratio of successive pairs of terms. In other words:$$
$$The other two roots are complex conjugates (source). The generating function for the tribonacci numbers is quite similar to the generating function for the Fibonacci numbers:$$ \sum_0 ^ \infty \! T_n \, x^n = \frac {x}{1-x-x^2-x^3} $$
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, ...
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:
On Thursday, the 21st April 2106, I posted about Repunits and Smith Numbers. The day was 24490 and the number turned out to be a member of OEIS A104167, a sequence whose members have the property that, when multiplied by any repunit prime, the result is a Smith number. Just to recapitulate from that post:
A repunit is defined by Wikipedia as a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book "Recreations in the Theory of Numbers". A repunit prime is a repunit that is also a prime number.
A Smith number is defined by Wikipedia as a composite number for which, in a given base (in base 10 by default), the sum of its digits is equal to the sum of the digits in its prime factorisation. For example, 378 = 2 × 3 × 3 × 3 × 7 is a Smith number since 3 + 7 + 8 = 2 + 3 + 3 + 3 + 7. In this definition the factors are treated as digits: for example, 22 factors to 2 × 11 and yields three digits: 2, 1, 1. Therefore 22 is a Smith number because 2 + 2 = 2 + 1 + 1.
Today, I turned 25428 days old and this number is a Smith number with the property that the next consecutive number (25429) is also a Smith number. Such pairs of numbers are termed Smith brothers. They are not that common. OEIS A050219 lists the smaller of the members of each pair. Here is the list as shown on the OEIS website:
Here is a SageMathCell with the code that I wrote to generate this sequence (up to 25428). Note that print F must be changed to print(F) because SageMath is now using Python 3 and the old Python 2 code for print no longer works:
It works but I'm sure there are more elegant ways to generate the same result. Here is a Numberphile YouTube video that explains a little more about Smith Numbers:
