Write a script to generate first 5

`Long Primes`

.A prime number (p) is called Long Prime if (1/p) has an infinite decimal expansion repeating every (p-1) digits.

\(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.

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.

Implementations in other languages are very similar to Perl solution. We also have solutions in: AWK, Bash, bc, C, Go, Java, Lua, Node.js, Pascal, Python, R, Ruby, and Tcl.