Proof of a Conjecture of Neil Sloane Concerning Claude Lenormand’s “Raboter” Operation (OEIS sequence A318921)

Doron ZEILBERGER

Dedicated to Neil James Alexander Sloane (born Oct. X, MCMXXXIX) on his turning

1001111 years young (100101 days late)

Yesterday, Neil Sloan gave a great talk([S1]), where among many other fascinating results and open problems, he mentioned a conjecture that he made less than two months ago, concerning the “planing” operation (raboter) introduced in 2004 by sequence enthusiast Claude Lenormand, and described in [S2]. He also mentioned that he has no idea how hard it is to prove, and made a ‘meta-conjecture’ that it may be a ‘low-hanging fruit’. I will now show that both conjecture and meta-conjecture are true.

By examining the definition of http://oeis.org/A318921 in terms of the binary representation of n, it is readily seen that r(n) may be defined recursively as follows

r(n) := \{ \begin{matrix}2 r(n/2) , if n ≡ 0 ( mod 4 ) ; \\ r(\frac{n−1}{2}) , if n ≡ 1 ( mod 4 ) ; \\ r(n/2) , if n ≡ 2 ( mod 4 ) ; \\ 2 r(\frac{n−1}{2}) + 1 , if n ≡ 3 ( mod 4 ) , \end{matrix}

subject to the initial conditions r(0) = 0 and r(1) = 0.

Sloane defined, for, integers k, k ≥ 1,

L(k) := ∑_{n=2^{k}}^{2^{k+1}−1} r(n) ,

and conjectured the following

Fact: L(k) = 2 · 3^{k−1} − 2^{k−1} .

Indeed, breaking up the sum into the four congruence classes modulo four, we have

L(k) = ∑_{n=2^{k}}^{2^{k+1}−1} r(n)

= ∑_{m=2^{k−2}}^{2^{k−1}−1} r(4m) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(4m + 1) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(4m + 2) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(4m + 3)

= ∑_{m=2^{k−2}}^{2^{k−1}−1} 2 r(2m) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m + 1) + ∑_{m=2^{k−2}}^{2^{k−1}−1} ( 2 r(2m + 1) + 1 )

= 3 ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m + 1) + 2 ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m + 1) + ∑_{m=2^{k−2}}^{2^{k−1}−1} 1

= 3 ( ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m) + ∑_{m=2^{k−2}}^{2^{k−1}−1} r(2m + 1)) + 2^{k−2}

= 3 ( ∑_{m=2^{k−1}}^{2^{k}−1} r(m) ) + 2^{k−2} = 3 L(k − 1) + 2^{k−2} .

Hence the sequence L(k) satisfies the first-order inhomogeneous recurrence with constant coefficients

L(k) − 3 L(k − 1) = 2^{k−2} .

But R(k) := 2 · 3^{k−1} − 2^{k−1} also satisfies the same recurrence, i.e.

R(k) − 3 R(k − 1) = 2^{k−2} ,

(check!), and the fact follows by induction on k, since it is true for k = 1.

References

[S1] N.J.A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences, talk given in Rutgers University Experimental Mathematics Seminar, Nov. 15, 2018.

part 1: https://vimeo.com/301216222 ; part 2: https://vimeo.com/301219515 .
slides: http://sites.math.rutgers.edu/~my237/expmath/EMNov2018.pdf .

[S2] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, Sequence A318921,

http://oeis.org/A318921 .

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.

Nov. 16, 2018.