Simple Somos Sequence

Browsing through an old collection of Russian olympiad problems, I noticed one that I marked solved years ago, when a highschooler. For the life of me I could not remember the solution I came up with at the time. The problem has been offered at the final stage of the XXVI (1963) Moscow Mathematical Olympiad, senior class.

The sequence, so simply defined, falls into the category of Elliptic Sequences discovered by M. Somos in the mid-1970s. As I do not remember my old solution, I shall simply adopt the approach that worked for more complex Somos sequences.

Let's find a few first members of the sequences: 1, 1, 3, 11, 41, 153, ... An immediate observation is that all of the numbers are odd. More generally, if the process indeed generates an integer sequence then all the members of the sequence are bound to be odd. The proof is by induction: if a_n-1 is odd, then so is its square increased by 2. When divided by an integer a_n-2 it may only give another odd number.

But more is true: in any triple of successive terms, the members of the sequences are pairwise prime:

gcd(3, 11) = gcd(3, 41) = gcd(11, 41) = 1 and also
gcd(11, 41) = gcd(11, 153) = gcd(41, 153) = 1,

but, of course, gcd(3, 153) = 51 ≠ 1. The claim is actually obvious as any common factor of a_n and a_n-1 (which are both odd) would divide 2, i.e., 1.

Denote some four consecutive terms of the sequence a, b, c = (b² + 2) / a, d = (c² + 2) / b and suppose that these and all the preceding terms are integers. We want to show that the next term e = (d² + 2) / c is also an integer.

Observe that d ≡ 2/b (mod c), which is a regular residue modulo c because c and b are mutually prime. Let's write d = d₀ + C, where d₀ is the residue modulo c equal to 2/b, and C is a multiple of c.

We have

because again b and c are mutually prime. It follows that ce is divisible by c so that, indeed, e is an integer.

Simple as it is, the fact that the algorithm generates an integer sequence is really unexpected (from the pre-Somos view point). As if it were not enough, the algorithm admits a generalization: 2 in the numerator can be replaced with any positive integer m: a_n = (a_n-1² + m) / a_n-2 would still produce an integer sequence. The proof is exactly the same.

This is also true for some combinations of the initial conditions and m. If a₀ = a, and a₁ = b, then, for example, the triples (a, b, m), with (1, 5, 4), (1, 7, 6), or (2, 7, 3) generate integer sequences.

A calculator that lists a few dozens terms of the sequence is available on a separate page.

• Step into the Elliptic Realm
• Simple Somos Sequence
  • Simple Somos Sequence Calculator
• The Rascal Triangle
• Frieze Patterns

|Contact| |Front page| |Contents| |Algebra| |Store|