Chernick's Carmichael numbers: Difference between revisions
Content added Content deleted
m (→{{header|C++}}: minor code compression) |
(→{{header|Go}}: Added much faster version to deal with optional requirement.) |
||
Line 173: | Line 173: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Basic only=== |
|||
<lang go>package main |
<lang go>package main |
||
Line 240: | Line 241: | ||
a(8) = 53487697914261966820654105730041031613370337776541835775672321 |
a(8) = 53487697914261966820654105730041031613370337776541835775672321 |
||
a(9) = 58571442634534443082821160508299574798027946748324125518533225605795841 |
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> |
</pre> |
||