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.
18 Replies to “NotCH 2: A Digits Puzzle”
Nice :). I for one enjoy NotCHes just as much as WitCHes.
Question: (I promise not to post any answers until others have had a good go) what is meant by “prove” in this context? I’m guessing you’re not going to allow me to invent a new type of function for example…?
Thanks, RF. By “prove” I mean to give a convincing argument. So, no need for a formal pure maths style of proof. But, enough of an argument that it’s clear those formal details could somehow be filled in if demanded.
OK, we’re not sure if we scared everybody into silence, or if people are not interested in the puzzle, or if people are simply puzzled by the puzzle.
So, let me know. Do people want the smart loudmouths to (a) go for it, (b) give hints (presumably starting small), or (c) to remain silent? If no one puts up their hand for (b) or (c), we’ll let the smart loudmouths off the leash.
There are 10 types of mathematicians in the world some of whom may speak loudly…
The pattern in the last digit is quite simple to understand using modular arithmetic.
I guess that there is no pattern in the first digit but there appears to be because 1024 is approximately equal to 1000. The apparent pattern would break down for large enough powers of two.
Thanks, Gavin. That’s it in a nutshell. We’ll let others add the details if they wish, and we’ll update the post with details soon.
Well, there’s more to your second question… I’m not sure where you were headed with it, so I’ll keep quiet, except perhaps to ask two innocent little questions for interested readers:
When looking at the sequence of first digits, do you notice any of them occurring more often than others? How often do you conjecture this to happen, and can you prove it?
Huh. You’re probably looking harder at this than I (and the article from which I grabbed it) intended.
I have been known to be a little bit of a tryhard, but there is something interesting there, at least in my opinion.
Gavin is right in that there is no obvious pattern for large enough n for leading digit as 2^10 is slightly larger than 10^3
For the first 10000 doubles the leading digit pattern will cycle mod 10 as 1.024 ^ 1000 is still less than 2 mod 10
Glen, are you referring to that chestnut of an anecdote about the professor who noticed the early pages of his book of log tables were more well-read than the later ones?
Also, if you know what I’m talking about – can you remember the name?
Are you referring to Benford’s law?
Used by ATO to audit returns etc
That’s the one.
Just giving it all away huh :).
I really despise the word “law” here btw. Like the Gibbs “phenomenon”. Bah!
> 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?
Well for any positive integer , you’ll have two powers of two which share the same last digits, because there’s only finitely many strings of digits. Then once you have two powers of two with the same last few digits, it will repeat, since you’re applying the same operation.
> 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?
My idea is that when we take the base-10 logarithm of, say, N, the decimal places are a sort of ‘signature’ which determines the leading digits of N. Then if we divide [0,1) into ten intervals:
where logarithms are base-10, then the interval which the fractional part of log(N) lies in determines the leading digit of N. So we’re interested in the sequence , or for .
From now on, I’ll be implicitly referring to the fractional parts of numbers rather than their actual quantity, because we only really care about what our numbers are in .
If I want to show that the pattern doesn’t repeat, then all I need to do is to show that when we keep adding multiples of log(2), the intervals that we ‘land in’ don’t repeat (we only care about the decimal places). Suppose it did, and that the starting digit of was the same as for all sufficiently large . Then this means that and are in the same interval, so can’t be greater than the ‘distance’ from to the edge of one of the intervals. But if we choose so that is smaller than but so close to that would belong to a different interval, this would contradict that the first digits repeated. So I only need to find such an .
It seems like because is irrational, that I should be able to multiply it by something and end up with something very close to any string of digits. You can prove this using Pigeonhole again! If there was an interval of length which wasn’t in the sequence then in there will be two of them in for some integer and we can subtract them to ‘cover’ the 1/K interval.
So I can choose so that is just below (fractional parts), by choosing a relevant interval of length 1/K. This means that will be in a lower interval than .
Oh, I guess if is really close to 1 it could loop around to land in the same interval again. In that case… we can choose so it’s greater than but really close to so that lies in but will fall just short and land in .
Sorry if I’m not really able to explain my ideas rigorously or succinctly. Most of this is just me trying to formalise this idea of eventually landing in a different interval, but I think this means that the first digits won’t repeat.
Thanks, Student. I’ll take a careful look later today.
Hi, Student. That’s a very nice argument. I’ll work on a cleaned-up version to add to the post.