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?

About these ads

Tags: Beatty Sequences, Golden Ratio, Integer Sequences, Putnam problem of the day, Python, Wythoff Sequences

This entry was posted on August 21, 2011 at 21:19 and is filed under Puzzles, Python. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Wythoff sequences”

D. Eppstein Says:
August 21, 2011 at 22:47 | Reply
If you happen to be familiar with Beatty sequences, the part about partitioning the integers into two monotonic sequences should be a tip-off that they might be involved (or, if not, that you should do something with the Lambek–Moser theorem, but first try Beatty because it’s simpler).

And once you guess that the answer comes from Beatty sequences, i.e. that f(n) = floor(rx) and g(n) = floor(sx) for 1/r+1/s=1, then the functional equation g(n)=f(f(n))+1 translates into the equation s=r^2 — the floor and +1 parts of the functional equation are irrelevant for large n. Now all you have to do is solve the two simultaneous equations s=r^2 and 1/r+1/t=1, and check that the simplifying assumptions you made are valid i.e. that the Beatty sequences you get from this solution actually solve the original problem.

Rod Carvalho

Wythoff sequences

Like this:

One Response to “Wythoff sequences”

Leave a Reply Cancel reply

Follow “Rod Carvalho”