Penultimate POTW Now Available!

Cool problem! You can brute-force it, counting rotations from the outside in (e.g., the "2" indicates there have been two full rotations of the 100's digit, skipping "4" twice, so 18 steps, etc.). But much easier is to realize that "skipping the 4" is equivalent to counting in base-9, with slightly each character above "4" representing one less quantity (i.e., replace "N" with N-1 for "5" through "9" becoming 4 through 8).

So "2016" is really 2015 (base 9), or 1,472 decimal miles.

Michael's method is much better than mine!

But for the sake of completeness, here's how I approached it:
- From 1-39, it will have gone 35 miles (skipping 4, 14, 24, 34).
- At 59, it will have gone 44 miles (having skipped 40-44 and 54 in addition).
- At 99, it will have gone 80 miles (as from now on every 10 miles gets us 9, so 36 more miles than when it showed 59).

Now, at 399, it will have gone 323 miles. That's because in addition to 101-199, 201-299, 301-399 (which are 80 miles each, as they are equivalent to 1-99 above), we have to add a mile for 100, 200, and 300.

At 599, it will have gone 404 miles (it will skip 400-499; 501-599 is 80 miles, and 500 is another mile).
At 999, we can use the rule that every 100 miles from 599 onwards to here is 81 real miles, so that's an additional 324 miles, for a total of 728 miles.

At 1999, since we can say that 1001-1999 is the equivalent of 1-999, it will be 1456 + 1 (for mile 1000) = 1457 miles.

From 2000-2016 (17 miles), it will skip 2004 and 2014, so we add another 15 to our 1999 total to get 1472 miles. (Which of course is the same as Michael's answer above).

Michael@1: The "brute force" method is mathematically identical to the base 9 strategy you use. If you work it out, you find that the car has traveled ((2 * 9 + 0) * 9 + 1) * 9 + 5 miles, which is 1472 miles, just what you would get from computing it as 2 * 729 + 0 * 81 + 1 * 9 + 5.

From a computer algorithm point of view, the first method is actually more "efficient". It has three multiplications and three additions. Your method has three additions and six multiplications (because you compute each power of 9 separately). I've had occasion to write subroutines to evaluate series where each term can be readily computed from the previous term--that's the way you do it. If you recall the technique of synthetic substitution from your algebra classes, that's what this method involves.

Eric Lund:

Exactly right. The only exceptions are when there's symmetry to exploit, that is, where you wring some efficiency out by precomputing some terms that are used several times in an algebraically identical expression. This comes up a lot in interpolation functions for instance.

@Eric Lund #3: You are quite right, of course! But, as we both know from dealing with students, "mathematically identical" is rarely synonymous with "conceptually identical." I was laying out my thought process in analyzing the problem: Starting from "just counting cycles" led to the realization that skipping one digit is the same as counting to nine instead of ten (i.e., base 9).

When I did the final sum, I used the same "nested" calculation -- less work on the calculator :-), that is (2*9*9 + 1)*9 + 5. This is surprisingly efficient for many sorts of "power-series" summations which crop up far more often than most non-physicists might realize.