Somos Sequences

I came across an interesting article in Quanta Magazine, dated November 16th 2023, that mentions Somos sequences that I'd not heard of before. To quote from the article:

A Somos-\(k\) sequence starts with the digit or digits 1, \(k\) of them. Each new term of a Somos-\(k\) sequence is defined by pairing off previous terms, multiplying each pair together, adding up the pairs, and then dividing by the term \(k\) positions back in the sequence.

The sequences aren’t very interesting if \(k\) equals 1, 2 or 3 — they are just a series of repeating ones. But for \(k\) = 4, 5, 6 or 7 the sequences have a weird property. Even though there is a lot of division involved, fractions don’t appear.

Figure 1 shows an excerpt from the article that illustrates how the Somos-5 series is generated.

Figure 1

It's easy enough to write some SageMath code to generate the Somos-5 and here are the initial terms and, as can be seen, the terms get very large very quickly.

1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, 274, 1217, 6161, 22833, 165713, 1249441, 9434290, 68570323, 1013908933, 11548470571, 142844426789, 2279343327171, 57760865728994, 979023970244321

These terms constitute OEIS A006721  (permalink): 

A006721

Somos-5 sequence: a(n) = (a(n-1) * a(n-4) + a(n-2) * a(n-3)) / a(n-5), with a(0) = a(1) = a(2) = a(3) = a(4) = 1.

The Somos-4 sequence is OEIS A006720 (permalink):

A006720

Somos-4 sequence: a(0)=a(1)=a(2)=a(3)=1; for n >= 4, a(n) = (a(n-1) * a(n-3) + a(n-2)^2) / a(n-4).

The initial members are:

1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898, 126742987, 1687054711, 47301104551, 1123424582771, 32606721084786, 1662315215971057, 61958046554226593, 4257998884448335457, 334806306946199122193

The Somos-6 series is OEIS A006722:

A006722

Somos-6 sequence: a(n) = (a(n-1) * a(n-5) + a(n-2) * a(n-4) + a(n-3)^2) / a(n-6), a(0) = ... = a(5) = 1.

The initial members are:

1, 1, 1, 1, 1, 1, 3, 5, 9, 23, 75, 421, 1103, 5047, 41783, 281527, 2534423, 14161887, 232663909, 3988834875, 45788778247, 805144998681, 14980361322965, 620933643034787, 16379818848380849, 369622905371172929, 20278641689337631649, 995586066665500470689

The Somos-7 series is OEIS A006723:

A006723

Somos-7 sequence: a(n) = (a(n-1) * a(n-6) + a(n-2) * a(n-5) + a(n-3) * a(n-4)) / a(n-7), a(0) = ... = a(6) = 1.

The initial members are:

1, 1, 1, 1, 1, 1, 1, 3, 5, 9, 17, 41, 137, 769, 1925, 7203, 34081, 227321, 1737001, 14736001, 63232441, 702617001, 8873580481, 122337693603, 1705473647525, 22511386506929, 251582370867257, 9254211194697641, 215321535159114017

A Puzzle

Figure 1 shows the problem that confronted me over the breakfast table this morning.

Figure 1

As I've said before, I dislike this format and what we should say is that we say that we have a function \(f(x)\) that maps \(x\) to \(y\):

• \(f(1)=3\)
• \(f(2)=3\)
• \(f(3)=5\)
• \(f(4)=4\)
• \(f(5)=4\)
• \(f(6)= \, \, ?\)

I'll make a small adjustment here so that the graph has \(x\) coordinates that correspond. It looks like this with the answer of \(f(6)=6\) added which I'll explain and Figure 1 shows the result:

• \(f(0)=1\)
• \(f(1)=3\)
• \(f(2)=3\)
• \(f(3)=5\)
• \(f(4)=4\)
• \(f(5)=4\)
• \(f(6)= 6 \)

Figure 1: permalink

As can be seen from the graph the pattern repeats once \( (5, 4) \) is reached. Figure 2 is the pattern expanded.

Figure 2: permalink

What is the formula to represent the numbers as part of a recurrent series given by \( a(n) \) = ... ? Can the graph be expressed in terms of \(y=f(x) \) for some function \(f\)? These are two interesting questions that I should try to answer. Once I crack it, I'll post the information here and maybe a link to a new blog post about how I cracked it.

Alternating Series Test

Just lately, I fell to wondering what the sum of the following infinite series was:$$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\frac{1}{5}-\cdots = \sum_{n=1}^{\infty}(-1)^{n+1} \, \frac{1}{n}$$This can be called the alternating harmonic series. I knew that the harmonic series diverged but I was certain its alternating equivalent was convergent. But what did it converge to? Of course, the answer to such questions is always close at hand but the question had been bouncing around in my head without my doing anything to answer it. Today, I decided to answer it.

It turns out that the question of convergence of this sum can be decided for a much broader category of sums using what's referred to the Alternating Series Test but also Leibniz's test, Leibniz's rule, or the Leibniz criterion. Here is a statement of the test:

A series of the form:$$\sum_{n=0}^{\infty} (-1)^{n} a_n = a_0-a_1 + a_2 - a_3 + \cdots$$where \(a_n\) are all positive (or all negative) is called an alternating series. The alternating series test then says that if |\(a_n\)| decreases monotonically and \( \displaystyle \lim_{n \rightarrow \infty} a_n=0\) then the alternating series converges.

There are plenty of sources that will prove this to be true but I'll just use the result here, namely that the series converges because it satisfies the alternating test criteria. The question remains however, of what the sum converges to. Let's use SageMathCell to find the answer. Figure 1 shows the result.

Figure 1: permalink

$$ \text{Thus we see that }\sum_{n=1}^{\infty}(-1)^{n+1} \, \frac{1}{n}=\ln{2} $$This result is in fact a particular instance of a more general sum:$$x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+ \cdots =\sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} x^n = \ln (1+x)$$This infinite series is known as the Mercator or Newton-Mercator series and, when \(x=1\) it becomes the alternating harmonic series. The series converges to the natural logarithm (shifted by 1) whenever \( -1<x\leq 1 \). Reference. 

Again, SageMathCell will generate the correct result as shown in Figure 2.

Figure 2: permalink

It's relatively easy to prove that:$$\ln (1+x)=\sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} x^n $$Here is the proof as described in Wikipedia:

Start with the finite geometric series where \( t \ne -1 \):$$\begin{align} \frac{1-(-t)^n}{1+t}&=1-t+t^2-\cdots+(-t)^{n-1}\\
\frac1{1+t}&=1-t+t^2-\cdots+(-t)^{n-1}+\frac{(-t)^n}{1+t}\\
\int_0^x \frac{dt}{1+t}&=\int_0^x \left(1-t+t^2-\cdots+(-t)^{n-1}+\frac{(-t)^n}{1+t}\right)\ dt\\
\ln(1+x)&=x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots+(-1)^{n-1}\frac{x^n}{n}+(-1)^n \int_0^x \frac{t^n}{1+t}\ dt\\
&= \sum_{n=1}^{\infty} \frac{(-1)^{n+1}}{n} x^n \end{align}$$

This is because the remainder term tends to 0 as \( n \to \infty \) if \( -1< x \le 1 \). This is apparent if you graph \( \displaystyle \frac{t^n}{1+t} \) as shown in Figure 3 for \(n=50\).

Figure 3: created in GeoGebra

The Harmonic Series

Here's an interesting problem: an ant traverses a circle with a circumference of one metre at a rate of one centimetre per second. After each second, the circumference of the circle increases by one metre. Will the ant ever return to its starting point?

Let's consider the matter. In the first second, the ant traverses 1% of the circumference; in the second second, it traverses 1/2%; in the third second, 1/3% and so on. The cumulative distance covered is given by the sum of:

1 + 1/2 + 1/3 + 1/4 + 1/5 + ... 

This is the harmonic series and it is divergent, meaning that the sum is continuously increasing and never reaches any upper limit. Contrast this to a convergent geometric series, the sum of whose terms approaches ever closer to 2 as more terms are added:

1 + 1/2 + 1/4 + 1/8 + 1/16 + ...

In the case of the harmonic series, the sum will certainly surpass the 100% required for the ant to return to its starting point. It may take a long time but it will happen. In fact OEIS A004080 tells us that it would take the following number of seconds:

15092688622113788323693563264538101449859497

This of course represents more than 4.78 x 10^23 years which is far in excess of the age of the universe! The following screenshot is taken from the WolframAlpha article about the harmonic series.

Taken from http://mathworld.wolfram.com/HarmonicSeries.html

This Numberphile YouTube video was the inspiration for this post.