%sv.tex:  Guessing the Elusive Patterns in the Slater-Valez sequence (aka OEIS A081145) 
%%a Plain TeX file by Shalosh B. Ekhad and Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\C{{\cal C}}
\def\N{{\cal N}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\M{{\cal M}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\centerline
{\bf  Guessing the Elusive Patterns in the Slater-Valez sequence (aka OEIS A081145) }
\bigskip
\centerline
{\it Shalosh B. EKHAD and Doron ZEILBERGER}
\bigskip
\qquad\qquad\qquad\qquad\qquad{\it Dedicated to Aviezri S. Fraenkel (b. 28 Iyar, 5689) on his 90-th birthday.}
\bigskip

{\bf 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\leq i<n$
{\bf and} $|a(n)-a(n-1)|$ differs from all  $|a(i)-a(i-1)|$ for $1<i<n$.''

Using the ``{\it mex}'' function 
($mex(S)$ is the smallest positive integer {\bf not} in $S$),
$a(n)$ may be defined by $a(1)=1$, $d(1)=1$ and
$$
a(n):= mex \, \left ( \{ a(i)\,|\,  1 \leq i<n \} \cup  \{ a(n-1)+d(i)\,|\,  1 \leq i<n \} \cup  \{ a(n-1)-d(i)\,|\,  1 \leq i<n \} \right ) \quad ,
$$
$$
d(n):=|a(n)-a(n-1)| \quad .
$$

In [SV] it is proved that the sequence $\{a(n)\}$ is a {\bf 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

{\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/svPics/sv1.html} \quad .

Being experimental mathematicians, we were wondering whether
one can deduce these slopes using `back of the envelope heuristic arguments'. Then 
{\bf 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 ``{\it mex}'', shows up.
It so happened that Fraenkel's $90$-th Hebrew birthday is {\bf 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.

{\bf  Aviezri Fraenkel}

In addition to his many other accomplishments, Aviezri is one of the founding fathers 
of {\bf 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 {\it Wythoff's game},
that Fraenkel and his collaborators extended in many ways. A search of {\tt MathSciNet} for
the papers authored by Fraenkel that include the key-word {\bf Wythoff},
comes up with 25 hits! We will only mention one of them [F]. That paper  includes a short bio, whose
last sentence reads

\qquad {\it ``... 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''.}

{\bf The original Wythoff's Game}

Consider two piles, containing, say, $x$ and $y$ pennies (so the {\bf initial position} is $(x,y)$) .
Players take turn executing {\bf 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), \dots, (0,y) \quad ; \quad  (x,y-1), (x,y-2), \dots, (x,0) \quad,
$$
or the {\bf same} number of pennies from both piles, leading to one of the positions (w.l.o.g, by symmetry we can assume that $x \leq y$)
$$
(x-1,y-1), (x-2, y-2), \dots, (0,y-x) \quad .
$$

The player to make the {\bf last} move is the {\bf 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 {\bf perfect} play what are the {\bf losing} positions? (aka $P$ positions, the {\bf Previous} player wins.)

Obviously, the positions   $(0,y)$ or $(y,y)$ ( $y>0$),  are all winning positions (aka as $N$ positions, the {\bf Next} player wins).
Since one legal move can lead to the $P$ position $(0,0)$. The smallest position $(x,y)$, with $x \leq y$,that is {\bf 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 {\bf not} of that form is $(3,5)$ (and $(5,3)$). Etc.

A moment's thought would convince the reader that the set of {\bf losing positions} $(x,y)$ with $x \leq y$, are
$$
(A(n),B(n)) \quad,
$$
where $A(0)=0, B(0)=0$ and the sequences $A(n)$ and $B(n)$ are defined {\bf recursively}, for $n>0$,  by
$$
A(n)\,=\, mex\, \left ( \{ A(i)\, | \, 1 \leq i<n\} \cup  \{ B(i)\, | \, 1 \leq i<n\} \right ) \quad , 
$$
$$
B(n)=A(n)+n \quad .
$$
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]\} \quad ,
$$
and, of course, their reverses, $[2,1],[5,3], \dots$.

If you plot the points  $(n,A(n))$ for say, $n\leq 20$, you would immediately notice an approximate straight line with a certain slope.
Let's call is $\alpha$. This leads to an {\bf ansatz} 
$$
A(n)=\lfloor \alpha n \rfloor \quad , \quad B(n)=\lfloor (1+\alpha) n \rfloor \quad ,
$$
for {\it some} number $\alpha$ (the slope), yet to be determined. Since the two sequences $A(n)$, $B(n)$ {\it exhaust}
everything and their `densities' are, respectively $1/\alpha$ and $1/(1+\alpha)$, our $\alpha$ (if it exists) must satisfy
$$
\frac{1}{\alpha} \, + \,  \frac{1}{\alpha+1} \, = \, 1 \quad,
$$
leading to the fact that $\alpha$ is the {\bf golden ratio}, $\phi=\frac{1+\sqrt{5}}{2}$.

Now this is not yet a proof. But it turns out that one can  prove that indeed
$A(n)=\lfloor \phi n \rfloor$ and hence $B(n)=\lfloor (1+\phi) n \rfloor$. Why won't {\it you} do it!


{\bf 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 {\it a priori} these slopes like we did for the Wythoff sequence?

Examining the sequence $a(n)$, we call a positive  integer $n$ 

$\bullet$ State $1$ if $a(n)/n \leq 1$ \quad ;

$\bullet$ State $2$ if $ 1< a(n)/n \leq 2$ \quad ;

$\bullet$ State $3$ if $ 2< a(n)/n $ \quad .

In an ideal world, their relative frequencies would each be {\bf exactly} $\frac{1}{3}$, and the states
would cycle through $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$, and the slopes would be,
respectively $\alpha$, $\alpha+\delta$, $\alpha+2\delta$, for some numbers $\alpha$ and $\delta$ to be determined.
Under this ideal situation, $\delta$ is easy.

The `scatter-plot' of the set of points  $(n,d(n))$ (for $n>0$) falls naturally into two lines, of slope $\delta$ and $2 \delta$, but the
transitions $1 \rightarrow 2$ and $2 \rightarrow 3$ both give rise to slope $\delta$, while
$3 \rightarrow 1$ gives rise to slope $2\delta$. Assuming that $\{d(n)\}$ is a permutation of the
integers, by a density argument, we must have
$$
\frac{2}{3} \cdot \frac{1}{\delta} \, + \,\frac{1}{3} \cdot \frac{1}{2\delta}  \, = \, 1 \quad,
$$
leading to the exact value $\delta=\frac{5}{6}$. Since the slopes of states $1$, $2$ and $3$ are
$\alpha$, $\alpha+\delta$, $\alpha+2\delta$, respectively, in an ideal world we would have
$$
\frac{1}{3} \left ( \,\frac{1}{\alpha} \, + \,\frac{1}{\alpha+\delta} \, + \,\frac{1}{\alpha+2\delta} \, \right ) \, = \, 1 \quad .
$$
Since, $\delta=\frac{5}{6}$, this leads to the {\bf cubic equation} for $\alpha$
$$
54\,{\alpha}^{3}+81\,{\alpha}^{2}-15\,\alpha-25 \, = \, 0 \quad ,
$$
implying that $\alpha=0.54807171036\dots$ and the other slopes being $\alpha+ \frac{5}{6}=1.381405043\dots$ and 
$\alpha+ \frac{10}{6}=2.2147383770$. A physicist would call this a {\it mean field approximation}.


{\bf Alas}, we do not live in a perfect world. It so happens that 
right after State $1$, you {\bf must} have State $2$,
and right after State $3$, you {\bf must} have State $1$,
but right after State $2$, while {\it usually} you have State $3$, {\it sometimes} you may have State $1$.
Let $c=P(1|2)$ (and hence $P(3|2)=1-c$),
the {\bf transition matrix} is
$$
\left ( \matrix { 0 & 1 & 0 \cr c & 0 & 1-c \cr 1 & 0 & 0} \right ) \quad,
$$
implying that the `steady-state' {\bf 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} \quad , \quad
x_2 = \frac{1}{3-c} \quad , \quad
x_3 = \frac{1-c}{3-c} \quad .
$$

The equation for $\delta$ is now
$$
(x_1+x_2) \frac{1}{\delta} \, + \,x_3 \frac{1}{2\delta} \, = \, 1  \quad,
$$
leading to
$$
\delta=\frac{5-c}{2(3-c)} \quad ,
$$
and the equation for $\alpha$ is
$$
 x_1 \,\frac{1}{\alpha} \, + \, x_2\,\frac{1}{\alpha+\delta} \, + \, x_3 \frac{1}{\alpha+2\delta} \, = \, 1 \quad ,
$$
leading to a certain cubic equation for $\alpha$.

It would have been nice if $c$ could be determined by {\it 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  \approx 0.080 \quad ,
$$
implying the following estimates for the slopes:
$$
0.557 \quad , \quad 1.399 \quad , \quad    2.2419,
$$
with relative frequencies, respectively
$$
0.342, 0.342,    0.315 \quad .
$$

See the output file

{\tt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/oSlaterValez1.txt} \quad .


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.

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

{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/sv.html} \quad .

{\bf References}

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

[Sl] Neil J.A. Sloane, {\it OEIS sequence A081145}, {\tt http://oeis.org/A081145}.

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

\bigskip
\hrule
\bigskip
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. \hfill\break
Email: {\tt ShaloshBEkhad at gmail dot com}   \quad .
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail  dot com}   \quad .
\bigskip
\hrule
\bigskip
{\bf Exclusively published in the Personal Journal of Shalosh B.  Ekhad and Doron Zeilberger \quad .}
\bigskip
\hrule
\bigskip
Written: Iyar 28, 5779 [Aviezri's Hebrew 90-th birthday] (5 days before June 7, 2019 [Aviezri's Gregorian 90-th birthday]).
\end


