Long primes
A long prime (the definition that will be used
here) are primes whose reciprocals (in decimal) have
a period length of one less than
the prime number (also expressed in decimal).
Long primes are also known as:
- base ten cyclic numbers
- full reptend primes
- golden primes
- long period primes
- maximal period primes
- proper primes
- 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 other 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
- the Wikipedia webpage: full reptend prime.
- the MathWorld webpage: full reptend prime.
- the OEIS webpage: A1913.
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- define TRUE 1
- define FALSE 0
typedef int bool;
void sieve(int limit, int primes[], int *count) {
bool *c = calloc(limit + 1, sizeof(bool)); // composite = TRUE
// no need to process even numbers
int i, p = 3, p2, n = 0;
while (TRUE) {
p2 = p * p;
if (p2 > limit) break;
for (i = p2; i <= limit; i += 2 * p) c[i] = TRUE;
while (TRUE) {
p += 2;
if (!c[p]) break;
}
}
for (i = 3; i <= limit; i += 2) {
if (!c[i]) primes[n++] = i;
}
*count = n;
free(c);
}
// finds the period of the reciprocal of n int findPeriod(int n) {
int i, r = 1, rr, period = 0;
for (i = 1; i <= n + 1; ++i) {
r = (10 * r) % n;
}
rr = r;
while (TRUE) {
r = (10 * r) % n;
period++;
if (r == rr) break;
}
return period;
}
int main() {
int i, prime, count = 0, index = 0, primeCount, longCount = 0;
int *primes, *longPrimes;
int numbers[] = {500, 1000, 2000, 4000, 8000, 16000, 32000, 64000};
int totals[8];
primes = calloc(6500, sizeof(int));
longPrimes = calloc(2500, sizeof(int));
sieve(64000, primes, &primeCount);
for (i = 0; i < primeCount; ++i) {
prime = primes[i];
if (findPeriod(prime) == prime - 1) {
longPrimes[longCount++] = prime;
}
}
for (i = 0; i < longCount; ++i) {
if (longPrimes[i] > numbers[index]) {
totals[index++] = count;
}
count++;
}
totals[7] = count;
printf("The long primes up to 500 are:\n");
printf("[");
for (i = 0; i < totals[0]; ++i) {
printf("%d ", longPrimes[i]);
}
printf("\b]\n");
printf("\nThe number of long primes up to:\n");
for (i = 0; i < 8; ++i) {
printf(" %5d is %d\n", numbers[i], totals[i]);
}
free(longPrimes);
free(primes);
return 0;
}</lang>
- Output:
The long primes up to 500 are:
[7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499]
The number of long primes up to:
500 is 35
1000 is 60
2000 is 116
4000 is 218
8000 is 390
16000 is 716
32000 is 1300
64000 is 2430
Go
<lang go>package main
import "fmt"
func sieve(limit int) []int {
var primes []int
c := make([]bool, limit+1) // composite = true
// no need to process even numbers
p := 3
for {
p2 := p * p
if p2 > limit {
break
}
for i := p2; i <= limit; i += 2 * p {
c[i] = true
}
for {
p += 2
if !c[p] {
break
}
}
}
for i := 3; i <= limit; i += 2 {
if !c[i] {
primes = append(primes, i)
}
}
return primes
}
// finds the period of the reciprocal of n func findPeriod(n int) int {
r := 1
for i := 1; i <= n+1; i++ {
r = (10 * r) % n
}
rr := r
period := 0
for {
r = (10 * r) % n
period++
if r == rr {
break
}
}
return period
}
func main() {
primes := sieve(64000)
var longPrimes []int
for _, prime := range primes {
if findPeriod(prime) == prime-1 {
longPrimes = append(longPrimes, prime)
}
}
numbers := []int{500, 1000, 2000, 4000, 8000, 16000, 32000, 64000}
index := 0
count := 0
totals := make([]int, len(numbers))
for _, longPrime := range longPrimes {
if longPrime > numbers[index] {
totals[index] = count
index++
}
count++
}
totals[len(numbers)-1] = count
fmt.Println("The long primes up to 500 are: ")
fmt.Println(longPrimes[:totals[0]])
fmt.Println("\nThe number of long primes up to: ")
for i, total := range totals {
fmt.Printf(" %5d is %d\n", numbers[i], total)
}
}</lang>
- Output:
The long primes up to 500 are:
[7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499]
The number of long primes up to:
500 is 35
1000 is 60
2000 is 116
4000 is 218
8000 is 390
16000 is 716
32000 is 1300
64000 is 2430
Kotlin
<lang scala>// Version 1.2.60
fun sieve(limit: Int): List<Int> {
val primes = mutableListOf<Int>()
val c = BooleanArray(limit + 1) // composite = true
// no need to process even numbers
var p = 3
while (true) {
val p2 = p * p
if (p2 > limit) break
for (i in p2..limit step 2 * p) c[i] = true
while (true) {
p += 2
if (!c[p]) break
}
}
for (i in 3..limit step 2) {
if (!c[i]) primes.add(i)
}
return primes
}
// finds the period of the reciprocal of n fun findPeriod(n: Int): Int {
var r = 1
for (i in 1..n + 1) r = (10 * r) % n
val rr = r
var period = 0
while (true) {
r = (10 * r) % n
period++
if (r == rr) break
}
return period
}
fun main(args: Array<String>) {
val primes = sieve(64000)
val longPrimes = mutableListOf<Int>()
for (prime in primes) {
if (findPeriod(prime) == prime - 1) {
longPrimes.add(prime)
}
}
val numbers = listOf(500, 1000, 2000, 4000, 8000, 16000, 32000, 64000)
var index = 0
var count = 0
val totals = IntArray(numbers.size)
for (longPrime in longPrimes) {
if (longPrime > numbers[index]) {
totals[index++] = count
}
count++
}
totals[numbers.lastIndex] = count
println("The long primes up to 500 are:")
println(longPrimes.take(totals[0]))
println("\nThe number of long primes up to:")
for ((i, total) in totals.withIndex()) {
System.out.printf(" %5d is %d\n", numbers[i], total)
}
}</lang>
- Output:
The long primes up to 500 are:
[7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499]
The number of long primes up to:
500 is 35
1000 is 60
2000 is 116
4000 is 218
8000 is 390
16000 is 716
32000 is 1300
64000 is 2430
Perl 6
Not very fast as the numbers get larger. 64000 takes a little over 15 minutes on my computer. 😕 <lang perl6>my @long-primes = lazy (1..*).grep(*.is-prime).hyper(:8degree, :8batch).grep({1+(1/$_).base-repeating[1].chars == $_});
put "Long primes ≤ 500:\n", @long-primes[^(@long-primes.first: * > 500, :k)];
say "\nNumber of long primes ≤ $_: ", +@long-primes[^(@long-primes.first: * > $_, :k)]
for 500, 1000, 2000, 4000, 8000, 16000, 32000, 64000;</lang>
- Output:
Long primes ≤ 500: 7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499 Number of long primes ≤ 500: 35 Number of long primes ≤ 1000: 60 Number of long primes ≤ 2000: 116 Number of long primes ≤ 4000: 218 Number of long primes ≤ 8000: 390 Number of long primes ≤ 16000: 716 Number of long primes ≤ 32000: 1300 Number of long primes ≤ 64000: 2430
REXX
For every doubling of the limit, it takes about roughly 8 times longer to compute the long primes.
uses odd numbers
<lang rexx>/*REXX pgm calculates/displays base ten long primes (AKA golden primes, proper primes,*/ /*───────────────────── maximal period primes, long period primes, full reptend primes).*/ parse arg a /*obtain optional argument from the CL.*/ if a= | a="," then a= '500 -500 -100 -2000 -4000 -8000 -16000' /*use the default?*/
do k=1 for words(a); H=word(a, k) /*step through the list of high limits.*/
neg= H<1 /*used as an indicator to display count*/
H= abs(H) /*obtain the absolute value of H. */
numeric digits max(H, 500) /*insure enough dec digs for periodLen.*/
$= /*the list of long primes (so far). */
do j=7 to H by 2 /*start with 7, just use odd integers.*/
if .len(j) + 1 \== j then iterate /*period length too small? " " " */
$=$ j /*add the long prime to the $ list.*/
end /*j*/
say
if neg then do; say 'number of long primes ≤ ' H " is: " words($); end
else do; say 'list of long primes ≤ ' H":"; say strip($); end
end /*k*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ .len: procedure; parse arg x -1 z; y=9 /*obtain the argument from the caller. */
if z==5 then return 0 /*if the last digit is 5, then skip. */
_=1
do while y//x \== 0; y= y'9'; _= length(y)
end /*while*/
return _</lang>
list of long primes ≤ 500: 7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499 number of long primes ≤ 500 is: 35 number of long primes ≤ 1000 is: 60 number of long primes ≤ 2000 is: 116 number of long primes ≤ 4000 is: 218 number of long primes ≤ 8000 is: 390 number of long primes ≤ 16000 is: 716 number of long primes ≤ 32000 is: 1300
uses primes
This REXX version is about 15% faster than the 1st REXX version (becauses it only tests primes). <lang rexx>/*REXX pgm calculates/displays base ten long primes (AKA golden primes, proper primes,*/ /*───────────────────── maximal period primes, long period primes, full reptend primes).*/ parse arg a /*obtain optional argument from the CL.*/ if a= | a="," then a= '500 -500 -1000 -2000 -4000 -8000 -16000 -32000' /*use default?*/ m=0; aa=words(a) /* [↑] two list types of low primes. */
do j=1 for aa; m= max(m, abs(word(a, j))) /*find the maximum argument in the list*/ end /*j*/
call genP /*go and generate some primes. */
do k=1 for aa; H=word(a, k) /*step through the list of high limits.*/
neg= H<1 /*used as an indicator to display count*/
H= abs(H) /*obtain the absolute value of H. */
numeric digits max(H, 500) /*insure enough dec digs for periodLen.*/
$= /*the list of long primes (so far). */
do j=7 to H by 2
if \@.j then iterate /*Is J not a prime? Then skip it. */
if .len(j) + 1 \== j then iterate /*period length too small? " " " */
$=$ j /*add the long prime to the $ list.*/
end /*j*/ /* [↑] some pretty weak prime testing.*/
say
if neg then do; say 'number of long primes ≤ ' H " is: " words($); end
else do; say 'list of long primes ≤ ' H":"; say strip($); end
end /*k*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: @.=0; @.2=1; @.3=1; @.5=1; @.7=1; @.11=1; !.=0; !.1=2; !.2=3; !.3=5; !.4=7; !.5=11
#=5 /*the number of primes (so far). */
do g=!.#+2 by 2 until #>=m /*gen enough primes to satisfy max A. */
do d=2 until !.d**2 > g /*only divide up to square root of X. */
if g // !.d == 0 then iterate g /*Divisible? Then skip this integer. */
end /*d*/ /* [↓] a spanking new prime was found.*/
#=#+1; @.g=1; !.#=g /*bump P counter; assign P, add to P's.*/
end /*g*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/ .len: procedure; parse arg x; _=1; y=9 /*obtain the argument from the caller. */
do while y//x \== 0; y= y'9'; _= length(y)
end /*while*/
return _</lang>
- output is identical to the 1st REXX version.