Let p >= 10^d, and let 0 <= B < 10^d be any d-digit block of digits. By the definition of the ceiling function [1] pB/10^d <= ceil(pB/10^d) < pB/10^d + 1. Dividing by p gives [2] B/10^d <= ceil(pB/10^d)/p < B/10^d + 1/p But p >= 10^d, so 1/p <= 1/10^d, and [3] B/10^d + 1/p <= B/10^d + 1/10^d = (B+1)/10^d [2] and [3] together give [4] B/10^d <= ceil(pB/10^d)/p < (B+1)/10^d Letting n = ceil(pB/10^d), we have integer n with [5] B/10^d <= n/p < (B+1)/10^d [5] says that the decimal fraction n/p starts with block B. So if p >= 10^d, there is a fraction n/p (0 <= n < p) starting with any given d-digit block B, namely n/p = ceil(pB/10^d)/p. If p > 10^d, then by the previous paragraph, there is a fraction n/p (0 <= n < p) starting with any given d-digit block B. But because p > 10^d, since 0/p and 1/p both start with block B = 0, so we can strengthen the condition on n to 1 <= n < p. In other words: If p > 10^d, there is a fraction n/p (1 <= n < p) starting with any given d-digit block B. Now suppose p > 10^d and p has primitive root 10. Because of the primitive root 10, every n with 1 <= n < p is expressible as n = 10^k mod p for some 0 <= k < p-1. By our previous paragraph, there is then a fraction of the form (10^k mod p) / p starting with any desired d-digit block B. From this we conclude that every d-digit block occurs somewhere in the decimal expansion of 1/p. In other words, any prime p > 10^d with primitive root 10 includes every d-digit block in the decimal expansion of its reciprocal. This is why I must choose the smallest such prime if I am looking for the first number with that property. I can show that the smallest number n whose decimal reciprocal includes every d-digit block must satisfy n >= 10^d. I can also show that the reciprocal of the smallest prime p > 10^d with primitive root 10 includes every d-digit block. I can show that if p < 2*10^d, then there is no other prime q with 10^d <= q < p whose reciprocal includes every d-digit block. What I can't show is that there is not some composite q with 10^d <= q < p whose reciprocal includes every d-digit block, though I seriously doubt such a q could exist. On 1/29/2012 7:33 PM, Hans Havermann wrote:
I'll take a half-hearted empirical stab at this myself. The smallest base-ten number that contains the numbers from 1 to n as substrings (A035239) appears to be of length n. The period of a primitive-root-10 prime (A001913) p is p-1, so it can contain all d-digit numbers only if p-1 >= 10^d-1. Which leaves why p should happen to be the *first* member of A001913 > 10^d (and not some subsequent one).
I wrote:
David Wilson:
I realized that this sequence would be a(n) = smallest prime >= 10^n with primitive root 10.
The primitive-root-10 (A001913) criterion assures us a large decimal expansion period from which to cull our n-digit collection. That is also shared by primitive-root-10 primes < 10^n. How do you know one of these doesn't eventually luck into a 9*10^(n-1) distinct n-digit count?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun