Task — Long primes

Write a script to generate first 5 Long Primes. A prime number $p is called a Long Prime if 1 / $p has an infinite decimal expansion repeating every $p - 1 digits.

Examples

Example 1:
7 is a long prime since 1/7 = 0.142857142857...
The repeating part (142857) size is 6 ie one less than 
the prime number 7.

Example 2:
17 is a long prime since 1/17 = 
0.05882352941176470588235294117647...
The repeating part (0588235294117647) size is 16 ie one 
less than the prime number 17.

Example 3:
2 is not a long prime as 1/2 = 0.5.
There is no repeating part in this case.

Analysis

My solution of this challenge is simple in principle, although not so simple to express in Perl. The steps are:

1. Loop over prime numbers (obtained from a sieve of Eratosthenes) from 2 upwards.
2. Calculate 1 / $p. We need to calculate this quotient to at least 2 * ($p - 1) significant digits - the digits following 0. or 0.0 etc.
3. Examine the quotient to determine the shortest repeat within it.
4. Report $p as a long prime if that length is $p - 1

Calculation of the quotient can no doubt be done using a module, but probably everyone learned to do long division in primary school, and we can easily replicate that in Perl. Note that in order to dissuade Perl from treating a long string of digits as a floating point number I have prefixed the string with '* '.

Finding the shortest repeat is simply a case of seeing whether the significant digits in the quotient repeat after 1, 2, 3 .. $p - 1 places - stopping as soon as a repeating pattern is found. If that is $p - 1 digits, than $p is a long prime, or else it isn't. We are required only to find the first 5, but I calculated all those under 100, which are 9 in number.

Script

#!/usr/bin/perl

# Peter Campbell Smith - 2021-11-15
# PWC 139 task 2

use v5.20;
use warnings;
use strict;

my (@primes, $prime, $limit, $j, $inverse, $digits, $is_long, $min_repeat, $min_repeat_length, $max_prime);

# make sieve of Eratosthenes to generate primes
$max_prime = 100;
@primes = make_sieve($max_prime);   # primes[j] = 1 if j is prime

# loop over primes
for $prime (2 .. $max_prime) {
    next unless $primes[$prime];
    
    # calculate the inverse
    $inverse = precise_inverse($prime);
    
    # get the first ($prime - 1) digits
    $digits = substr($inverse, 3, $prime - 1);
    next unless substr($inverse, 2 + $prime, $prime - 1) eq $digits;
    
    # check for the smallest number of repeating digits
    $min_repeat = min_repeat($inverse);
    $min_repeat_length = length($min_repeat);   
    next unless $min_repeat_length == $prime - 1;
    
    # format and issue result, if successful
    $inverse =~ m|(0\.0*)(.*)|;
    $inverse = $1 . substr($2, 0, 2 * $min_repeat_length);
    say qq[$prime is a long prime since 1/$prime is $inverse\n] .
        qq[The repeating part ($min_repeat) size is ] . $min_repeat_length . 
        qq[ ie 1 less than the prime number $prime\n] if ($min_repeat_length == $prime - 1);
    
}

sub make_sieve {
    
    # make sieve of Eratosthenes
    my ($arg, $j, $k, @sieve);
    
    # set all values provisionally to 1 (ie prime)
    $arg = $_[0];
    for $j (0 .. $arg) {
        $sieve[$j] = 1;
    }
    
    # for each prime in turn, set its multiples to 0 (ie not prime)
    for $j (2 .. $arg) {
        next unless $sieve[$j];   # $j is not prime     
        last if $j ** 2 > $arg;
        for $k ($j .. $arg) {
            last if $k * $j > $arg;
            $sieve[$k * $j] = 0;
        }
    }
    return @sieve;
}

sub precise_inverse {
    
    my ($divisor, $remainder, $quotient, $q, %seen); 

    # returns inverse of argument using long division   
    $divisor = $_[0];
    $remainder = 1;
    $quotient = '*0.';

    # one digit at a time
    while (1) {
        $remainder *= 10;
        $q = int($remainder / $divisor);
        $remainder = ($remainder - $q * $divisor);
        $quotient .= $q;
        
        # check that it is at least twice (p - 1) long so that we can check for repeat
        if ($quotient =~ m|\*0\.0*(.*)|) {
            last if length($1) >= 2 * ($divisor - 1);
        }
    }
    return $quotient;
}

sub min_repeat {
    
    my ($test, $test_length, $j, $snippet, $snippets);
    
    # returns length of shortest repeating string 
    $_[0] =~ m|\*0\.0*(.*)|;
    
    # check to see if the first $j digits repeat to form $test
    $test = $1;
    $test_length = length($test);
    for $j (1 .. int($test_length / 2)) {
        $snippet = substr($test, 0, $j);
        $snippets = $snippet x (int($test_length / length($snippet) + 1));
        $snippets = substr($snippets, 0, $test_length);
        return $snippet if $snippets eq $test;
    }
}

Output

7 is a long prime since 1/7 is 0.142857142857
The repeating part (142857) size is 6 ie 1 less than the 
prime number 7

17 is a long prime since 1/17 is 
0.058823529411764705882352941176470
The repeating part (5882352941176470) size is 16 ie 1
less than the prime number 17

19 is a long prime since 1/19 is 
0.0526315789473684210526315789473684210
The repeating part (526315789473684210) size is 18 ie 1
less than the prime number 19

23 is a long prime since 1/23 is 
0.043478260869565217391304347826086956521739130
The repeating part (4347826086956521739130) size is 22
ie 1 less than the prime number 23

29 is a long prime since 1/29 is 
0.0344827586206896551724137931034482758620689655172413793
10
The repeating part (3448275862068965517241379310) size is
28 ie 1 less than the prime number 29

47 is a long prime since 1/47 is 0.0212765957446808510638
297872340425531914893617021276595744680851063829787234042
55319148936170
The repeating part (2127659574468085106382978723404255319
148936170) size is 46 ie 1 less than the prime number 47

59 is a long prime since 1/59 is 0.0169491525423728813559
322033898305084745762711864406779661016949152542372881355
93220338983050847457627118644067796610
The repeating part (1694915254237288135593220338983050847
457627118644067796610) size is 58 ie 1 less than the 
prime number 59

61 is a long prime since 1/61 is 0.0163934426229508196721
311475409836065573770491803278688524590163934426229508196
721311475409836065573770491803278688524590
The repeating part (1639344262295081967213114754098360655
73770491803278688524590) size is 60 ie 1 less than the
prime number 61

97 is a long prime since 1/97 is 0.0103092783505154639175
257731958762886597938144329896907216494845360824742268041
237113402061855670103092783505154639175257731958762886597
938144329896907216494845360824742268041237113402061855670
The repeating part (1030927835051546391752577319587628865
979381443298969072164948453608247422680412371134020618556
70) size is 96 ie 1 less than the prime number 97