Let b >= 2, d >= 1. We can show that the number of distinct k-digit blocks that occur somewhere after the point in the b-ary expansion of some fraction with denominator d is precisely min(b^k, d). Suppose we want the number of distinct 2-digit blocks that occur in the decimal expansions of fractions with denominator 6. These fractions are 0/6 = .000000... blocks: 00 1/6 = .166666... blocks: 16, 66 2/6 = .333333... blocks: 33 3/6 = .500000... blocks: 00, 50 4/6 = .666666... blocks: 66 5/6 = .833333... blocks: 33, 83 Any other fraction with denominator 6 will have fractional part equal to one of the above fractions, and will therefore have the same set of blocks as that fraction. This means that there are exactly 6 distinct 2-digit blocks that can occur after the decimal in a fraction with denominator 6, to wit 00, 16, 33, 50, 66, or 83. The above formula agrees: min(10^2, 6) = 6. If a block occurs anywhere within a fraction of denominator d, then it occurs immediately after the point in some fraction n/d, 0 <= n < d. You can prove this by multiplying the fraction by b repeatedly, shifting the block left until it abuts the point, then taking the floor of the resulting fraction. Note that if d <= b^k, then 1/d >= 1/b^k, which is to say, adding 1/d to a fraction will change the k-digit block immediately following the point. This means that the k-digit blocks immediately following the points in each of 0/d, 1/d, 2/d, ... up to (d-1)/d are all distinct, so that there are exactly d such blocks. If d >= b^k, then 1/d <= 1/b^k. In that case, you can show that each of the b^k possible k-digit blocks must occur immediately after the point in some k/d, with 0 <= k < d, so there are b^k distinct k-digit blocks among all fractions with denominator d. Hence there are exactly min(b^k, d) distinct k-digit blocks immediately after the decimal point in fractions with denominator d, and by the previous paragraph, min(b^k, d) distinct blocks anywhere within those fractions. So this answers one your question below. If d < b^k, there are min(b^k, d) = d < b^k k-digit blocks among all fractions with denominator d. This means there are at most d < b^k distinct blocks in any single fraction with denominator d. It is not possible for some fraction n/d with d < b^k to "luck into" all b^k possible k-digit blocks. On 1/29/2012 3:21 PM, Hans Havermann 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