[math-fun] Fwd: Re: [EXTERNAL] Re: Fun with math: Dividing one by 998001 yields a surprising result
I realized that this sequence would be a(n) = smallest prime >= 10^n with primitive root 10. This made it easier to extend 1 17 2 109 3 1019 4 10007 5 100019 6 1000171 7 10000019 8 100000007 9 1000000007 -------- Original Message -------- Subject: Re: [math-fun] [EXTERNAL] Re: Fun with math: Dividing one by 998001 yields a surprising result Date: Sat, 28 Jan 2012 10:41:33 -0500 From: David Wilson <davidwwilson@comcast.net> Reply-To: math-fun <math-fun@mailman.xmission.com> To: math-fun <math-fun@mailman.xmission.com> Which made me curious... What is the smallest value a(d) such that every d-digit sequence occurs in the decimal expansion of 1/d (after the decimal point). For small d>= 1 my program says 17, 109, 1019, 10007, 100019, ... but it seems stuck on 6 digits, so perhaps there is an overflow issue. All primes slightly above 10^d, as one might expect, but not necessarily the smallest such primes. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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?
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?
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
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
participants (2)
-
David Wilson -
Hans Havermann