Circular primes
- Definitions
A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will also be prime.
For example: 1193 is a circular prime, since 1931, 9311 and 3119 are all also prime.
Note that a number which is a cyclic permutation of a smaller circular prime is not considered to be itself a circular prime. So 13 is a circular prime but 31 is not.
A repunit (denoted by R) is a number whose base 10 representation contains only the digit 1.
For example: R(2) = 11 and R(5) = 11111 are repunits.
- Task
- Find the first 19 circular primes.
- If your language has access to arbitrary precision integer arithmetic, given that they are all repunits, find the next 4 circular primes.
- (Stretch) Determine which of the following repunits are probably circular primes: R(5003), R(9887), R(15073), R(25031), R(35317) and R(49081). The larger ones may take a long time to process so just do as many as you reasonably can.
- See also
- Wikipedia article - Circular primes.
- Wikipedia article - Repunit.
- OEIS sequence A016114 - Circular primes.
Go
<lang go>package main
import (
"fmt" big "github.com/ncw/gmp" "strings"
)
// OK for 'small' numbers. func isPrime(n int) bool {
switch { case n < 2: return false case n%2 == 0: return n == 2 case n%3 == 0: return n == 3 default: d := 5 for d*d <= n { if n%d == 0 { return false } d += 2 if n%d == 0 { return false } d += 4 } return true }
}
func repunit(n int) *big.Int {
ones := strings.Repeat("1", n) b, _ := new(big.Int).SetString(ones, 10) return b
}
var circs = []int{2, 3, 5, 7}
// binary search is overkill for a small number of elements func alreadyFound(n int) bool {
for _, i := range circs { if i == n { return true } } return false
}
func isCircular(n int) bool {
nn := n pow := 1 // will eventually contain 10 ^ d where d is number of digits in n for nn > 0 { pow *= 10 nn /= 10 } nn = n for { nn *= 10 f := nn / pow // first digit nn += f * (1 - pow) if alreadyFound(nn) { return false } if nn == n { break } if !isPrime(nn) { return false } } return true
}
var digits = [5]int{0, 1, 3, 7, 9}
func to01379(n int) int {
sum := 0 pow := 1 for n > 0 { d := n % 5 sum += digits[d] * pow n /= 5 pow *= 10 } return sum
}
func main() {
fmt.Println("The first 19 circular primes are:") count := 4 for i := 6; count < 19; i++ { j := to01379(i) if j%10 == 0 || !isPrime(j) { continue } if !isPrime(j) { continue } if isCircular(j) { count++ circs = append(circs, j) } } fmt.Println(circs) fmt.Println("\nThe next 4 circular primes, in repunit format, are:") count = 0 var rus []string for i := 7; count < 4; i++ { if repunit(i).ProbablyPrime(10) { count++ rus = append(rus, fmt.Sprintf("R(%d)", i)) } } fmt.Println(rus) fmt.Println("\nThe following repunits are probably circular primes:") for _, i := range []int{5003, 9887, 15073, 25031, 35317, 49081} { fmt.Printf("R(%-5d) : %t\n", i, repunit(i).ProbablyPrime(10)) }
}</lang>
- Output:
The first 19 circular primes are: [2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939 199933] The next 4 circular primes, in repunit format, are: [R(19) R(23) R(317) R(1031)] The following repunits are probably circular primes: R(5003 ) : false R(9887 ) : false R(15073) : false R(25031) : false R(35317) : false R(49081) : true
Raku
<lang perl6>#!/usr/bin/env raku
- 20200406 Raku programming solution
sub isCircular(\n) {
return False unless n.is-prime; my @circular = n.comb; for (1..^@circular.elems) { return False if n > my $rotated = @circular.rotate($_).join; return False unless $rotated.is-prime; } return True
}
say "The first 19 circular primes are:"; say ((1..∞).grep: { isCircular($_) })[^18];
say "The next 4 circular primes, in repunit format, are:"; loop ( my $i = 7, my $count = 0; $count < 4; $i++ ) {
my $target = (1 xx $i).join.Int; if $target.is-prime { say "R(",$i,")"; $count++ }
}</lang>
- Output:
The first 19 circular primes are: (2 3 5 7 11 13 17 37 79 113 197 199 337 1193 3779 11939 19937 193939) The next 4 circular primes, in repunit format, are: R(19) R(23) R(317) R(1031)