...... .
..
Part i: Constructing these four sequences is mostly
a matter of carefully following directions and avoiding careless mistakes.
The master numbers M=11, 23, 29, and 37 lead to the four sequences
shown below.
..[11].. 1—>5(1)—>3(1)—>1(3)
..[23].. 1—>11(1)—>3(2)—>5(2)—>9(1)—>7(1)—>1(4)
..[29].. 1—>7(2)—>11(1)—>9(1)—>5(2)—>3(3)—>13(1)—>1(4)
..[37].. 1—>9(2)—>7(2)—>15(1)—>11(1)—>13(1)—>3(3)—>17(1)—>5(2)—>1(5)
Part ii: We first observe that the terms in our sequence
can be no larger than 561. To see why this must be the case, let l
be any term of the sequence. If k is the previous term, then
we obtain l by subtracting 1123–k and then dividing
out any factors of 2 from the result. Since all the terms of the sequence
are positive we know that 1123–k is at most 1122. Furthermore,
k is odd so that 1123–k is even, implying that
there is always at least one factor of 2. Hence l is less than
or equal to 1122/2=561.
......
Now let k be the term immediately preceding 5. Then we obtain
5 by subtracting 1123–k and dividing out all the factors
of 2. Suppose there are exactly n factors of 2 that are divided
out, meaning that (1123–k)/(2^n)=5, or k=1123-5(2^n).
At first it appears that we don't have enough information to compute k.
The table below lists the possibilities for n (which is the number
of factors of 2 we divide out) along with the corresponding value of k
n= |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
... |
k= |
1118 |
1113 |
1103 |
1083 |
1043 |
963 |
803 |
483 |
–157 |
... |
However, recall that that the terms of the sequence are positive odd integers no greater than 561. Hence the only possibility is k=483, which must be the term preceding 5.
Part iii: Suppose that our sequence has the form 1—>k(a)—>1(b) for some master number M. This implies that M–1=(2^a)k and M–k = 2^b. Multiplying the second equation by 2^a, subtracting the first equation from the result, and solving for M gives
M = (2^(a+b)–1) / (2^a–1).
One way to ensure that M is an integer is to choose b=a, so that M=2^a+1. But this leads to the sequence 1—>1(a)—>1(a), which repeats too quickly. The next best option is to try b=2a, leading to M=2^(2a)+2^a+1. Substituting various values for a gives M=7, 21, 73, and 273. The latter gives one possible solution over 100. We could also take a=2 and b=8, yielding M=341.
Part iv: Let M be an odd composite number, and let p be an odd prime divisor of M. Note that p is less than M/2 (in fact p=M/3 at most), so in theory it could appear in the sequence. However, we will demonstrate that no term of the sequence is divisible by p, which will show that our sequence is not complete. We proceed by induction. The first term is 1, which is clearly not divisible by p. Now let k be any term of the sequence, and assume that p does not divide k. We will prove that p does not divide the next term l either. We know that M–k=(2^n)l, which can be rewritten as M–(2^n)l=k. Recall that M is divisible by p. If l were also divisible by p, then the left-hand side would be a multiple of p, implying that k would be divisible by p also, contrary to hypothesis. We conclude that l is not divisible by p either. Hence no term in the sequence is divisible by p, so our sequence cannot be complete.
Part v: Adding up the numbers above the arrows in each
of the sequences from the first part yields totals of 5, 11, 14, and 18
for the master numbers M=11, 23, 29, and 37, respectively. These
numbers appear to be just about half the value of the master number. In
fact, the sum is exactly equal to (M–1)/2 in each case,
so we conjecture that this expression gives the total for any complete
sequence.
......
We will first illustrate the proof using M=11. Once again we
list the terms in the sequence, but this time we divide out factors of
2 one at a time, showing all intermediate numbers along the way:
1—>10—>5—>6—>3—>8—>4—>2—>1.
Next we list all the instances where we divided out a factor of 2.
10—>5,...... 6—>3,......8—>4, ...... 4—>2,...... 2—>1
Observe that the right-hand numbers, in boldface, consist of precisely
the numbers from 1 to 5, in some order.
......
We claim that the same sort of phenomenon will occur in general. Suppose
we list all the instances in which we divide out a factor of 2, as we
did above, and then examine the right-hand numbers. The largest possible
result will be (M–1)/2, since the largest possible left-hand
number is (M–1). Of course, the smallest right-hand number
will be 1, since all terms are positive integers. Furthermore, all the
right-hand numbers will be different, since the sequence has not yet begun
to repeat. So there can be at most (M–1)/2 pairs in which
we divide out a factor of 2. Finally, we know that all possible pairs
appear, since we are given that our sequence includes all possible odd
numbers. We deduce that we must have divided out precisely (M–1)/2
factors of 2 before the sequence began repeating. This completes the proof.
......
By the way, there is a way to modify the conjecture so that is does hold
for any master number M. Can you discover the correct
statement? (Hint: in the sequence for M=73 many of the
odd integers from 1 to 35 are missing, such as 3. Try creating another
sequence starting with 3 instead of 1 to include the missing numbers.)
Can you prove your more general conjecture? Try mimicking the proof above.