FirstWritten: March 21, 2013 ; This version: June 12, 2013.

[Published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, arxiv.org, and also co-published in J. Difference Eq. Appl. v. 20(2014), 852-858.]

Jacobi said ``man muss immer umkehren''. And indeed it takes a genius like Michael Somos to take a specific non-linear recurrence, like

a(n)=(a(n-1)a(n-3)+a(n-2)^2)/a(n-4), subject to a(1)=1, a(2)=1, a(3)=1, a(4)=1,

and observe that surprise, surprise, they always generate integers. Then it takes other geniuses to actually prove this fact (and the more general so-called Laurent phenomenon).

But let's follow Jacobi's advice and go backwards. Rather than try to shoot a target fifty meters away, and most probably miss it, let's shoot first, and then draw the bull'e eye. Then we are guaranteed to be champion target-shooters. So let's take a sequence of integers that manifestly and obviously only consists of integers, and ask our beloved computers to find non-linear recurrences satisfied by the sequence itself, or by well-defined subsequences (e.g. if the original sequence is a_n, study b_n:=a_n², or even b_n:=a_2ⁿ.

Maple Package

• NesSomos

Input and Output files

• To see a webbook containing 198 second-order, non-linear, recurrences that surprisingly always give you integers,
  input file yields the output file.

• To get a non-linear recurrence that suprisingly always outputs polynomials in c,
  the input file yields the output file.

• To get a webbook with 48 non-linear, SIMPLE Somos-like (where the denominator is a monomial) recurrences, that suprisingly always give integers,
  the input file yields the output file.

• To get a webbook with 48 non-linear, COMPLICATED Somos-like (where the denominator is NOT a monomial) recurrences, that suprisingly always give integers,
  the input file yields the output file.

Doron Zeilberger's Home Page