OK, hands up who thought there was ever gonna be a second NotCH?
We’re not really a puzzle sort of guy, and base ten puzzles in particular tend to bore us. So, this is unlikely to be a regular thing. Still, the following question came up in some non-puzzle reading (upon which we plan to post very soon), and it struck us as interesting, for a couple reasons. And, a request to you smart loudmouths who comment frequently:
Please don’t give the game away until non-regular commenters have had time to think and/or comment.
Start by writing out a few terms of the standard doubling sequence:
1, 2, 4, 8, 16, 32, 64, etc.
Now, look at the sequence of final digits: 1, 2, 4, 8, 6, 2, 4, etc. If you keep going, is there a pattern? Can you prove it?
Next, look at the sequence of first digits: 1, 2, 4, 8, 1, 3, 6, etc. If you keep going, is there a pattern? Can you prove it?
Thanks to the all the commenters. Leaving aside commenter Glen’s pondering on Benford’s Law, we’ll summarise the solution to the intended puzzle and, more interesting to us, the origins and the purpose of the puzzle.
The “puzzle” appears in Teaching Mathematics at Secondary Level, a book by by Tony Gardiner, who also coauthored the great book of mathematical problems that we discussed here. Written in 2016, TMSL is Gardiner’s guide/manifesto to teaching the English Mathematics Curriculum. Being such a commentary, Gardiner’s book does not always stand alone so well, but it has some great stuff, and we’ll post some excerpts in the near future.
Gardiner introduces the doubling sequence when discussing a Curriculum requirement for early secondary school, for students to “reason deductively with number” (p 44). He notes that this requirement is already problematic when considering simple numerical patterns:
“At present the patterns pupils meet are often chosen in a way that misleads everyone into thinking that
patterns that seem genuine, always are genuine.
This makes it hard for pupils to discover the need for proof.”
Then to illustrate, Gardiner lists the first seventeen terms in the doubling sequence (beginning with 2, and without the stupid colours):
2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072
He then extracts the sequences of last (units) digits and first digits:
2 4 8 6 2 4 8 6 2 4 8 6 2 4 8 6 2
2 4 8 1 3 6 1 2 5 1 2 4 8 1 3 6 1
So, two apparent patterns. Of course the existence of the first pattern is easy to prove: the units of a number 2N only depends upon the units of N. That implies the units in the doubling sequence must continue to cycle forever.
But, the sequence of first digits is much different, since no such simple proof for the apparent pattern exists. And so the first point, and Gardiner’s point, is
“Somehow pupils need to learn that what looks like a pattern may not be a pattern at all!”
That is a hugely important message. And, that is where Gardiner leaves the “puzzle”, and goes on with his guide/manifesto.
To finish off, we’ll indicate why there appears to be a pattern in the second sequence, and when the pattern disappears. As mystery commenter Gavin noted, the key is 210 = 1024 ≈ 1000. So, unless we’re unlucky, the first digit of 210N (which is the number ten spots along from N in the doubling sequence) will be the same as the first digit of N.
To see what needs to happen to be unlucky, suppose we have a number N with beginning digits ABCD… Then, multiplying each of the digits separately by 1024, the digits of 1024N are determined from summing
A 0 2A 4A
B 0 2B 4B
C 0 2C 4C
D 0 2D 4D
So, the first digit of 1204N will be A unless the 2A + C in the third column carries over, and the B in the second column is 8 or 9 accordingly. Or, the 4A + 2B + D in the fourth column is enough for a carry over and … . And so on. Of course, unless God is playing with our heads, this is bound to happen eventually. Which it does:
236 = 68,719,476,736
The first-digit pattern finally breaks at 246, with a 7 instead of a 6.
This is a rewriting and filling in of the mystery Student’s proof in the comments, that there can be no first digit pattern in the doubling sequence. It is long, but hopefully readable step by step.
To set things up, we’re asking whether it is possible for the first digits of the doubling sequence to eventually repeat every spots:
*) If is huge then and always have the same first digit.
(The “huge” here means that we’re allowing it to take a while for the pattern to kick in, and we’re making no guess as to when.)
We’ll prove by contradiction that (*) is impossible. So, to set up the proof, suppose there is such an , and let’s write in scientific form:
For example, if , corresponding to our apparent pattern, then , with . (Notice that in general is impossible, since this would imply has a final digit of 0.)
Now, how do we go about proving that , whatever it is, cannot work in (*)? The quantity that really matters is , and just to make it a little more concrete let’s assume that , just as for our apparent pattern. (Other ranges of can be handled in a similar manner. (09/09/21 – see the proof addendum))
With this assumption on but assuming nothing else, we’ll now show there must be a huge such that has first digit 1, but has first digit 2. That is, whatever is, we can find an as large as we want that kills the -repeating pattern, and so proving (*) is false.
Now all of the above is really set up, and it’s time to get down to work. We’re hunting for an that works as indicated, and let’s write the corresponding hoped-for in scientific form:
What would work perfectly is if we could wind up with . Then would definitely have first digit 1, and would be just big enough for to have first digit 2. Of course obtaining such an equality is too much to hope for. But, what we can do is choose huge so that is at most a tiny fraction larger than . To be precise, we’ll show that, whatever is, we can arrange for a huge so that
So, if “tiny” is tiny enough (relative to ), then we’ll still have (implying has first digit 1), and also (implying has first digit 2).
To show that there is such an , we first show there is a huge such that is really close to a power of 10. That is, writing in scientific form,
we’ll show that we can arrange
How does (2) prove (1)? Well, just keep multiplying by itself. Eventually some power of , let’s say , will just creep higher than . Then, we can choose .
And so, the final final thing to do is show we can find huge for which (2) holds. But that turns out to be pretty easy. Start with , some huge power of 2, wherever the pattern supposedly begins. Now keep taking powers of and write in scientific form:
Notice that none of the can equal each other, since, taking the ratio, that would imply a power of 2 ends in a 0. But then we have all these zillions of different , as many as you want, crammed into the interval (1,10). So, there must be a ratio of two of these trapped between 1 and (1 + really tiny). (Technically, this is the pigeonhole principle applied to finitely many intervals of the form covering (1,10)). Then, the corresponding power of 2 gives us our .
Just a quick addendum to the digits proof. We assumed in the proof that , and suggested other ranges of could be handled similarly. In fact, it’s very easy to see if is such that (*) holds then we must have . If then it is easy to choose at the end of the proof to ensure ; the only issue is if is close to 10 but, whatever is, we can still ensure is really really close to 1. So, will have first digit 1, and will definitely have a different first digit.