Cayley problem 23, 1997

January 22, 2020

Given the set $S=\{1, 2, 3, 5, 8, 13, 34, 55\}$ , how many integers $3 \leq n \leq 89$ cannot be written as the sum of exactly two different elements of $S$ ?

The numbers in $S$ are Fibonacci numbers, so we may guess that some magic is involved here. Indeed, we vaguely remember something about numbers having unique representations as sums of Fibonacci numbers. If the sum of any two Fibonacci numbers is a unique integer, the job of counting possibilities would be a lot simpler. Perhaps we can prove this. Here are the first 10 Fibonacci numbers:

$n$	1	2	3	4	5	6	7	8	9	10
$F_n$	1	1	2	3	5	8	13	21	34	55

Set $S$ contains $F_2$ to $F_{10}$ . Notice that $F_1$ is not included in $S$ . We want to prove that the sum of any two different Fibonacci numbers $F_m$ and $F_n$ with $m,n > 1$ is unique.

Let $m < n$ . There are two situations to think about. First, if $m = n-1$ then

$F_m + F_n = F_{n-1} + F_n = F_{n+1}$

by definition of Fibonacci numbers. And if $m<n-1<n$ it is clear that

$F_n < F_m + F_n < F_{n+1}.$

Either way, $F_m < F_m+F_n \leq F_{n+1}$ .

Suppose the same number $q$ can be written as the sum of two different Fibonacci numbers in two different ways:

$q = F_m + F_n = F_{m'} + F_{n'}.$

There is no loss if we suppose $m<n$ and $m' < n'$ . Since $q = F_m+F_n$ , we have

$F_n < q \leq F_{n+1}.$

And since $q = F_{m'} + F_{n'}$ , we have

$F_{n'} < q \leq F_{n'+1}.$

Since $q$ is sandwiched between two consecutive Fibonacci numbers, it must be that $F_n=F_{n'}$ and $F_m = F_{m'}$ . For Fibonacci numbers greater than $F_1$ , these imply $m=m'$ and $n=n'$ .

Now we can count. Imagine all the possible sums of two elements of $S$ organized into a $9\times 9$ table. We remove the sums of the form $a + a$ : this amounts to removing the diagonal which has 9 element. Then we divide by two to remove one of the upper or lower triangles of the table, because we don’t want to count both $a+b$ and $b+a$ . This leaves

$\frac{81 - 9}{2} = 36.$

There are 36 integers expressible as the sum of two elements of $S$ . Smallest is 3, largest is 89. In the range $3\leq n \leq 89$ there are $89-3+1= 87$ numbers. The total number of integers not expressible is therefore 87 - 36 = 51.

Let’s check this by Racket programming.

First we create a list of all the numbers expressible as the sum of two different elements of $S$ . We use a nested for-loop with a when-clause to catch the cases we are interested in.

(define cayley-23-list (list 1 2 3 5 8 13 21 34 55))

(define expressibles
  (for*/list ((Fm cayley-23-list)
              (Fn cayley-23-list)
              #:when (> Fm Fn))
    (+ Fm Fn)))

And then we filter the range of numbers from 3 to 89, keeping only the ones that are not in the expressible list. Getting the length of this filtered range solves the problem.

(define (solve-cayley-23)
  (length
   (filter
    (lambda (n)
      (not (member n expressibles)))
    (range 3 90))))

Run it in the Racket interactive REPL

> (solve-cayley-23)
51

There we go!