## Wythoff sequences

On November 20, 2007, the Putnam problem of the day was:

The set of all positive integers is the union of two disjoint subsets $\{f(1), f(2), f(3), \dots\}$, $\{g(1), g(2), g(3), \dots\}$, where $f(1) < f(2) < f(3) < \dots$, and $g(1) < g(2) < g(3) < \dots$, and $g(n) = f(f(n))+1$ for $n=1, 2, 3,\dots$. Determine $f(240)$.

Back in November 2007 I could not solve the problem. Now, almost four years later, I will give it another try.

__________

My “solution”:

Let $\mathbb{N} := \{1, 2, 3, \dots\}$ be the set of natural numbers (positive integers). We define $F := \{f(n)\}_{n \in \mathbb{N}}$ and $G := \{g(n)\}_{n \in \mathbb{N}}$. Note that we must have $F \cup G = \mathbb{N}$ and $F \cap G = \emptyset$.

Let $f(1) = 1$. Then, we obtain

$g(1) = f(f(1)) + 1 = f(1) + 1 = 2$.

Next, let $f(2) = 3$ and $f(3) = 4$. Then,

$g(2) = f(f(2)) + 1 = f(3) + 1 = 5$.

Let $f(4) = 6$. Then, we obtain

$g(3) = f(f(3)) + 1 = f(4) + 1 = 7$.

Next, let $f(5) = 8$ and $f(6) = 9$. Then,

$g(4) = f(f(4)) + 1 = f(6) + 1 = 10$.

Next, let $f(7) = 11$ and $f(8) = 12$. Then,

$g(5) = f(f(5)) + 1 = f(8) + 1 = 13$.

Let $f(9) = 14$. Then, we obtain

$g(6) = f(f(6)) + 1 = f(9) + 1 = 15$.

Next, let $f(10) = 16$ and $f(11) = 17$. Then,

$g(7) = f(f(7)) + 1 = f(11) + 1 = 18$.

Let $f(12) = 19$. Then, we obtain

$g(8) = f(f(8)) + 1 = f(12) + 1 = 20$.

Next, let $f(13) = 21$ and $f(14) = 22$. Then,

$g(9) = f(f(9)) + 1 = f(14) + 1 = 23$.

Let us stop iterating here. So far, we have

$\left(f(n)\right)_{n \in \mathbb{N}} = \left(1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, \dots\right)$

$\left(g(n)\right)_{n \in \mathbb{N}} = \left(2, 5, 7, 10, 13, 15, 18, 20, 23, \dots\right)$.

Consulting the On-Line Encyclopedia of Integer Sequences (OEIS), we find out that $\left(f(n)\right)_{n \in \mathbb{N}}$ and $\left(g(n)\right)_{n \in \mathbb{N}}$ are the lower Wythoff (A000201) and upper Wythoff (A001950) sequences, respectively. These two are Beatty sequences generated by the golden ratio $\varphi := \frac{1 + \sqrt{5}}{2}$, as follows

$f (n) = \lfloor n \varphi \rfloor$,     $g (n) = \lfloor n \varphi^2 \rfloor$

where $\lfloor \cdot \rfloor$ is the floor function. Recall that $\varphi^2 = \varphi + 1$, which allows us to write $g (n) = \lfloor n (\varphi + 1) \rfloor$.

The following Python script produces the first twenty terms of the lower and upper Wythoff sequences:

from math import floor
from math import sqrt

# golden ratio
phi = (1 + sqrt(5)) / 2.0

# define function f
def f (n):
return int(floor(phi * n))

# define function g
def g (n):
return int(floor((phi+1) * n))

print "Lower and upper Wythoff sequences:\n"
for n in range(1,21):
print "f(%d) = %d \t g(%d) = %d" % (n, f(n), n, g(n))


This script produces the output:

Lower and upper Wythoff sequences:

f(1) = 1         g(1) = 2
f(2) = 3         g(2) = 5
f(3) = 4         g(3) = 7
f(4) = 6         g(4) = 10
f(5) = 8         g(5) = 13
f(6) = 9         g(6) = 15
f(7) = 11        g(7) = 18
f(8) = 12        g(8) = 20
f(9) = 14        g(9) = 23
f(10) = 16       g(10) = 26
f(11) = 17       g(11) = 28
f(12) = 19       g(12) = 31
f(13) = 21       g(13) = 34
f(14) = 22       g(14) = 36
f(15) = 24       g(15) = 39
f(16) = 25       g(16) = 41
f(17) = 27       g(17) = 44
f(18) = 29       g(18) = 47
f(19) = 30       g(19) = 49
f(20) = 32       g(20) = 52

Finally, we have $f (240) = \lfloor 240 \varphi \rfloor = 388$.

__________

I am not happy with this “solution”. I obviously cheated when I consulted the OEIS. Supposing one is not acquainted with Beatty sequences, is there any hope of solving the problem? If one happens to be acquainted with Beatty sequences and postulates that

$f (n) = \lfloor n r \rfloor$,     $g (n) = \lfloor n s \rfloor$

where $\frac{1}{r} + \frac{1}{s} = 1$, how does one arrive at the conclusion that $r = \varphi$ and $s = \varphi^2$? In other words, what would a proper solution look like?