Guessing the Elusive Patterns in the Slater-Valez sequence (aka OEIS A081145)

Shalosh B. EKHAD and Doron ZEILBERGER

Dedicated to Aviezri S. Fraenkel (b. 28 Iyar, 5689) on his 90-th birthday.

The Slater-Valez sequence (OEIS sequence A081145)

A few days ago, guru Neil Sloane told us about the fascinating OEIS sequence A081145 [Sl] introduced in [SV]. Its definition, in English, is very simple:

“a(1) = 1 and a(n) is the smallest positive integer such that a(n) differs from all a(i) for 1 ≤ i < n and |a(n) − a(n − 1)| differs from all |a(i) − a(i − 1)| for 1 < i < n.”

Using the “mex” function (mex(S) is the smallest positive integer not in S), a(n) may be defined by a(1) = 1, d(1) = 1 and

a(n) := mex ({a(i) | 1 ≤ i < n} ∪ {a(n − 1) + d(i) | 1 ≤ i < n} ∪ {a(n − 1) − d(i) | 1 ≤ i < n}) ,

d(n) := |a(n) − a(n − 1)| .

In [SV] it is proved that the sequence {a(n)} is a permutation of the the set of positive integers, and it was conjectured that so is the sequence d(n) := |a(n) − a(n − 1)|. As pointed out in [Sl] a plot of the set of points [n, a(n)] shows that they seem to almost lie on three distinct lines through the origin whose slopes are approximately 0.56, 1.40 and 2.24. See the diagram in

http://www.math.rutgers.edu/~zeilberg/tokhniot/svPics/sv1.html .

Being experimental mathematicians, we were wondering whether one can deduce these slopes using ‘back of the envelope heuristic arguments’. Then Wythoff’s game came to mind. This lovely game was taught to one of us (DZ) many years ago, by combinatorial games guru Aviezri Fraenkel, where a similar sequence, also defined in terms of “mex”, shows up. It so happened that Fraenkel’s 90-th Hebrew birthday is today (Iyar 28, 5779; he was born Iyar 28, 5689), and his Gregorian birthday is in a few days (June 7, 2019; he was born June 7, 1929), so it is appropriate that we dedicate this modest note, inspired by his teaching, to him on this important day.

But first let’s digress and talk a little about Aviezri Fraenkel.

Aviezri Fraenkel

In addition to his many other accomplishments, Aviezri is one of the founding fathers of Combinatorial Game Theory [along with the Winning Ways trio, Elwyyn Berlekamp (1940-2019), John Conway (b. 1937), and Richard Guy (b. 1916)], one of the prettiest subjects in the whole of mathematics.

One of the nicest combinatorial games is a variant of two-pile Nim, called Wythoff’s game, that Fraenkel and his collaborators extended in many ways. A search of MathSciNet for the papers authored by Fraenkel that include the key-word Wythoff, comes up with 25 hits! We will only mention one of them [F]. That paper includes a short bio, whose last sentence reads

“... This and other works of his have been supported materially by his wife Shaula and their six children, one of whom studies mathematics and another considers an engineering career”.

The original Wythoff’s Game

Consider two piles, containing, say, x and y pennies (so the initial position is (x, y)) . Players take turn executing legal moves. A legal move consists of either taking any number of pennies from one of the piles (including the whole pile) leading to one of the positions

(x − 1, y), (x − 2, y), …, (0, y) ; (x, y − 1), (x, y − 2), …, (x, 0) ,

or the same number of pennies from both piles, leading to one of the positions (w.l.o.g, by symmetry we can assume that x ≤ y)

(x − 1, y − 1), (x − 2, y − 2), …, (0, y − x) .

The player to make the last move is the winner (in other words, if it is your turn and both piles are empty, i.e. the position is (0, 0), you lost the game.)

Under perfect play what are the losing positions? (aka P positions, the Previous player wins.)

Obviously, the positions (0, y) or (y, y) ( y > 0), are all winning positions (aka as N positions, the Next player wins). Since one legal move can lead to the P position (0, 0). The smallest position (x, y), with x ≤ y,that is not of that form is (1, 2). This is indeed a losing position, since all the legal moves lead to winning positions of your opponent. This implies, in turn, that (2, i + 1) and (1, 2 + i), and (1 + i, 2 + i) for i > 0 (and their reverses), are automatically winning positions. The smallest position that is not of that form is (3, 5) (and (5, 3)). Etc.

A moment’s thought would convince the reader that the set of losing positions (x, y) with x ≤ y, are

(A(n), B(n)) ,

where A(0) = 0, B(0) = 0 and the sequences A(n) and B(n) are defined recursively, for n > 0, by

A(n) = mex ({A(i) | 1 ≤ i < n} ∪ {B(i) | 1 ≤ i < n}) ,
B(n) = A(n) + n .

The first few losing positions (with x < y) are

{[1, 2], [3, 5], [4, 7], [6, 10], [8, 13], [9, 15], [11, 18], [12, 20], [14, 23], [16, 26], [17, 28], [19, 31],

[21, 34], [22, 36], [24, 39], [25, 41], [27, 44]} ,

and, of course, their reverses, [2, 1], [5, 3], . . .. If you plot the points (n, A(n)) for say, n ≤ 20, you would immediately notice an approximate straight line with a certain slope. Let’s call is α. This leads to an ansatz

A(n) = ⌊αn⌋ , B(n) = ⌊(1 + α)n⌋ ,

for some number α (the slope), yet to be determined. Since the two sequences A(n), B(n) exhaust everything and their ‘densities’ are, respectively 1/α and 1/(1 + α), our α (if it exists) must satisfy

\frac{1}{α} + \frac{1}{α + 1} = 1 ,

leading to the fact that α is the golden ratio, ϕ = \frac{1+\sqrt{5}}{2}. Now this is not yet a proof. But it turns out that one can prove that indeed A(n) = ⌊ϕn⌋ and hence B(n) = ⌊(1 + ϕ)n⌋. Why won’t you do it! A Heuristic Non-Rigorous estimate for the Slater-Valez slopes As noted in [Sl], if you plot the points (n, a(n)), they seem to lie on three distinct lines through the origin. Can we deduce a priori these slopes like we did for the Wythoff sequence? Examining the sequence a(n), we call a positive integer n

• State 1 if a(n)/n ≤ 1 ;

• State 2 if 1 < a(n)/n ≤ 2 ;

• State 3 if 2 < a(n)/n . In an ideal world, their relative frequencies would each be exactly \frac{1}{3}, and the states would cycle through 1 → 2 → 3 → 1, and the slopes would be, respectively α, α + δ, α + 2δ, for some numbers α and δ to be determined. Under this ideal situation, δ is easy. The ‘scatter-plot’ of the set of points (n, d(n)) (for n > 0) falls naturally into two lines, of slope δ and 2δ, but the transitions 1 → 2 and 2 → 3 both give rise to slope δ, while 3 → 1 gives rise to slope 2δ. Assuming that {d(n)} is a permutation of the integers, by a density argument, we must have

\frac{2}{3} · \frac{1}{δ} + \frac{1}{3} · \frac{1}{2δ} = 1 ,

leading to the exact value δ = \frac{5}{6}. Since the slopes of states 1, 2 and 3 are α, α + δ, α + 2δ, respectively, in an ideal world we would have

\frac{1}{3} ( \frac{1}{α} + \frac{1}{α + δ} + \frac{1}{α + 2δ} ) = 1 .

Since, δ = \frac{5}{6}, this leads to the cubic equation for α

54 α^{3} + 81 α^{2} − 15 α − 25 = 0 ,

implying that α = 0.54807171036 … and the other slopes being α + \frac{5}{6} = 1.381405043 … and α + \frac{10}{6} = 2.2147383770. A physicist would call this a mean field approximation.

Alas, we do not live in a perfect world. It so happens that right after State 1, you must have State 2, and right after State 3, you must have State 1, but right after State 2, while usually you have State 3, sometimes you may have State 1. Let c = P (1|2) (and hence P (3|2) = 1 − c), the transition matrix is

( \begin{matrix}0 & 1 & 0 \\ c & 0 & 1 − c \\ 1 & 0 & 0 \end{matrix} ) ,

implying that the ‘steady-state’ relative frequencies of the States 1, 2 and 3, let’s call them x_{1}, x_{2}, x_{3} are

x_{1} = \frac{1}{3 − c} , x_{2} = \frac{1}{3 − c} , x_{3} = \frac{1 − c}{3 − c} .

The equation for δ is now

(x_{1} + x_{2})\frac{1}{δ} + x_{3} \frac{1}{2δ} = 1 ,

leading to

δ = \frac{5 − c}{2(3 − c)} ,

and the equation for α is

x_{1} \frac{1}{α} + x_{2} \frac{1}{α + δ} + x_{3} \frac{1}{α + 2δ} = 1 ,

leading to a certain cubic equation for α.

It would have been nice if c could be determined by a priori reasoning (even a ‘non-rigorous’ and heuristic one), but we don’t know how to do it. By looking at the states between n = 10000 and n = 150000 we found empirically that

c ≈ 0.080 ,

implying the following estimates for the slopes:

0.557 , 1.399 , 2.2419,

with relative frequencies, respectively

0.342, 0.342, 0.315 .

See the output file

http://www.math.rutgers.edu/~zeilberg/tokhniot/oSlaterValez1.txt .

We really hope that the constant c can be identified precisely, possibly as a root of a certain explicit algebraic, (or even a transcendental), equation.

The Maple package. This article is accompanied by a Maple package SlaterValez.txt that can be obtained, along with input and output files, from the front of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/sv.html .

References

[F] Aviezri S. Fraenkel, How to beat your Wythoff’s games’ opponent on three fronts, Amer. Mathematical Monthly 89 (1982), 353-361.

[Sl] Neil J.A. Sloane, OEIS sequence A081145, http://oeis.org/A081145.

[SV] P. J. Slater and W. Y. Velez, Permutations of the positive integers with restrictions on the sequence of differences, II, Pacific Journal of Mathematics 82 (1979), 527-531.

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger .

Written: Iyar 28, 5779 [Aviezri’s Hebrew 90-th birthday] (5 days before June 7, 2019 [Aviezri’s Gregorian 90-th birthday]).