Perl Weekly Challenge 139: Long Primes

\(7\) is a long prime since \(\frac{1}{7} = 0.\overline{1428571}\). The repeating part (\(142857\)) size is \(6\) i.e. one less than the prime number \(7\).

Also \(17\) is a long prime since \(\frac{1}{17} = 0.\overline{0588235294117647}\). The repeating part (\(0588235294117647\)) size is \(16\) i.e. one less than the prime number \(17\).

Another example, \(2\) is not a long prime as \(\frac{1}{2} = 0.5\). There is no repeating part in this case.

Wikipedia call long primes Full reptend prime.

A naive method would be to take a prime number, and see whether its decimal fraction repeats. But that means, having to deal with floating point numbers, and that's hard in general.

For instance, in Perl, even a 64 bit perl, \(\frac{1}{23}\) equals 0.0434782608695652174. But that's enough to determine whether the fraction repeats with period 22 - as we only have 19 digits of precision. In many other languages, the situation is similar.

Luckily, there is an alternative way. As the Wikipedia page points out, for a full reptend prime \(p\), the quotient

\[ \frac{b^{p - 1} - 1}{p} \]

gives a cyclic number, where \(b\) is the base we are working in (so, for us \(b = 10\)).

Now, \(\frac{b^{p - 1} - 1}{p}\) becomes large quickly if \(p\) increases. For instance, if \(b = 10\) and \(p = 23\), the quotient is \(43478260869565217391\) which is larger than a 64 bit integer can hold.

We could use big integers to calculate the quotient, but that doesn't work for languages with no, or poor, support for large integers.

But there is a different way. We don't need the actual quotient. All we want to know is that the resulting number doesn't contain repeats. We can do this by performing long division and check all the intermediate results are different.

For instance, if \(b = 10\) and \(p = 7\), \(b^{p - 1} - 1\) equals \(999999\). On the left, we have the long division of those numbers. What we are interested in is the numbers left over after subtracting the appropriate multiple of \(7\), this the values below the lines (and without the dropped \(9\)). Here, they are \(9 - 7 = 2, 29 - 28 = 1, 19 - 14 = 2, 59 - 56 = 3, 39 - 35 = 4, 49 - 49 = 0\). There are no duplicates in this sequence, so the quotient doesn't repeat (\(\frac{10^6 - 1}{7} = 142857\)), and hence, \(7\) is a long prime.

But if we look at the long division of \(10^{12} - 1\) and \(13\) on the right, we see that the sequence is \(9, 8, 11, 2, 3, 0, 9, 8, 11, 2, 3, 0\). This sequence repeats, and hence the quotient repeats: \(\frac{10^{12} - 1}{13} = 076923076923\). This makes \(13\) not a long prime.

Note that in the latter case, we don't need to do the full calculation. As soon as we find an intermediate value we have seen before (here the \(9\)), we know the number is not a long prime, and there is no need to continue the calculations.

Now, we could just iterate over the primes and see if there are no repeats when doing the long division. But that would require us to generate primes. In Perl, we could use Math::Prime::Util, but not every language has such a module.

Instead, we just check every number starting from 2. Composite numbers will give a duplicate when doing the long division, so any number which passes the no-duplicates check has to be prime.

Input a number, hit Calculate, and it shows whether the number is a long prime or not.

Calculate

Each solution will contain two parts: a function is_long which takes a number, and returns a true or false value depending on whether the number is a long prime or not, and a main part which counts up from 2, skipping numbers which evenly divide 10, and then calls is_long, printing the numbers which are long primes, up to the required amount.

The is_long method will perform the long division described above. Note that we do not have to calculate a number of the form \(10^{p - 1} - 1\), where \(p\) is the argument to is_long. \(10^{p - 1} - 1\) will be a string of \(p - 1\) \(9\)s, so when performing the long division, we always "drop down" a \(9\).

The sequence \(a_n\) for a given number \(p\) can be calculated as follows:

\[ a_n = \begin{cases} 0 & \text{if } n = 0 \\ (10 * a_{n - 1} + 9) \mod p & \text{if } n > 0 \\ \end{cases} \]

We need \(p - 2\) terms of this sequence. If there are no duplicates, the given number is a long prime. Note that \(\forall i: 0 \leq a_i < p\).

The is_long function is now straight forward with the formula above:

my $BASE = 10;

sub is_long ($number) {
    my $rest = 0;
    my %seen;
    for (2 .. $number) {
        return 0 if $seen {$rest = ($rest * $BASE + $BASE - 1) % $number} ++;
    }
    return 1;
}

And the main function:

my $COUNT = 5;

my $number = 1;
while ($COUNT) {
    $number ++;
    next if $BASE % $number == 0;
    next unless is_long $number;
    say $number;
    $COUNT --;
}

Find the full program on GitHub.

The is-long function:

(define BASE  10)

(define (is-long number)
    (define seen (make-array 0 number))
    (define rest 0)
    (define r #t)

    (do ((i 2 (1+ i)))
        ((> i number))
        (set! rest (modulo (+ (* rest BASE) BASE -1) number))
        (if (= (array-ref seen rest) 1)
            (set! r #f))
        (array-set! seen 1 rest))

    r
)

And the main program:

(define COUNT  5)

(do ((number 2 (1+ number)))
    ((= COUNT 0))
    (cond ((= (modulo BASE number) 0) #f)
          ((is-long number)
               (begin (display number)(newline)
                      (set! COUNT (- COUNT 1))))))

Find the full program on GitHub.