Period of the reciprocals of prime numbers

[DizzyDon]

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.

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <time.h>

#define LOW             3         // should be odd >= 3
#define HIGH            1000000
#define REPORT          100000    // must be even

#define TYPE            unsigned
#define BITS            (sizeof(TYPE) * CHAR_BIT)
#define NUM_ELEMENTS(x) (((x) + BITS - 1) / BITS)
#define SET_BIT(x)      ba[(x) / BITS] |= (1u << ((x) % BITS))
#define TEST_BIT(x)     ba[(x) / BITS] &  (1u << ((x) % BITS))

// bit array to test for repeated remainder
TYPE ba[NUM_ELEMENTS(HIGH)];

void check_recip_count(TYPE n) {
    TYPE d = 1, count = 0;
    memset(ba, 0, NUM_ELEMENTS(n) * sizeof *ba);
    for (;;) {
        if (d >= n) d -= d / n * n;
        if (TEST_BIT(d)) break;
        SET_BIT(d);
        d *= 10;
        ++count;
    }
    if ((n - 1) % count != 0) // Conjecture: this is never true
        printf("%8u %8u\n", n, count);
}

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() {
    clock_t start = clock();
    for (TYPE n = LOW % 2 ? LOW : LOW + 1; n <= HIGH; n += 2) {
        if ((n - 1) % REPORT == 0) {
            clock_t end = clock();
            printf("=> %9u  %9.3fs\n",
                   n, (double)(end - start) / CLOCKS_PER_SEC);
            start = end;
        }
        if (isprime(n))
            check_recip_count(n);
    }
    return 0;
}

[Ganado]

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

In fact, I searched for 'fermat's little theorem prime reciprical period' and found stuff like:
https://manasataramgini.wordpress.com/2018/11/03/fermats-little-theorem-and-the-periods-of-the-reciprocals-of-primes/

[DizzyDon]

Thanks, Ganado. That looks promising. I'll try reading it tomorrow.

[againtry]

Sounds close, or better ...
https://www.johndcook.com/blog/2018/05/10/reciprocals-of-primes/
then,
https://www.johndcook.com/blog/2016/10/18/periods-of-fractions/


and for the sake of completeness ...
https://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html

[jonnin]

it runs slowly because you keep redoing your primes.
make a lookup table (vector bool) one time and refer back to it and it should cruise right along.

I got nothing on the math side.

[DizzyDon]

@againtry, Thanks. That looks like good stuff.

@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.

[jonnin]

I can be wrong.
that said, what I see, reduced:

for(n = blah blah)
{
if(isprime(n));
{meh}
}

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?

[DizzyDon]

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;
}

[againtry]

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.

The proof shatters hopes and dreams :(

[DizzyDon]

"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.

[againtry]

1,666,665 repeating digits in .02 seconds is no mean feat.