

A   long prime   (as defined here)   is a prime number whose reciprocal   (in decimal)   has
a   period length   of one less than the prime number.


Long primes   are also known as:

   base ten cyclic numbers
   full reptend primes
   golden primes
   long period primes
   maximal period primes
   proper primes


Another definition:   primes   p   such that the decimal expansion of   1/p   has period   p-1,   which is the greatest period possible for any integer.



Example

7   is the first long prime,   the reciprocal of seven
is   1/7,   which
is equal to the repeating decimal fraction   0.142857142857···

The length of the   repeating   part of the decimal fraction
is six,   (the underlined part)   which is one less
than the (decimal) prime number   7.

Thus   7   is a long prime.



There are other (more) general definitions of a   long prime   which
include wording/verbiage for bases other than ten.



Task

   Show all long primes up to   500   (preferably on one line).
   Show the   number   of long primes up to         500
   Show the   number   of long primes up to      1,000
   Show the   number   of long primes up to      2,000
   Show the   number   of long primes up to      4,000
   Show the   number   of long primes up to      8,000
   Show the   number   of long primes up to   16,000
   Show the   number   of long primes up to   32,000
   Show the   number   of long primes up to   64,000   (optional)
   Show all output here.


Also see

   Wikipedia: full reptend prime
   MathWorld: full reptend prime
   OEIS: A001913


 
PROGRAM "longprimes"
VERSION "0.0002"
 
DECLARE FUNCTION Entry()
INTERNAL FUNCTION Sieve(limit&, primes&[], count%)
INTERNAL FUNCTION FindPeriod(n&)
 
FUNCTION Entry()
  DIM numbers&[7]
  numbers&[0] = 500
  numbers&[1] = 1000
  numbers&[2] = 2000
  numbers&[3] = 4000
  numbers&[4] = 8000
  numbers&[5] = 16000
  numbers&[6] = 32000
  numbers&[7] = 64000
  numberUpperBound% = UBOUND(numbers&[])
  DIM totals%[numberUpperBound%]
  DIM primes&[6499]
  PRINT "Please wait."
  PRINT
  Sieve(64000, @primes&[], @primeCount%)
  DIM longPrimes&[primeCount% - 1] ' Surely longCount% < primeCount%
  longCount% = 0
  FOR i% = 0 TO primeCount% - 1
    prime& = primes&[i%]
    IF FindPeriod(prime&) = prime& - 1 THEN
      longPrimes&[longCount%] = prime&
      INC longCount%
    END IF
  NEXT i%
  count% = 0
  index% = 0
  FOR i% = 0 TO longCount% - 1
    IF longPrimes&[i%] > numbers&[index%] THEN
      totals%[index%] = count%
      INC index%
    END IF
    INC count%
  NEXT i%
  totals%[numberUpperBound%] = count%
  PRINT "The long primes up to"; numbers&[0]; " are:"
  PRINT "[";
  FOR i% = 0 TO totals%[0] - 2
    PRINT STRING$(longPrimes&[i%]); " ";
  NEXT i%
  IF totals%[0] > 0 THEN
    PRINT STRING$(longPrimes&[totals%[0] - 1]);
  END IF
  PRINT "]"
  PRINT
  PRINT "The number of long primes up to:"
  FOR i% = 0 TO numberUpperBound%
    PRINT FORMAT$("  #####", numbers&[i%]); " is"; totals%[i%]
  NEXT i%
END FUNCTION
 
FUNCTION Sieve(limit&, primes&[], count%)
  DIM c@[limit&]
  FOR i& = 0 TO limit&
    c@[i&] = 0
  NEXT i&
  ' No need to process even numbers
  p% = 3
  n% = 0
  p2& = p% * p%
  DO WHILE p2& <= limit&
    FOR i& = p2& TO limit& STEP 2 * p%
      c@[i&] = 1
    NEXT i&
    DO
      p% = p% + 2
    LOOP UNTIL !c@[p%]
    p2& = p% * p%
  LOOP
  FOR i& = 3 TO limit& STEP 2
    IFZ c@[i&] THEN
      primes&[n%] = i&
      INC n%
    END IF
  NEXT i&
  count% = n%
END FUNCTION
 
' Finds the period of the reciprocal of n&
FUNCTION FindPeriod(n&)
  r& = 1
  period& = 0
  FOR i& = 1 TO n& + 1
    r& = (10 * r&) MOD n&
  NEXT i&
  rr& = r&
  DO
    r& = (10 * r&) MOD n&
    INC period&
  LOOP UNTIL r& = rr&
END FUNCTION period&
 
END PROGRAM
 