A periodic recurrence relation is one containing a cycle of infinitely
repeating elements.
Sums of Powers of Two
Ponder this puzzle, August, 2007:
Define f(0)=1 and f(n) to be the number of different ways n can be
expressed as a sum of integer powers of 2 using each power no more than
twice.
Henceforth I will refer to such a partition of n as a "hyper-binary"
partition.
For example, f(10)=5 since there are five different ways to express 10:
1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8.
Describe, in a single sentence, the sequence {f(n)/f(n-1)} for positive
integer n.
Show your proof to this sentence.
. . . . . . this needs to be edited to clean it up a bit. Code
fragments need to be put in monospace font and indented properly.
Initial research
Using Excel, I converted numbers 0,1,2,... to base three, and then interpreted
the result as "hyper-binary", which means each place had a binary place value,
but the digits can range from 0 to 2 instead of just 0 to 1. This allowed me to
cycle through all of the ways to express numbers as sums of powers of 2 using
each power no more than twice. I counted up the number of occurrences of each
number, and then searched in OEIS for the resulting sequence. There, I found the
following:
f(n) is OEIS A002487(n+1) ( http://www.research.att.com/~njas/sequences/A002487
), which is described in OEIS as
Stern's diatomic series: a(0) = 0, a(1) = 1; for n >= 0, a(2n) = a(n), a(2n+1) =
a(n) + a(n+1).
The second comment listed in the description of this sequence describes the
sequence {a(n)/a(n+1)} as follows:
"a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once"
which struck me as an interesting statement very close to the single-sentence
description sought by this puzzle.
Understanding the Recurrence Relation
Now we see Stern's diatomic series is the same as our series except the index
is off by one. Thus we have discovered the recurrence relation that
describes the number of hyper-binary partitions of n, namely
f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1)
But why should this be the case?
First, let's consider an arbitrary hyper-binary partition, A, of an odd
number, 2n+1. Clearly, A contains a single 1, because otherwise it could
not be odd. By deleting this 1, and dividing all the remaining elements in
half, we're left with a unique partition, A', of n. So we see there is a
one-to-one correspondence between hyper-binary partitions of 2n+1 and
hyper-binary partitions of n, i.e. f(2n+1)=f(n)
Next, let's consider an arbitrary hyper-binary partition of an even number,
2n. If the partition contains a 1 then it contains two 1's, because 2n is
even. Let's consider both cases. We'll let B be an arbitrary
partition of 2n that does not contain any 1's, and we'll let C be an arbitrary
partition of 2n that contains two 1's.
Since B contains no 1's, we can add a single 1 to it to form partition B', so
there is a one-to-one correspondence of partitions of 2n without any 1's and
partitions of 2n+1.
Since C contains two 1's, we can delete a single 1 from it to form partition
C', so there is a one-to-one correspondence of partitions of 2n with two 1's and
partitions of 2n-1.
Thus we see f(2n) = f(2n+1) + f(2n-1).
Well, we have already seen that f(2n+1)=f(n), and it's a short step to also
realize that f(2n-1)=f(n-1), so we have our result for this case, namely
f(2n) = f(n) + f(n-1), which proves the result.
Puzzle Solution
The corresponding statement for our question is, "The sequence {f(n)/f(n-1)}
contains all the reduced nonnegative rationals exactly once."
A constructive proof of the statement will show (1) that f(n) and f(n-1) are
coprime for all n, and (2) a function arcf exists such that given any positive
coprime integers x,y arcf(x,y) exists, and f(arcf(x,y)-1)=x and f(arcf(x,y))=y,
and for positive n, arcf(f(n-1),f(n))=n.
I start by proving Lemma 1, which provides a recursive definition of f: f(0)=1,
for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1).
Then I prove Lemmas 2 and 3, which prove the properties of f and arcf,
essentially completing the proof. That arcf exists, i.e. it is defined for all
coprime x,y, the "contains all reduced nonnegative rationals" part of the
statement is proved. Since both f and arcf are injective, and each one is, in a
sense, the inverse of the other, they are both bijective in that sense, which
completes the proof of the "exactly once" part of the statement. The remainder
of this document provides these proofs in detail.
Lemma 1
f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1)
I will refer to a "restricted partition" of n as a partition of n into powers of
2 using each power no more than twice.
In overview, the first part of this proof will show that any restricted
partition of an odd number 2n+1 contains a single "1", so it can be converted to
a restricted partition of n by deleting the 1 and dividing every other number in
half. Conversely, a restricted partition of n can be converted to a restricted
partition of 2n+1 by doubling every number and adding a "1".
The second part of this proof will show that every restricted partition of an
even number has either two 1's or zero 1's. If it has two 1's, it can be
converted to a restricted partition of the next-lower odd number by deleting one
of the 1's. If it has zero 1's, it can be converted to a restricted partition of
the next-higher odd number by adding a "1". Conversely, every odd restricted
partition can be converted to a restricted partition of the neighboring lower
even number by deleting a 1, and it can be converted to a restricted partition
of the next higher even number by adding a 1. Then, by applying the first
result, the result follows.
First part, in detail: Let a0, a1, a2,... represent the number of times 1, 2, 4,
... appear in a given restricted partition of 2n+1.
Since 2n+1 is odd, a0=1. Let b0=a1, b1=a2, ... Now b0, b1, b2, ... represents a
corresponding restricted partition of n.
Now let b0, b1, b2,... represent any restricted partition of n. Let a0=1, a1=b0,
a2=b1,... represent a corresponding restricted partition of 2n+1.
Thus the number of restricted partitions of 2n+1 is equal to the number of
restricted partitions of n.
Second part, in detail: Let a0, a1, a2,... represent a restricted partition of
2n. Note that a0=0 or a0=2. Since b0=1, b1=a1, b2=a2,... is a restricted
partition of an odd number neighboring 2n, we see that every restricted
partition of an even number 2n corresponds to a restricted partition of one of
2n's odd neighbors. Conversely, let b0=1, b1, b2,... be a restricted partition
of 2n-1 and let c0=1, c1, c2,... be a restricted partition of 2n+1. A one-to-one
mapping can be made from the union of the sets of b0,b1,b2,... restricted
partitions and c0,c1,c2,... restricted partitions by simply changing b0 to 2,
and changing c0 to 0. Thus the number of restricted partitions of 2n is equal to
the sum of the number of restricted partitions of 2n-1 and the number of
restricted partitions of 2n+1. Using "f(n)" notation,
f(2n) = f(2n+1) + f(2n-1)
Now, applying the result from the first part of the proof to each of the terms
on the right-hand side of this equation,
f(2n) = f(n) + f(n-1)
Lemma 2
f(n) and f(n-1) are coprime
Proof:
Outline of the proof: Assume the opposite for contradiction. Let n be the
smallest positive integer such that f(n) and f(n-1) are not coprime. We know n
is at least 2 because f(1) and f(0) are both 1 and thus coprime. Then I will
show that f([n/2]) and f([n/2]-1) are also coprime contrary to our assumption.
Detailed proof: Suppose f(n) and f(n-1) share a common factor, k. Let r=[n/2].
Case 1: If n is even then f(n) = f(2r), and f(2r) = f(r) + f(r-1) by Lemma 1.
f(n-1) = f(2r-1), and f(2r-1) = f(r-1) by Lemma 1.
Case 2: If n is odd then f(n) = f(2r+1), and f(2r+1) = f(r), by Lemma 1.
f(n-1) = f(2r) = f(r) + f(r-1), by Lemma 1.
Thus, in either case, f(r)+f(r-1) divisible by k, and either f(r) or f(r-1) is
divisible by k, so f(r-1) and f(r) are both divisible by k. r is positive and
smaller than n, contradicting the choice of n as the smallest positive integer
that makes f(n) and f(n-1) coprime.
Lemma 3
The arcf algorithm presented here (written in VBA) is such that given any
positive coprime integers x,y arcf(x,y) exists, and f(arcf(x,y)-1)=x and
f(arcf(x,y))=y. In addition, arcf(f(n-1),f(n))=n for all positive n.
Function arcf(ByVal x As Long, ByVal y As Long) As Long
Dim z As Long, result As Long
If x < 1 Or y < 1 Then Exit Function
z = 1
Do While x <> 0
If x >= y Then
x = x - y
result = result + z
Else
y = y - x
End If
z = z * 2
Loop
arcf = result
End Function
First, an overview of how arcf works. It repeatedly replaces the larger of x,y
with |x-y|, keeping a binary string to "remember" which value was replaced. This
continues until x=y, in which case x is replaced by the difference, 0, and the
loop terminates. The binary string contains a "1" for every time x was replaced
by the difference, and "0" for every time y was replaced by the difference. The
binary string is interpreted as a base 2 number, with the first bit in the 1's
place, the second in the 2's place, etc.
Proof of the first assertion, that arcf(x,y) exists as long as x and y are
positive coprime integers: This is true because each iteration of the loop
reduces x+y by some nonzero amount, never allowing x or y to become negative.
This can't continue for ever, because at some point x+y would become zero.
Before that happens, x would have to be zero, and this ends the loop. So no
matter what input values are given, arcf terminates. As a practical matter, it
terminates even if x and y aren't positive (it returns zero) and even if x and y
are not coprime (it returns arcf(x/GCD(x,y),y/GCD(x,y))).
Proof of the second assertion that f(arcf(x,y)-1)=x and f(arcf(x,y))=y
Though this proof is a bit sketchy, you can think of it as either an induction
proof or better yet a proof by contradiction. Suppose the second assertion is
not always true. Then there exists an x,y for which it isn't true and x+y is
minimal. Thus, for smaller x+y it is true, and this is used to show that it is
also true for this x+y.
The following is evident from the algorithm when x,y are coprime:
if x=y then arcf(x,y) = 1
if x>y then arcf(x,y) = 2*arcf(x-y,y)+1
if x<y then arcf(x,y) = 2*arcf(x,y-x)
Thus if x>y,
f(arcf(x,y)-1) = f(2*arcf(x-y,y)) by the algorithm
= f(arcf(x-y,y))+f(arcf(x-y,y)-1) by Lemma 1
= y + (x-y)
= x
f(arcf(x,y)) = f(2*arcf(x-y,y)+1)
= f(arcf(x-y,y))
= y
And if x<y,
f(arcf(x,y)-1) = f(2*arcf(x,y-x)-1)
= f(arcf(x,y-x)-1)
= x
f(arcf(x,y)) = f(2*arcf(x,y-x))
= f(arcf(x,y-x))+f(arcf(x,y-x)-1)
= (y-x) + x
= y
Proof of the third assertion that arcf(f(n-1),f(n))=n, using a similar technique
as the second assertion, above. Suppose n is the largest number for which
arcf(f(k-1),f(k))=k whenever k<=n.
arcf(f(2n),f(2n+1)) = arcf(f(n)+f(n-1),f(n)) by Lemma 1
= 2*arcf(f(n-1),f(n))+1 by the algorithm
= 2n+1
arcf(f(2n-1),f(2n)) = arcf(f(n-1),f(n)+f(n-1))
= 2*arcf(f(n-1),f(n))
= 2n
Conclusion and general comments
A non-recursive implementation of the f function in VBA, called "frac1" here,
is:
' f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1)
Function frac1(ByVal n As Long) As Long
Dim x As Long, y As Long, z As Long
x = 0: y = 1
If n < 0 Then Exit Function
If n < 65536 Then z = 32768 Else z = 1073741824
Do While z > 0
If n >= z Then x = x + y: n = n - z Else y = x + y
z = z \ 2
Loop
frac1 = y
End Function
This problem was one of the more delightful problems that has ever appeared in
"Ponder This" because of the simplicity yet richness of the functions f and arcf.
Thank you for presenting it.
The reason f(n) and f(n-1) are coprime is the same as the reason every pair of
adjacent Fibonacci numbers are coprime -- because the recursion formula that
defines the sequence is, in effect, the Euclidean algorithm, and the first two
elements of the sequence are coprime -- which is true for both this sequence, f,
and the Fibonacci sequence.
I was initially disappointed to find such a full detailed description of the
function, f, in OEIS. At first, I was tempted to send you an email saying simply
A002487, but then I realized that a proof was needed. I always prefer a
constructive proof to an existence proof, so that led me to try to find where in
the sequence of f(n)/f(n-1) any particular rational number might be found. The
description of this sequence in OEIS suggests writing out a pyramid of values of
f in a certain way, but I found it was much more instructive to write a "tree"
of values of f. The tree is the same as the pyramid, but it's organized so that
the left branch of every node brings you to an identical-value node. The binary
sequence of branch selections (left=0, right=1) corresponds roughly to the value
of arcf(x,y).
Finding arcf was a big breakthrough, because in so doing, I proved what I
thought was the major part of the statement, that every rational is represented.
It turned out that the "exactly once" part of the proof was a bit harder. For
that, I had to show not only that f(arcf(x,y)-1)=x and f(arcf(x,y))=y but also
that arcf(f(n-1),f(n)) = n, which wouldn't be the case if f(n-1),f(n) appeared
in sequence more than once.
Additional information from OEIS
If the terms are written as an array:
1
1, 2
1, 3, 2, 3
1, 4, 3, 5, 2, 5, 3, 4
1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5
1, 6, 5, 9, 4,11, 7,10, 3,11, 8,13, 5,12, 7, 9, 2, 9, 7,12, 5,13, 8,11, 3,10,
7,11, 4, 9, 5, 6
then the sum of the k-th row is 3^(k-1), each columns is an arithmetic
progression, and the steps are nothing but the original sequence.
Recursive formula for f(n):
f(n+1) = (2k+1)f(n) - f(n-1) where k = [f(n-1) / f(n)] is the largest integer
smaller than or equal to f(n-1)/f(n)
Internet References
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf
Related
pages in this website
Counting
