The period of the reciprocal of a prime number is the number of decimal places in 1/p until it begins to repeat. E.g., 1/7 = 0.142857142857..., so the period is 6. The period will always be less than the number since by long division it will start to repeat as soon as a remainder repeats.
I've noticed that the period seems to always divide evenly into one-less-than the number, e.g., 1/5 = 0.200..., so the period is 2, and (5 - 1) % 2 == 0. The period for 60013 is 5001, and 60012 % 5001 == 0.
Does anyone know why this is the case? I've tested it for odd primes up to ten million.
Here's a C program I wrote to test it. It will take quite a while to run for 10,000,000 since as the primes get higher it takes longer and longer.
I mean I don't feel like doing any math right now, my brain is fried from other work, but it's probably a corollary of "Fermat's Little Theorem" or a similar theorem. https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
@jonnin, I don't think you understand how the program works. It only calculates the primes once each. It's certainly not the primes that are slowing it down. It's the long division to calculate the period.
where isprime starts at 3 or whatever and trundles along.
so ..
isprime(1001) muddles through 3,5,7,11,...
and then
isprime(1003) muddles through 3,5,7,11,...
which is much slower than
if(table[n])
where table is pre calculated via the sieve, without all that iteration, or better yet, loaded from a file or something generated offline.
that said the long division could be a worse bottleneck, if you tested it I believe you.
do you care enough to dig into that as well?
As usual, you simply have no idea what you are talking about.
I would tell you to "think for once", but that is obviously a foreign concept to you.
This program completes in a few seconds, while the original program (with HIGH as 10000000, of course) takes well over an hour.
#include <stdio.h>
#define LOW 3 // should be odd >= 3
#define HIGH 10000000
#define TYPE unsigned
int isprime(TYPE n) {
//if (n < 2) return 0;
//if (n % 2 == 0) return n == 2;
for (TYPE d = 3; d * d <= n; d += 2)
if (n % d == 0) return 0;
return 1;
}
int main() {
unsigned count = 0;
for (TYPE n = LOW % 2 ? LOW : LOW + 1; n <= HIGH; n += 2)
if (isprime(n))
++count;
printf("%u\n", count);
return 0;
}
The nearest prime to 10,000,000 is 9,999,991 (Prime No: 664579 ? ) so that makes the period calculation fairly time consuming - an interesting exercise to program.
"Time consuming" as in about 0.02 seconds. :-) Still, if every prime took that long the whole thing would take almost four hours.
Each one depends on the actual period, which can of course be far smaller than the number itself. The period of 9999991 is 1666665, whereas the period of 9999943 is 9999942. So 9999943 takes three or four times as long.
I can't think of how to speed it up and there's not really much point. From tests, I calculated it would take less than two hours, and since I was interested in the answer, I just let it run as is.