[math-fun] Wilson's theorem on primes (no, not that one, the one about decimals)
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.
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 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
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.
* Warren Smith <warren.wds@gmail.com> [Jan 30. 2012 17:09]:
From: David Wilson <davidwwilson@comcast.net> [...]
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.
Without really having followed through: This rings the "shift register sequences"-bell for me. So a good source about these might be worth checking. I recommend "the bible": Rudolf Lidl, Harald Niederreiter: {Finite fields}, Cambridge University Press, second edition, (1997); Almost the same (and sufficient for what we care about) is: Rudolf Lidl, Harald Niederreiter: {Introduction to finite fields and their applications}, Cambridge University Press, revised edition, (1994)
[...]
On Mon, Jan 30, 2012 at 11:03 AM, Warren Smith <warren.wds@gmail.com> wrote:
From: David Wilson <davidwwilson@comcast.net>
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's postulate tells us there is a prime between 10^d and 2*10^d. But what I think David Wilson needs as an assumption is the stronger statement that there is a prime p between 10^d and 2*10^d such that 10 is a primitive root mod p. Andy
="Warren Smith" <warren.wds@gmail.com> a randomness property of the Marsaglia type of pseudorandom number generator
Apologies for a sideways rant, but this thread keeps picking at a pet peeve: First let me say that I don't want to disparage anyone's interest in the number theory or various PRNGs for their own sake--that can be fascinating and illuminating. Nor do I claim that there are no other interesting applications for them, say in some kind of complexity analysis or proof. However I've long felt Don Knuth did the world a well-meaning disservice with his extensive and scholarly--but highly distracting--analysis of the linear congruential generator in TAoCP. Such tiny-footprint methods were of course of practical interest in the "classic" computing era where we'd dare only use a few registers, but as soon as even relatively small tables are an option I think such methods are at best irrelevant. Ironically, Knuth in that same chapter gives brief descriptions (in his Algorithms "A" and "M") of a basis for what I believe is a much better and more straightforward (and therefore perhaps too pedestrian) generator. I will describe this briefly for those interested in such arcana:
="Joerg Arndt" <arndt@jjj.de> This rings the "shift register sequences"-bell for me.
The key idea (which Bill Gosper brought to my notice) is to use one of these well-studied shift register generators, but operate on a vector of entire words, rather than a vector of single bits (basically Knuth's Algorithm A). That is, X_n+1 = sum of some earlier X_n-k for some fixed set of k chosen by the usual primitive polynomial criteria. The LSBs of the outputs then follows an exact bitwise shift register sequence, and the more significant bits try to, but are increasingly perturbed by the "chaotic" carries bubbling up from below. The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA). Xn is easy to compute (no multiplies), hard to invert, and obviously has monstrously long period. However the output sequence X_n admittedly DOES still have SOME detectable patterns and "auto correlations" (eg the LSBs). So to be "extra EXTRA random" we can scramble and mangle it as follows (a variation on Knuth's Algorithm M): Make another table Y also initialized with junk. Use the previous algorithm to generate pairs X and X'. Use X to pick an index into Y in the usual way, call it k. Then increment Y_k by X', store that back and output it. Knuth notes that this downstream process can make even lame generators (eg Fibonacci) viable. Note that there's no feedback, so it can't get hung up on a pathological fixpoint. Given that the upstream generator is already excellent this is going to produce an essentially endless source of super hi-fi noise. And it's easy to code and cheap to run. There may be plenty of interesting number theory to explore around other generators, but as a practical matter I claim this recipe makes PRNGs pretty much a solved problem.
It's a long time since I did anything in this area, but I remember coming to similar conclusions then. It was around the time DES appeared ... 'nuff said! << The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA). >> Dunno what a EULA might be, but it sounds as if it might be large. If that's the case, and this seed itself is badly nonrandom in some fashion, it could quite easily corrupt the output from the main generator for a considerable time afterwards. One detects a certain circularity supervening ... WFL On 1/31/12, Marc LeBrun <mlb@well.com> wrote:
="Warren Smith" <warren.wds@gmail.com> a randomness property of the Marsaglia type of pseudorandom number generator
Apologies for a sideways rant, but this thread keeps picking at a pet peeve:
First let me say that I don't want to disparage anyone's interest in the number theory or various PRNGs for their own sake--that can be fascinating and illuminating. Nor do I claim that there are no other interesting applications for them, say in some kind of complexity analysis or proof.
However I've long felt Don Knuth did the world a well-meaning disservice with his extensive and scholarly--but highly distracting--analysis of the linear congruential generator in TAoCP.
Such tiny-footprint methods were of course of practical interest in the "classic" computing era where we'd dare only use a few registers, but as soon as even relatively small tables are an option I think such methods are at best irrelevant.
Ironically, Knuth in that same chapter gives brief descriptions (in his Algorithms "A" and "M") of a basis for what I believe is a much better and more straightforward (and therefore perhaps too pedestrian) generator.
I will describe this briefly for those interested in such arcana:
="Joerg Arndt" <arndt@jjj.de> This rings the "shift register sequences"-bell for me.
The key idea (which Bill Gosper brought to my notice) is to use one of these well-studied shift register generators, but operate on a vector of entire words, rather than a vector of single bits (basically Knuth's Algorithm A).
That is, X_n+1 = sum of some earlier X_n-k for some fixed set of k chosen by the usual primitive polynomial criteria.
The LSBs of the outputs then follows an exact bitwise shift register sequence, and the more significant bits try to, but are increasingly perturbed by the "chaotic" carries bubbling up from below.
The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA).
Xn is easy to compute (no multiplies), hard to invert, and obviously has monstrously long period.
However the output sequence X_n admittedly DOES still have SOME detectable patterns and "auto correlations" (eg the LSBs). So to be "extra EXTRA random" we can scramble and mangle it as follows (a variation on Knuth's Algorithm M):
Make another table Y also initialized with junk. Use the previous algorithm to generate pairs X and X'. Use X to pick an index into Y in the usual way, call it k. Then increment Y_k by X', store that back and output it.
Knuth notes that this downstream process can make even lame generators (eg Fibonacci) viable. Note that there's no feedback, so it can't get hung up on a pathological fixpoint. Given that the upstream generator is already excellent this is going to produce an essentially endless source of super hi-fi noise. And it's easy to code and cheap to run.
There may be plenty of interesting number theory to explore around other generators, but as a practical matter I claim this recipe makes PRNGs pretty much a solved problem.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
End User License Agreement. Marc is continuing to riff on the silliness of encoding one's copyright notice in the random seed. On Tue, Jan 31, 2012 at 3:42 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
It's a long time since I did anything in this area, but I remember coming to similar conclusions then. It was around the time DES appeared ... 'nuff said!
<< The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA). >>
Dunno what a EULA might be, but it sounds as if it might be large. If that's the case, and this seed itself is badly nonrandom in some fashion, it could quite easily corrupt the output from the main generator for a considerable time afterwards.
One detects a certain circularity supervening ... WFL
On 1/31/12, Marc LeBrun <mlb@well.com> wrote:
="Warren Smith" <warren.wds@gmail.com> a randomness property of the Marsaglia type of pseudorandom number generator
Apologies for a sideways rant, but this thread keeps picking at a pet peeve:
First let me say that I don't want to disparage anyone's interest in the number theory or various PRNGs for their own sake--that can be fascinating and illuminating. Nor do I claim that there are no other interesting applications for them, say in some kind of complexity analysis or proof.
However I've long felt Don Knuth did the world a well-meaning disservice with his extensive and scholarly--but highly distracting--analysis of the linear congruential generator in TAoCP.
Such tiny-footprint methods were of course of practical interest in the "classic" computing era where we'd dare only use a few registers, but as soon as even relatively small tables are an option I think such methods are at best irrelevant.
Ironically, Knuth in that same chapter gives brief descriptions (in his Algorithms "A" and "M") of a basis for what I believe is a much better and more straightforward (and therefore perhaps too pedestrian) generator.
I will describe this briefly for those interested in such arcana:
="Joerg Arndt" <arndt@jjj.de> This rings the "shift register sequences"-bell for me.
The key idea (which Bill Gosper brought to my notice) is to use one of these well-studied shift register generators, but operate on a vector of entire words, rather than a vector of single bits (basically Knuth's Algorithm A).
That is, X_n+1 = sum of some earlier X_n-k for some fixed set of k chosen by the usual primitive polynomial criteria.
The LSBs of the outputs then follows an exact bitwise shift register sequence, and the more significant bits try to, but are increasingly perturbed by the "chaotic" carries bubbling up from below.
The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA).
Xn is easy to compute (no multiplies), hard to invert, and obviously has monstrously long period.
However the output sequence X_n admittedly DOES still have SOME detectable patterns and "auto correlations" (eg the LSBs). So to be "extra EXTRA random" we can scramble and mangle it as follows (a variation on Knuth's Algorithm M):
Make another table Y also initialized with junk. Use the previous algorithm to generate pairs X and X'. Use X to pick an index into Y in the usual way, call it k. Then increment Y_k by X', store that back and output it.
Knuth notes that this downstream process can make even lame generators (eg Fibonacci) viable. Note that there's no feedback, so it can't get hung up on a pathological fixpoint. Given that the upstream generator is already excellent this is going to produce an essentially endless source of super hi-fi noise. And it's easy to code and cheap to run.
There may be plenty of interesting number theory to explore around other generators, but as a practical matter I claim this recipe makes PRNGs pretty much a solved problem.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
There's a good paper on parallel random number generation here: http://www.thesalmons.org/john/random123/papers/random123sc11.pdf It won the best paper award at SC11. The basic idea is to come up with a function f such that the nth random number is f(n), instead of generating the numbers sequentially, which makes the "parallel" part trivial. The paper describes how f can be chosen so that the random number generation is fast on modern processors and passes the BigCrush statistical test. J.P. On Tue, Jan 31, 2012 at 3:44 PM, Allan Wechsler <acwacw@gmail.com> wrote:
End User License Agreement. Marc is continuing to riff on the silliness of encoding one's copyright notice in the random seed.
On Tue, Jan 31, 2012 at 3:42 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
It's a long time since I did anything in this area, but I remember coming to similar conclusions then. It was around the time DES appeared ... 'nuff said!
<< The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA).
Dunno what a EULA might be, but it sounds as if it might be large. If that's the case, and this seed itself is badly nonrandom in some fashion, it could quite easily corrupt the output from the main generator for a considerable time afterwards.
One detects a certain circularity supervening ... WFL
On 1/31/12, Marc LeBrun <mlb@well.com> wrote:
="Warren Smith" <warren.wds@gmail.com> a randomness property of the Marsaglia type of pseudorandom number generator
Apologies for a sideways rant, but this thread keeps picking at a pet peeve:
First let me say that I don't want to disparage anyone's interest in the number theory or various PRNGs for their own sake--that can be fascinating and illuminating. Nor do I claim that there are no other interesting applications for them, say in some kind of complexity analysis or proof.
However I've long felt Don Knuth did the world a well-meaning disservice with his extensive and scholarly--but highly distracting--analysis of the linear congruential generator in TAoCP.
Such tiny-footprint methods were of course of practical interest in the "classic" computing era where we'd dare only use a few registers, but as soon as even relatively small tables are an option I think such methods are at best irrelevant.
Ironically, Knuth in that same chapter gives brief descriptions (in his Algorithms "A" and "M") of a basis for what I believe is a much better and more straightforward (and therefore perhaps too pedestrian) generator.
I will describe this briefly for those interested in such arcana:
="Joerg Arndt" <arndt@jjj.de> This rings the "shift register sequences"-bell for me.
The key idea (which Bill Gosper brought to my notice) is to use one of these well-studied shift register generators, but operate on a vector of entire words, rather than a vector of single bits (basically Knuth's Algorithm A).
That is, X_n+1 = sum of some earlier X_n-k for some fixed set of k chosen by the usual primitive polynomial criteria.
The LSBs of the outputs then follows an exact bitwise shift register sequence, and the more significant bits try to, but are increasingly perturbed by the "chaotic" carries bubbling up from below.
The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA).
Xn is easy to compute (no multiplies), hard to invert, and obviously has monstrously long period.
However the output sequence X_n admittedly DOES still have SOME detectable patterns and "auto correlations" (eg the LSBs). So to be "extra EXTRA random" we can scramble and mangle it as follows (a variation on Knuth's Algorithm M):
Make another table Y also initialized with junk. Use the previous algorithm to generate pairs X and X'. Use X to pick an index into Y in the usual way, call it k. Then increment Y_k by X', store that back and output it.
Knuth notes that this downstream process can make even lame generators (eg Fibonacci) viable. Note that there's no feedback, so it can't get hung up on a pathological fixpoint. Given that the upstream generator is already excellent this is going to produce an essentially endless source of super hi-fi noise. And it's easy to code and cheap to run.
There may be plenty of interesting number theory to explore around other generators, but as a practical matter I claim this recipe makes PRNGs pretty much a solved problem.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
="J.P. Grossman" <jpg@alum.mit.edu> There's a good paper on parallel random number generation here: http://www.thesalmons.org/john/random123/papers/random123sc11.pdf
Very interesting, thanks for the link! I will plan to read it more carefully, but already I'm intrigued that one of the authors is *that* David Elliot Shaw: http://en.wikipedia.org/wiki/David_E._Shaw Small valley!
It won the best paper award at SC11. The basic idea is to come up with a function f such that the nth random number is f(n), instead of generating the numbers sequentially, which makes the "parallel" part trivial. The paper describes how f can be chosen so that the random number generation is fast on modern processors and passes the BigCrush statistical test.
I don't know yet how this compares to what's in the cited paper, but another thing Bill Gosper noted about the word-vector shift-register upstream (Algorithm A) part of generator I described is that each step is effectively a multiplication of the vector by a sparse 01 matrix whose non-zero entries are simply the coefficients of the primitive polynomial (or the feedback taps in the delay line, to use signal-processing lingo). Thus one can jump n steps simply by multiplying by the n-th power of that matrix instead. Of course the downstream (Algorithm M) part is specifically intended to mess up even this vestigial "autocorrelation".
* Marc LeBrun <mlb@well.com> [Feb 02. 2012 07:23]:
[...]
Here is my two nano cents: Use a LFSR (over GF(2)) with some polynomial allowing easy mod operation, e.g., one from http://www.jjj.de/mathdata/all-lowblock-irredpoly-short.txt it should span a few words (I consider period 2^128 (Salmon et. al. paper) a bit small, so go for, say >=4 words to get >=2^256 ). [may check Brent's XOR-shift method as well] Together with this one run a (or a few) FCSR (essentially 2^n mod a prime with primitive root 2), XOR some parts of both to get the random numbers. Rate should be reasonably near to how fast you can copy memory (so I'd expect to generate, say, 1 GB/sec on one core; possibly we need to allow for (rather small) buffers). Jumping to any point in the period is trivial once we know the orders of all parts (shift registers). And so we can run instances on as many cores as we like. Here I did _not_ care about "cryptographical security". [I'd speculate that running two (large) LSFR, and one small LFSR whose bits select between the two large one's outputs could do the trick (by causing a huge and hard to determine period). Could replace small LFSR by some other method to avoid ease of analysis (wrt. periods).] If reproducibility is not required (and the user is really paranoid about randomness) XORing the above with some (even weak) source of entropy should make the output pass all tests in existence. Btw. I found the following paper surprising: Paul Leopardi: {Testing the tests: using random number generators to improve empirical tests}, Eighth International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (MCQMC 2008) proceedings, (2009). URL: \url{http://wwwmaths.anu.edu.au/~leopardi/Leopardi-TestU01-paper-final.pdf}. ...web site down at the moment, can supply final version on request. Note I did never really work on random number generation.
* Joerg Arndt <arndt@jjj.de> [Feb 02. 2012 10:15]:
* Marc LeBrun <mlb@well.com> [Feb 02. 2012 07:23]:
[...]
Small correction:
[...]
Use a LFSR (over GF(2)) with some polynomial allowing easy mod operation, e.g., one from http://www.jjj.de/mathdata/all-lowblock-irredpoly-short.txt it should span a few words (I consider period 2^128 (Salmon et. al. paper) a bit small, so go for, say >=4 words to get >=2^256 ).
This should have been http://www.jjj.de/mathdata/lowbit-primpoly.txt # Binary primitive polynomials with lowest-most possible set bits. # These are the minimal numbers with the corresponding # polynomial of given degree primitive. E.g.g the entry 256,10,5,2,0 says that x^256+x^10+x^5+x^2+1 is primitive over GF(2) (and is the lex-first such polynomial).
[...]
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
David Wilson and Warren Smith batted about the side puzzle: When can the reciprocal of a composite N contain every digit combination of length floor[log10(N)]? Smith (roughly) argued 'never', and Wilson pointed out that some prime powers worked. Adding a bit more fuel: The reciprocals of 343 (7^3), 841 (29^2), and 799 (17*47) each contain all two-digit combinations. Rich
In the US, prior to 1975, the official system of weights and measures was the avoirdupois system. Other weights and measures, specifically metric units, were defined in nice round terms of avoirdupois units. For example, a meter was defined as precisely 39.37 inches. In 1975, the US government officially adopted the metric system. The scientific world was already universally metric, so it needed no change. There was a metrication campaign, and millimeters appeared on our grade school rulers. But the ostensible ulterior motive, which was to cajole US industry into adopting metric product sizing for compatiblity with world markets, was largely a failure. The failure was popularly blamed on cultural resistance by the backward American public, but I submit it was largely due to industrial resistance to the costs of retooling. True, 2-liter soda bottles, 16mm film, and 195/55R16 tires showed up on the American scene, but for the most part manufacturers added parenthetical metric equivalents to their avoirdupois packaging ("12 oz (340 grams)"), and life went on with teaspoons, 7/16" socket wrenches and 12-foot two-by-fours. Perhaps the most significant change at that time was that the US government rebased its weights and measures in terms of metric units. So whereas previously, a centimeter precisely 0.3937 inches, so that an inch was a smidgin over 2.54 centimeters, the inch was now precisely 2.54 centimeters, making the centimeter a smidgimeter larger than 0.3937 inches. This was one small step for most of the US units, whose values adjusted slightly as they were rebased, but one giant leap for the final arbiter of US weights and measures, from the National Bureau of Standards (now NIST) in the US to the International Bureau of Weights and Measures (BIPM) in France. But I promised fun with sequence embedded decimals, so... Prior to 1975, a centimeter would have been an exact 0.3937 inches. This means that an inch would have been 1/0.3937 = 2.54 000508 001016 002032 004064 ... centimeters. Observe the nice doubling pattern of the 6-digit blocks. After 1975, the inch was precisely 2.54 centimeters. Now the centimeter is 1/2.54 = 0.3937 007874 015748 031496 062992 ... inches. Almost amazingly, we find the same 6-digit block doubling pattern here. Prior to the conversion, a centimeter was 0.3937 inches, post-conversion it was 1/2.54 centimeters. Perhaps, instead of letting either the avoirdupois or metric system dictate the conversion factor, we should adopt a compromise system whose conversion factors which are the geometric mean of the conversion factors of the two competing systems. In this new system, a centimeter would be sqrt(0.3937 * (1/2.54)) = sqrt(0.155) = 0.39370 039370 059055 098425 ... inches, and again we see curious relationships between blocks of 6 digits. Similarly, in our new system, the inch would be 1/sqrt(0.155) = 2.5400 025400 038100 063500 111125 ... centimeters. All this mathematical magic actually stems from an interesting factorization of a number near 500000. Perhaps you can find it.
Hey that's cool, and they're much like my favorite such pair, 1/27=0.037037037... and 1/37=0.027027027... I'll add them to my numbers pages! - Robert mrob.com/pub/math/numbers-2.html#l2_54 mrob.com/pub/math/numbers-6.html#la39_37 On Sat, Feb 4, 2012 at 11:31, David Wilson <davidwwilson@comcast.net> wrote:
In the US [...] Prior to 1975, a centimeter would have been an exact 0.3937 inches. This means that an inch would have been
1/0.3937 = 2.54 000508 001016 002032 004064 ...
centimeters. Observe the nice doubling pattern of the 6-digit blocks.
After 1975, the inch was precisely 2.54 centimeters. Now the centimeter is
1/2.54 = 0.3937 007874 015748 031496 062992 ...
inches. Almost amazingly, we find the same 6-digit block doubling pattern here.
[...]
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
participants (10)
-
Allan Wechsler -
Andy Latto -
David Wilson -
Fred lunnon -
J.P. Grossman -
Joerg Arndt -
Marc LeBrun -
rcs＠xmission.com -
Robert Munafo -
Warren Smith