On 1/30/2012 11:03 AM, Warren Smith wrote:
From: David Wilson<davidwwilson@comcast.net> 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. --this is a nice theorem, and it might be a new one. It is also of some importance because it proves a randomness property of the Marsaglia type of pseudorandom number generator.
To determine if it is new, I suggest looking to see if it is in Hardy& Wright chapter 9 as step one. Frankly though, it looks too easy to have escaped previous notice.
I agree. If I can prove it, I assume it must be pretty straightforward. The core idea is that if 1/p <= 1/10^k, then obviously you will visit every k-digit prefix (k-digit block immediately after the point) as you progress through 0/p, 1/p, ..., (p-1)/p, since the differences aren't large enough to skip a prefix. If in addition 1/p < 1/10^k (actually, this is necessary for base 10), then you get the bonus that 1/p starts with k 0's, so you don't need 0/p, so that 1/p, ..., (p-1)/p will visit all prefixes. Likewise, if 1/p > 1/10^k, there are not enough values in 0/p, 1/p, ..., (p-1)/p to visit all 10^k k-digit prefixes. Finally, we observe that every k-digit substring of n/p occurs as prefix of some n'/p, which completes the argument.
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. --well, that seems trivial since the period<n. I was just recapping what I had said earlier in preparation for what followed. 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, --you do not need this "if" because of the known theorem that there is always a prime between X and 2X if X>1: http://en.wikipedia.org/wiki/Bertrand's_postulate
Bertrand says that there is a prime between n and 2n, whereas we need a prime with primitive root 10 between n and 2n. I'm sure this happens for sufficient n, but then, I'm also sure that Goldbach's conjecture is true.
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.
--if q=a*b*...*c where a,b,...,c are primes with 10 primitive modulo each of them, then every n with 1<=n<q and gcd(n,q)=1 is expressible as n = 10^k mod q for some 0<=k<p-1. However, each n with gcd(n,q)>1 definitely is NOT thus-expressible. This tells me that the decimal expansion of 1/q with q composite, q>10, NEVER includes all k-digit blocks where k=floor(log10(q)), because those blocks are exactly the opening bars of 10^j/q. To prove that, there are two cases: case i: q>10 contains a prime p with p>10. Then the multiples of q/p are unrepresentable and include examples below 10^k case ii: q>10 contains a prime p<10, then the multiples of p do the job. QED.
I don't (immediately) buy it. I agree that if q is composite, the residues of 10^n mod q cannot include all of the residues mod q, there must be some missing residues. Specifically consider q = p^k for prime p coprime to 10. The residues of q coprime to q form the multiplicative group Z/qZ. There are |Z/qZ| = (p-1)p^(k-1) such residues.
In some cases, 10 is primitive root of q, in which case 10 generates Z/qZ, so that every residue of q is a power of 10. In this case, 10 is order |Z/qZ| in Z/qZ, hence there will be (p-1)p^(k-1) distinct fractional parts of 10^n/q. An example is q = p^k = 7^2. 10 happens to generate Z/49Z, so there are |Z/49Z| = 42 distinct fractional parts of 10^n/49. Furthermore, in the case of q = p^k, if we order the elements of Z/qZ as integer remainders on [0, q-1], the missing remainders are precisely those divisible by p. Again, taking q = 7^2, we find Z/49Z = {1,2,3,4,5,6,8,9, ..., 41,43,44,45,46,47,48} consists of the 42 residues of 49 that are not divisible by 7. A consequence of this fact is that no two of these residues are adjacent. This means that if we form the fractions 1/49, 2/49, ..., 48/49 with numerators from Z/49Z, the maximum difference between adjacent fractions will be 2/49. In the general case q = p^k, the maximum difference will be 2/p^k. Now let's look at the d-digit prefixes of the fractional part of n. Take d = 5, consider the decimal .3141500001. In order to skip from prefix 31415 to 31417 (skipping 31416), we must add .0000199999, which is nearly 2*10^-5. For arbitrarily tiny e, to skip from .31415+e to .31417, we must add 2*10^-5 - e. This means that to guarantee that we skip a prefix (in this case 31416), we must add a value >= 2*10^-5 (although in favorable circumstances, any value > 10^-5 could skip a prefix). So in order to guarantee that our 2/p^k difference will skip a d-digit prefix, we must guarantee that 2/p^k >= 2/10^d, which implies p^k <= 10^d. If p^k > 10^d, we cannot guarantee that adjacent 10^n/q = 10^n/p^k skips a d-digit prefix, at least by a simpleminded difference analysis. And q = p^k is not the only sort of value we have to eliminate. We must also show that fractions with denominators q skip prefixes for other composite q, and prime q without primitive root 10 skip prefixes. So back to a restatement of the problem: n is d-good if the decimal expansion of 1/n includes every block of d-decimal digits. We have shown that no n < 10^d is d-good. We have also shown that the smallest prime p >= 10^d with primitive root 10 is d-good. The problem is to show that no q with 10^d <= q < p is d-good. I think it is true, I don't think it is easy to show.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun