Hello! While you're here, feel free to check out some of my educational interactives. Highlights are on my About page and the whole collection is in the Index.
A long time ago, I took a course in Budapest called Conjecture and Proof, and one of our homework problems was to determine (with proof) whether there was a power of 2 which begins with 7777777777... . Initially, this seems very unlikely, but if we do a brute force search, we find a close call fairly early:
This input below will allow you to hunt for a power of 2 starting with whatever prefix you want and/or completely obliterate your computer:It should be clear by how long this process takes that we're going to have to use some math to find this number, if it even exists.
A seasoned math problem solver should already be familiar with a technique to investigate the last few digits of numbers, namely modular arithmetic. In fact, we can go a step further than just computing the last few digits of integers. Let's solve the problem:
Is there a multiple of pi whose first few digits after the decimal place are .777?
|
Rotation Amount: Number of rotations: |
If one looks at sufficiently enough multiples of pi, two of them must be closer together than the width of the target range. In fact, one can show that one of the two multiples must be 0 pi using a subtraction argument. We can then take multiples of that multiple to get us (very inefficiently) into the target range.
You have now been provided with all the information I was given when presented with this homework problem. Now's a good time to take a break and try to solve the problem yourself.
Are there positive integers n and x such that:Taking the log (base 10) of the problem gives us: or: In other words, is there a multiple of log(2), whose fractional part is between log(7.777777777) and log(7.777777778)? And, once you've proved that log(2) is irrational, a similar argument to that above will prove that such an n exists. But how do we find one?
We might first consider the tactic we used with multiples of pi: simply list multiples of log(2) until we find two that are close enough together (specifically, of a distance less than the width of the target interval. However, this approach is still too brute-force to be practical: the width of the target interval is:
We would need more than multiples to guarantee we had found two close enough together, and even then we'd still have to do some figuring to determine which multiples were that close together.Let's consider what we're looking for specifically: some positive integer multiple of log(2) whose decimal part is exceptionally close to 0, that we can use to walk our way around the circle and land in the target area. In other words, for some positive integers n and x:
In other words: That is, we're looking for a really good rational approximation to log(2). The go-to for rational approximations to log(2) is since . (In fact, is close by too, giving good approximations of ln(2) and ln(10).)But we need a much better rational approximation, and in fact it needs to be quite good relative to its size. Specifically, we want:
Luckily, we know that log(2) is transcendental (a correlate of the Gelfond-Schneider theorem), and thus has irrationality measure (thanks, Liouville!) at least 2 (possibly more), and thus: Or: Has infinitely many solutions in whole numbers n,x.One can calculate exactly how much precision we need in our rational approximation, but trial-and-error is likely to give better results. The rational approximation I used was: