[math-fun] Reciprocals of integers in binary
I wondered what reciprocals of integers looked like in binary, so I computed them. I noticed that lots of them had first and second halves of the repeating section that were complements of each other. For instance 1/97 is 0.000000101010001110100000111111010101110001011111.... That's 0.000000101010001110100000 111111010101110001011111.... For which numbers is this the case? It turns out to be precisely those in http://oeis.org/A014657 (except the first two) times any power of two (including zero). And I see why.
Very interesting. Which leads me to wonder what reciprocal integers look like in factorial base, where x ∊ (0, 1) is represented as x = ∑ a_n / n! where the sum is over n ≥ 2 with a_n ∊ Z+, 0 ≤ a_n < n, using the greedy algorithm. —Dan
On Saturday/30January/2021,
at 2:05 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote: I wondered what reciprocals of integers looked like in binary, so I computed them. I noticed that lots of them had first and second halves of the repeating section that were complements of each other. For instance 1/97 is 0.000000101010001110100000111111010101110001011111.... That's 0.000000101010001110100000 111111010101110001011111....
For which numbers is this the case? It turns out to be precisely those in http://oeis.org/A014657 (except the first two) times any power of two (including zero). And I see why.
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even). 1/7 = 0.142857 and 142 + 857 = 999. Numbers have to be to a multiple of 2 or 5 within the factorization. 1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19. Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m. This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft). Best regards, Simon Plouffe
<< The Mersenne Twister is a procedure to produce very good random numbers. >> However, for a more nuanced view see https://arxiv.org/pdf/1910.06437.pdf WFL On 1/31/21, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even).
1/7 = 0.142857 and 142 + 857 = 999.
Numbers have to be to a multiple of 2 or 5 within the factorization.
1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19.
Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m.
This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft).
Best regards, Simon Plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, I am aware that MT19937 is not perfect and also that it is not good enough for cryptography. But : almost all math packages are using it. For most Monte-Carlo programs : it is quite sufficiently random. It passes many tests including hard ones and Knuth criteria. You need a pretty high level of randomness to find the limits of this monster. I think that this kind of <discussion> has already occurred many times for random number generators. There is a saying in this area (Von Neumann) : Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin. Best regards, Simon Plouffe Le 2021-01-31 à 02:49, Fred Lunnon a écrit :
<< The Mersenne Twister is a procedure to produce very good random numbers. >>
However, for a more nuanced view see https://arxiv.org/pdf/1910.06437.pdf
WFL
On 1/31/21, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even).
1/7 = 0.142857 and 142 + 857 = 999.
Numbers have to be to a multiple of 2 or 5 within the factorization.
1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19.
Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m.
This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft).
Best regards, Simon Plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Dan Asimov, upthread, tickled my curiosity. So I calculated 1/17 in factorial expansion, and if I understood the definition correctly, it's 1/17 = .001202368909270G where the G represents a 16. All rational numbers have a terminating representation in factorial base. Prime reciprocals will take a full p-1 digits. I don't expect to see any catchy patterns. On Sat, Jan 30, 2021 at 9:11 PM Simon Plouffe <simon.plouffe@gmail.com> wrote:
Yes, I am aware that MT19937 is not perfect and also that it is not good enough for cryptography. But : almost all math packages are using it.
For most Monte-Carlo programs : it is quite sufficiently random. It passes many tests including hard ones and Knuth criteria. You need a pretty high level of randomness to find the limits of this monster.
I think that this kind of <discussion> has already occurred many times for random number generators.
There is a saying in this area (Von Neumann) :
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
Best regards, Simon Plouffe
Le 2021-01-31 à 02:49, Fred Lunnon a écrit :
<< The Mersenne Twister is a procedure to produce very good random numbers. >>
However, for a more nuanced view see https://arxiv.org/pdf/1910.06437.pdf
WFL
On 1/31/21, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even).
1/7 = 0.142857 and 142 + 857 = 999.
Numbers have to be to a multiple of 2 or 5 within the factorization.
1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19.
Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m.
This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft).
Best regards, Simon Plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hello, there is a difficulty with the notation if I may, actually 1/17 in factorial base is : 0, 0, 0, 0, 1, 2, 0, 2, 3, 6, 8, 9, 0, 9, 2, 7, 0, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,... it is getting bigger than 16. recall : exp(1) in that base is 1, 1, 1, 1 ... with ones only but the number Pi - 3 is [0, 0, 0, 0, 3, 1, 5, 6, 5, 0, 1, 4, 7, 8, 0, 6, 7, 10, 7, 10, 4, 10, 6, 16, 1, 11, 20, 3, 18, 12, 9, 13, 18, 21, 14, 34, 27, 11, 27, 33, 36, 18, 5, 18, 5, 23, 39, 1, 10, 42, 28 , 17, 20, 51, 8, 42, 47, 0, 27, 23, 16, 52, 32, 52, 53, 24, 43, 61, 64, 18, 17, 11, 0, 53, 14, 62, 0, 38, 26, 27, 23, 18, 13, 66, 47, 83, 78, 23, 37, 73, 37, 41, 35, 68, 63, 15, ... Patterns in this context are rare. You can count on your fingers the number of special expansions. One of them is : 1/24 in base exp(Pi*n)+1 is : 1, 0, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 13, 0, 15, 0, 17, 0, 19... and 1/504 in base n^3/(exp(2*Pi)-1) is 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196... These are the nice examples. have a nice day, Simon Plouffe Le 2021-01-31 à 05:21, Allan Wechsler a écrit :
Dan Asimov, upthread, tickled my curiosity. So I calculated 1/17 in factorial expansion, and if I understood the definition correctly, it's
1/17 = .001202368909270G
where the G represents a 16.
All rational numbers have a terminating representation in factorial base. Prime reciprocals will take a full p-1 digits. I don't expect to see any catchy patterns.
On Sat, Jan 30, 2021 at 9:11 PM Simon Plouffe <simon.plouffe@gmail.com> wrote:
Yes, I am aware that MT19937 is not perfect and also that it is not good enough for cryptography. But : almost all math packages are using it.
For most Monte-Carlo programs : it is quite sufficiently random. It passes many tests including hard ones and Knuth criteria. You need a pretty high level of randomness to find the limits of this monster.
I think that this kind of <discussion> has already occurred many times for random number generators.
There is a saying in this area (Von Neumann) :
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
Best regards, Simon Plouffe
Le 2021-01-31 à 02:49, Fred Lunnon a écrit :
<< The Mersenne Twister is a procedure to produce very good random numbers. >> However, for a more nuanced view see https://arxiv.org/pdf/1910.06437.pdf
WFL
On 1/31/21, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even).
1/7 = 0.142857 and 142 + 857 = 999.
Numbers have to be to a multiple of 2 or 5 within the factorization.
1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19.
Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m.
This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft).
Best regards, Simon Plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, I misunderstood the definition of the factorial expansion. Please disregard my earlier post. On Sun, Jan 31, 2021 at 1:17 AM Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, there is a difficulty with the notation if I may, actually 1/17 in factorial base is : 0, 0, 0, 0, 1, 2, 0, 2, 3, 6, 8, 9, 0, 9, 2, 7, 0, 15, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,...
it is getting bigger than 16.
recall : exp(1) in that base is 1, 1, 1, 1 ... with ones only but the number Pi - 3 is
[0, 0, 0, 0, 3, 1, 5, 6, 5, 0, 1, 4, 7, 8, 0, 6, 7, 10, 7, 10, 4, 10, 6, 16, 1, 11, 20, 3, 18, 12, 9, 13, 18, 21, 14, 34, 27, 11, 27, 33, 36, 18, 5, 18, 5, 23, 39, 1, 10, 42, 28 , 17, 20, 51, 8, 42, 47, 0, 27, 23, 16, 52, 32, 52, 53, 24, 43, 61, 64, 18, 17, 11, 0, 53, 14, 62, 0, 38, 26, 27, 23, 18, 13, 66, 47, 83, 78, 23, 37, 73, 37, 41, 35, 68, 63, 15, ...
Patterns in this context are rare. You can count on your fingers the number of special expansions.
One of them is : 1/24 in base exp(Pi*n)+1 is : 1, 0, 3, 0, 5, 0, 7, 0, 9, 0, 11, 0, 13, 0, 15, 0, 17, 0, 19...
and 1/504 in base n^3/(exp(2*Pi)-1) is 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196...
These are the nice examples.
have a nice day, Simon Plouffe
Le 2021-01-31 à 05:21, Allan Wechsler a écrit :
Dan Asimov, upthread, tickled my curiosity. So I calculated 1/17 in factorial expansion, and if I understood the definition correctly, it's
1/17 = .001202368909270G
where the G represents a 16.
All rational numbers have a terminating representation in factorial base. Prime reciprocals will take a full p-1 digits. I don't expect to see any catchy patterns.
On Sat, Jan 30, 2021 at 9:11 PM Simon Plouffe <simon.plouffe@gmail.com> wrote:
Yes, I am aware that MT19937 is not perfect and also that it is not good enough for cryptography. But : almost all math packages are using it.
For most Monte-Carlo programs : it is quite sufficiently random. It passes many tests including hard ones and Knuth criteria. You need a pretty high level of randomness to find the limits of this monster.
I think that this kind of <discussion> has already occurred many times for random number generators.
There is a saying in this area (Von Neumann) :
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
Best regards, Simon Plouffe
Le 2021-01-31 à 02:49, Fred Lunnon a écrit :
<< The Mersenne Twister is a procedure to produce very good random numbers. >> However, for a more nuanced view see https://arxiv.org/pdf/1910.06437.pdf
WFL
On 1/31/21, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even).
1/7 = 0.142857 and 142 + 857 = 999.
Numbers have to be to a multiple of 2 or 5 within the factorization.
1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19.
Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m.
This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft).
Best regards, Simon Plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Even as a non-cryptographic PRNG, MT19937 is still pretty bad: it fails several of the statistical tests in the TestU01 'BigCrush' battery. By comparison, Melissa O'Neill's PCG is a great non-cryptographic PRNG (very fast, very compact, and passes TestU01 even when you restrict the state space): https://www.pcg-random.org/index.html Daniel Lemire has written a review of this generator: https://lemire.me/blog/2017/08/15/on-melissa-oneills-pcg-random-number-gener... Another good generator is George Marsaglia's Xorshift* 64/32 -- that is to say, the upper 32 bits of the 64-bit output -- as described here: https://en.wikipedia.org/wiki/Xorshift#xorshift* As a side-note, Sebastian Vigna seems to have a chip (or maybe a full silicon wafer) on his shoulder regarding O'Neill and her PRNGs. See, for example, this: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html Best wishes, Adam P. Goucher
Sent: Sunday, January 31, 2021 at 2:10 AM From: "Simon Plouffe" <simon.plouffe@gmail.com> To: math-fun@mailman.xmission.com Subject: Re: [math-fun] Reciprocals of integers in binary
Yes, I am aware that MT19937 is not perfect and also that it is not good enough for cryptography. But : almost all math packages are using it.
For most Monte-Carlo programs : it is quite sufficiently random. It passes many tests including hard ones and Knuth criteria. You need a pretty high level of randomness to find the limits of this monster.
I think that this kind of <discussion> has already occurred many times for random number generators.
There is a saying in this area (Von Neumann) :
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
Best regards, Simon Plouffe
Le 2021-01-31 à 02:49, Fred Lunnon a écrit :
<< The Mersenne Twister is a procedure to produce very good random numbers. >>
However, for a more nuanced view see https://arxiv.org/pdf/1910.06437.pdf
WFL
On 1/31/21, Simon Plouffe <simon.plouffe@gmail.com> wrote:
Hello, this is also true in base 10. But with conditions. The period needs to be even. For primes it is always true (if the period is even).
1/7 = 0.142857 and 142 + 857 = 999.
Numbers have to be to a multiple of 2 or 5 within the factorization.
1/323 in base 10 has 144 digits from which the first 72 are complement to the other half, 323 = 17*19.
Important remark : If you take any integer m and if you can tell which half you are or another way of saying it : if you can tell where the half period is : this is enough information to factor m. Of course, a number m of let's say 300 digits could have a very long period when we compute 1/m.
This fact was taken into account when they constructed the Mersenne Twister by using the period of 2^19937 -1. It has 10^6002 digits. The Mersenne Twister is a procedure to produce very good random numbers. So good that these days, most of the serious math programs uses it . (even excel and microsoft).
Best regards, Simon Plouffe
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Adam P. Goucher -
Allan Wechsler -
Dan Asimov -
Fred Lunnon -
Keith F. Lynch -
Simon Plouffe