Chernick's Carmichael numbers: Difference between revisions
→{{header|Go}}: Added much faster version to deal with optional requirement.
m (→{{header|C++}}: minor code compression) |
(→{{header|Go}}: Added much faster version to deal with optional requirement.) |
||
Line 173:
=={{header|Go}}==
===Basic only===
<lang go>package main
Line 240 ⟶ 241:
a(8) = 53487697914261966820654105730041031613370337776541835775672321
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
</pre>
===Basic plus optional===
{{libheader|GMP(Go wrapper)}}
<br>
To reach a(10) in a reasonable time, a much more efficient approach is needed.
The following version takes account of the optimizations referred to in the Talk page and previewed in the C++ entry above.
It also uses a wrapper for the C library, GMP, which despite the overhead of cgo is still much faster than Go's native big.Int library.
The resulting executable is several hundred times faster than before and, even on my modest Celeron @1.6GHZ, reaches a(9) in under 10ms and a(10) in about 22 minutes.
<lang go>package main
import (
"fmt"
big "github.com/ncw/gmp"
)
const (
min = 3
max = 10
)
var (
prod = new(big.Int)
fact = new(big.Int)
factors = [max]uint64{}
bigFactors = [max]*big.Int{}
)
func init() {
for i := 0; i < max; i++ {
bigFactors[i] = big.NewInt(0)
}
}
func isPrimePretest(k uint64) bool {
if k%3 == 0 || k%5 == 0 || k%7 == 0 || k%11 == 0 ||
k%13 == 0 || k%17 == 0 || k%19 == 0 || k%23 == 0 {
return k <= 23
}
return true
}
func ccFactors(n, m uint64) bool {
if !isPrimePretest(6*m + 1) {
return false
}
if !isPrimePretest(12*m + 1) {
return false
}
factors[0] = 6*m + 1
factors[1] = 12*m + 1
t := 9 * m
for i := uint64(1); i <= n-2; i++ {
tt := (t << i) + 1
if !isPrimePretest(tt) {
return false
}
factors[i+1] = tt
}
for i := 0; i < int(n); i++ {
fact.SetUint64(factors[i])
if !fact.ProbablyPrime(0) {
return false
}
bigFactors[i].Set(fact)
}
return true
}
func prodFactors(n uint64) *big.Int {
prod.Set(bigFactors[0])
for i := 1; i < int(n); i++ {
prod.Mul(prod, bigFactors[i])
}
return prod
}
func ccNumbers(start, end uint64) {
for n := start; n <= end; n++ {
mult := uint64(1)
if n > 4 {
mult = 1 << (n - 4)
}
if n > 5 {
mult *= 5
}
m := mult
for {
if ccFactors(n, m) {
num := prodFactors(n)
fmt.Printf("a(%d) = %d\n", n, num)
fmt.Printf("m(%d) = %d\n", n, m)
fmt.Println("Factors:", factors[:n], "\n")
break
}
m += mult
}
}
}
func main() {
ccNumbers(min, max)
}</lang>
{{out}}
<pre>
a(3) = 1729
m(3) = 1
Factors: [7 13 19]
a(4) = 63973
m(4) = 1
Factors: [7 13 19 37]
a(5) = 26641259752490421121
m(5) = 380
Factors: [2281 4561 6841 13681 27361]
a(6) = 1457836374916028334162241
m(6) = 380
Factors: [2281 4561 6841 13681 27361 54721]
a(7) = 24541683183872873851606952966798288052977151461406721
m(7) = 780320
Factors: [4681921 9363841 14045761 28091521 56183041 112366081 224732161]
a(8) = 53487697914261966820654105730041031613370337776541835775672321
m(8) = 950560
Factors: [5703361 11406721 17110081 34220161 68440321 136880641 273761281 547522561]
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841
m(9) = 950560
Factors: [5703361 11406721 17110081 34220161 68440321 136880641 273761281 547522561 1095045121]
a(10) = 24616075028246330441656912428380582403261346369700917629170235674289719437963233744091978433592331048416482649086961226304033068172880278517841921
m(10) = 3208386195840
Factors: [19250317175041 38500634350081 57750951525121 115501903050241 231003806100481 462007612200961 924015224401921 1848030448803841 3696060897607681 7392121795215361]
</pre>
| |||