rosettacode.org

 
 package main
 
 import (
     "fmt"
     "math"
     //"os"
     "sort"
 )
 
 type Signed interface {
     ~int | ~int8 | ~int16 | ~int32 | ~int64
 }
 
 type Unsigned interface {
     ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
 }
 
 type Integer interface {
     Signed | Unsigned
 }
 
 type Float interface {
     ~float32 | ~float64
 }
 
 type Complex interface {
     ~complex64 | ~complex128
 }
 
 type Ordered interface {
     Integer | Float | ~string
 }
 
 
 type Int = Integer
 
 // Returns the larger of two integers.
 func Max[T Int](x, y T) T {
     if x > y {
         return x
     }
     return y
 }
 
 // Returns the smaller of two integers.
 func Min[T Int](x, y T) T {
     if x < y {
         return x
     }
     return y
 }
 
 // Returns the absolute value of an integer.
 func Abs[T Int](x T) T {
     if x < 0 {
         return -x
     }
     return x
 }
 
 // Returns the greatest common divisor of two integers.
 func Gcd[T Int](x, y T) T {
     for y != 0 {
         x, y = y, x%y
     }
     return x
 }
 
 // Returns the least common multiple of two integers.
 func Lcm[T Int](x, y T) T { return Abs(x*y) / Gcd(x, y) }
 
 // Returns whether or not an integer is prime.
 func IsPrime[T Int](n T) bool {
     switch {
     case n < 2:
         return false
     case n%2 == 0:
         return n == 2
     case n%3 == 0:
         return n == 3
     case n%5 == 0:
         return n == 5
     default:
         d := T(7)
         wheel := []T{4, 2, 4, 2, 4, 6, 2, 6}
         for {
             for _, w := range wheel {
                 if d*d > n {
                     return true
                 }
                 if n%d == 0 {
                     return false
                 }
                 d += w
             }
         }
         return true
     }
 }
 
 // Sieves for primes up to and including 'limit'.
 // Returns a bool slice 'c' of size (limit + 1) where:
 // c[i] is false if 'i' is prime or true if 'i' is composite.
 // Optionally processes even numbers >= 4.
 func PrimeSieve[T Int](limit T, processEven bool) []bool {
     limit++
     // True denotes composite, false denotes prime.
     c := make([]bool, limit) // all false by default
     c[0] = true
     c[1] = true
     if processEven {
         for i := T(4); i < limit; i += 2 {
             c[i] = true
         }
     }
     p := T(3) // Start from 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
             }
         }
     }
     return c
 }
 
 // Returns a slice of all primes up to and including 'limit'.
 func Primes[T Int](limit T) []T {
     c := PrimeSieve(limit, false)
     if limit < 2 {
         return []T{}
     }
     primes := []T{2}
     for i := T(3); i < T(len(c)); i += 2 {
         if !c[i] {
             primes = append(primes, i)
         }
     }
     return primes
 }
 
 // Sieves for primes up to and including 'n' and returns how many there are.
 // Uses an algorithm better suited to counting than the one used in the PrimeSieve method.
 func PrimeCount[T Int](n T) int {
     if n < 2 {
         return 0
     }
     if n == 2 {
         return 1
     }
     count := 1
     k := (n-3)/2 + 1
     marked := make([]bool, k) // all false by default
     limit := (T(math.Sqrt(float64(n)))-3)/2 + 1
     for i := T(0); i < limit; i++ {
         if !marked[i] {
             p := 2*i + 3
             s := (p*p - 3) / 2
             for j := s; j < k; j += p {
                 marked[j] = true
             }
         }
     }
     for i := T(0); i < k; i++ {
         if !marked[i] {
             count++
         }
     }
     return count
 }
 
 // Returns the prime factors of 'n' in order using a wheel with basis [2, 3, 5].
 func PrimeFactors[T Int](n T) []T {
     if n < 2 {
         return []T{}
     }
     inc := []T{4, 2, 4, 2, 4, 6, 2, 6}
     var factors []T
     for n%2 == 0 {
         factors = append(factors, 2)
         n = n / 2
     }
     for n%3 == 0 {
         factors = append(factors, 3)
         n = n / 3
     }
     for n%5 == 0 {
         factors = append(factors, 5)
         n = n / 5
     }
     for k, i := T(7), 0; k*k <= n; {
         if n%k == 0 {
             factors = append(factors, k)
             n = n / k
         } else {
             k += inc[i]
             i = (i + 1) % 8
         }
     }
     if n > 1 {
         factors = append(factors, n)
     }
     return factors
 }
 
 // Returns all the divisors of 'n' including 1 and 'n' itself.
 func Divisors[T Int](n T) []T {
     if n < 1 {
         return []T{}
     }
     var divisors []T
     var divisors2 []T
     i := T(1)
     k := T(1)
     if n%2 == 1 {
         k = 2
     }
     for ; i*i <= n; i += k {
         if n%i == 0 {
             divisors = append(divisors, i)
             j := n / i
             if j != i {
                 divisors2 = append(divisors2, j)
             }
         }
     }
     if len(divisors2) > 0 {
         ReverseInts(divisors2)
         divisors = append(divisors, divisors2...)
     }
     return divisors
 }
 
 // Returns all the divisors of 'n' excluding 'n'.
 func ProperDivisors[T Int](n T) []T {
     d := Divisors(n)
     c := len(d)
     if c <= 1 {
         return []T{}
     }
     return d[0 : len(d)-1]
 }
 
 // Reverses a slice of integers in place.
 func ReverseInts[T Int](s []T) {
     for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
         s[i], s[j] = s[j], s[i]
     }
 }
 
 // Returns a slice of an integer's digits in base b.
 func Digits[T Int](n T, b int) []int {
     if n == 0 {
         return []int{0}
     }
     var digits []int
     for n > 0 {
         digits = append(digits, int(n%T(b)))
         n /= T(b)
     }
     ReverseInts(digits)
     return digits
 }
 
 // Returns the sum of an integer's digits in base b.
 func DigitSum[T Int](n T, b int) int {
     sum := 0
     for n > 0 {
         sum += int(n % T(b))
         n /= T(b)
     }
     return sum
 }
 
 // Returns the sum of a slice of integers.
 func SumInts[T Int](a []T) T {
     sum := T(0)
     for _, i := range a {
         sum += i
     }
     return sum
 }
 
 // Returns the maximum of a slice of integers.
 func MaxInts[T Int](a []T) T {
     max := a[0]
     for _, i := range a[1:] {
         if i > max {
             max = i
         }
     }
     return max
 }
 
 // Returns the minimum of a slice of integers
 func MinInts[T Int](a []T) T {
     min := a[0]
     for _, i := range a[1:] {
         if i < min {
             min = i
         }
     }
     return min
 }
 
 // Adds thousand separators to an integer.
 func Commatize[T Int](n T) string {
     s := fmt.Sprintf("%d", n)
     if n < 0 {
         s = s[1:]
     }
     le := len(s)
     for i := le - 3; i >= 1; i -= 3 {
         s = s[0:i] + "," + s[i:]
     }
     if n >= 0 {
         return s
     }
     return "-" + s
 }
 
 // Prints a slice of integers in tabular form with a given row and column size
 // and optionally comma separators.
 func PrintTable[T Int](s []T, rowSize, colSize int, commas bool) {
     for i := 0; i < len(s); i++ {
         if !commas {
             fmt.Printf("%*d ", colSize, s[i])
         } else {
             fmt.Printf("%*s ", colSize, Commatize(s[i]))
         }
         if (i+1)%rowSize == 0 {
             fmt.Println()
         }
     }
     if len(s)%rowSize != 0 {
         fmt.Println()
     }
 }
 
 
 
 func main() {
     const limit = int(1e10)
     const maxIndex = 9
     primes := Primes(limit)
     anaprimes := make(map[int][]int)
     for _, p := range primes {
         digs := Digits(p, 10)
         key := 1
         for _, dig := range digs {
             key *= primes[dig]
         }
         if _, ok := anaprimes[key]; ok {
             anaprimes[key] = append(anaprimes[key], p)
         } else {
             anaprimes[key] = []int{p}
         }
     }
     largest := make([]int, maxIndex+1)
     groups := make([][][]int, maxIndex+1)
     for key := range anaprimes {
         v := anaprimes[key]
         nd := len(Digits(v[0], 10))
         c := len(v)
         if c > largest[nd-1] {
             largest[nd-1] = c
             groups[nd-1] = [][]int{v}
         } else if c == largest[nd-1] {
             groups[nd-1] = append(groups[nd-1], v)
         }
     }
     j := 1000
     for i := 2; i <= maxIndex; i++ {
         js := Commatize(j)
         ls := Commatize(largest[i])
         fmt.Printf("Largest group(s) of anaprimes before %s: %s members:\n", js, ls)
         sort.Slice(groups[i], func(k, l int) bool {
             return groups[i][k][0] < groups[i][l][0]
         })
         for _, g := range groups[i] {
             fmt.Printf("  First: %s  Last: %s\n", Commatize(g[0]), Commatize(g[len(g)-1]))
             //fmt.Printf("  %v\n", g)
         }
         // if i > 4 { os.Exit(0) }
         j *= 10
         fmt.Println()
     }
 }
 
 
 

 
 from itertools import count
 from itertools import islice
 from typing import Iterable
 from typing import Tuple
 
 import gmpy2
 
 
 def factorials() -> Iterable[int]:
     fact = 1
     for i in count(1):
         yield fact
         fact *= i
 
 
 def factorial_primes() -> Iterable[Tuple[int, int, str]]:
     for n, fact in enumerate(factorials()):
         if gmpy2.is_prime(fact - 1):
             yield (n, fact - 1, "-")
         if gmpy2.is_prime(fact + 1):
             yield (n, fact + 1, "+")
 
 
 def print_factorial_primes(limit=10) -> None:
     print(f"First {limit} factorial primes.")
     for n, fact_prime, op in islice(factorial_primes(), 1, limit + 1):
         s = str(fact_prime)
         if len(s) > 40:
             s = f"{s[:20]}...{s[-20:]} ({len(s)} digits)"
         print(f"{n}! {op} 1 = {s}")
 
 
 if __name__ == "__main__":
     import sys
     print_factorial_primes(int(sys.argv[1]) if len(sys.argv) > 1 else 40)
 
 
 

 
 from itertools import permutations
 from gmpy2 import is_prime
 
 
 def oeis36229(wanted=20):
     ''' get first [wanted] entries in OEIS A036229 '''
     for ndig in range(1, wanted + 1):
         if ndig < 21 or ndig % 100 == 0:
             dig = ['1' for _ in range(ndig)] + ['2' for _ in range(ndig)]
             for arr in permutations(dig, ndig):
                 candidate = int(''.join(arr))
                 if is_prime(candidate):
                     print(f'{ndig:4}: ', candidate)
                     break
 
 oeis36229()
 

 
 from gmpy2 import is_prime, mpz
 
 print("  n  m  prime")
 for n in range(1, 401):
     m = 0
     term = mpz(n)
     while True:
         if is_prime(term + 1):
             print(f"{n:3d}  {m}  {term + 1:5d}")
             break
         m += 1
         term *= 2
 
 
 

 
 from gmpy2 import is_prime
 def useful(n):
     k = 1
     is_useful = False
     while is_useful == False:
         p = 2**(2**n) - k
         if is_prime(p):
             is_useful = True
             break
         k += 2
     return k, p
 if __name__ == "__main__":
     print("n | k   prime")
     print("=============")
     for i in range(1,14):
         k, p = useful(i)
         print(f"{i:<4} {k}      {p}")
 
 

 
 from sympy import isprime
 
 def wagstaff(N):
     """ find first N Wagstaff primes """
     pri, wcount = 1, 0
     while wcount < N:
         pri += 2
         if isprime(pri):
             wag = (2**pri + 1) // 3
             if isprime(wag):
                 wcount += 1
                 print(f'{wcount: 3}: {pri: 5} => ', 
                       f'{wag:,}' if wcount < 11 else f'[{len(str(wag))} digit number]')
 
 
 wagstaff(24)