Carmichael 3 strong pseudoprimes: Difference between revisions
Content added Content deleted
(C Solution addition) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 408: | Line 408: | ||
61 * 3361 * 4021 = 824389441 |
61 * 3361 * 4021 = 824389441 |
||
-> |
-> |
||
</pre> |
|||
=={{header|Julia}}== |
|||
This solution is a straightforward implementation of the algorithm of the Jameson paper cited in the task description. Just for fun, I use Julia's capacity to accommodate Unicode identifiers to match some of the paper's symbols to the variables used in the <tt>carmichael</tt> function. |
|||
'''Function''' |
|||
<lang Julia> |
|||
function carmichael{T<:Integer}(pmax::T) |
|||
0 < pmax || throw(DomainError()) |
|||
car = T[] |
|||
for p in primes(pmax) |
|||
for h₃ in 2:(p-1) |
|||
m = (p - 1)*(h₃ + p) |
|||
pmh = mod(-p^2, h₃) |
|||
for Δ in 1:(h₃+p-1) |
|||
m%Δ==0 && Δ%h₃==pmh || continue |
|||
q = div(m, Δ) + 1 |
|||
isprime(q) || continue |
|||
r = div((p*q - 1), h₃) + 1 |
|||
isprime(r) && mod(q*r, (p-1))==1 || continue |
|||
append!(car, [p, q, r]) |
|||
end |
|||
end |
|||
end |
|||
reshape(car, 3, div(length(car), 3)) |
|||
end |
|||
</lang> |
|||
'''Main''' |
|||
<lang Julia> |
|||
hi = 61 |
|||
car = carmichael(hi) |
|||
curp = 0 |
|||
tcnt = 0 |
|||
print("Carmichael 3 (p\u00d7q\u00d7r) Pseudoprimes, up to p = ", hi, ":") |
|||
for j in sortperm(1:size(car)[2], by=x->(car[1,x], car[2,x], car[3,x])) |
|||
p, q, r = car[:,j] |
|||
c = prod(car[:,j]) |
|||
if p != curp |
|||
curp = p |
|||
print(@sprintf("\n\np = %d\n ", p)) |
|||
tcnt = 0 |
|||
end |
|||
if tcnt == 4 |
|||
print("\n ") |
|||
tcnt = 1 |
|||
else |
|||
tcnt += 1 |
|||
end |
|||
print(@sprintf("p\u00d7%d\u00d7%d = %d ", q, r, c)) |
|||
end |
|||
println("\n\n", size(car)[2], " results in total.") |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Carmichael 3 (p×q×r) Pseudoprimes, up to p = 61: |
|||
p = 3 |
|||
p×11×17 = 561 |
|||
p = 5 |
|||
p×13×17 = 1105 p×17×29 = 2465 p×29×73 = 10585 |
|||
p = 7 |
|||
p×13×19 = 1729 p×13×31 = 2821 p×19×67 = 8911 p×23×41 = 6601 |
|||
p×31×73 = 15841 p×73×103 = 52633 |
|||
p = 13 |
|||
p×37×61 = 29341 p×37×97 = 46657 p×37×241 = 115921 p×61×397 = 314821 |
|||
p×97×421 = 530881 |
|||
p = 17 |
|||
p×41×233 = 162401 p×353×1201 = 7207201 |
|||
p = 19 |
|||
p×43×409 = 334153 p×199×271 = 1024651 |
|||
p = 23 |
|||
p×199×353 = 1615681 |
|||
p = 29 |
|||
p×113×1093 = 3581761 p×197×953 = 5444489 |
|||
p = 31 |
|||
p×61×211 = 399001 p×61×271 = 512461 p×61×631 = 1193221 p×151×1171 = 5481451 |
|||
p×181×331 = 1857241 p×271×601 = 5049001 p×991×15361 = 471905281 |
|||
p = 37 |
|||
p×73×109 = 294409 p×73×181 = 488881 p×73×541 = 1461241 p×109×2017 = 8134561 |
|||
p×613×1621 = 36765901 |
|||
p = 41 |
|||
p×61×101 = 252601 p×73×137 = 410041 p×101×461 = 1909001 p×241×521 = 5148001 |
|||
p×241×761 = 7519441 p×881×12041 = 434932961 p×1721×35281 = 2489462641 |
|||
p = 43 |
|||
p×127×211 = 1152271 p×127×1093 = 5968873 p×127×2731 = 14913991 p×211×337 = 3057601 |
|||
p×211×757 = 6868261 p×271×5827 = 67902031 p×433×643 = 11972017 p×547×673 = 15829633 |
|||
p×631×1597 = 43331401 p×631×13567 = 368113411 p×3361×3907 = 564651361 |
|||
p = 47 |
|||
p×1151×1933 = 104569501 p×3359×6073 = 958762729 p×3727×5153 = 902645857 |
|||
p = 53 |
|||
p×79×599 = 2508013 p×157×521 = 4335241 p×157×2081 = 17316001 |
|||
p = 59 |
|||
p×1451×2089 = 178837201 |
|||
p = 61 |
|||
p×181×1381 = 15247621 p×181×5521 = 60957361 p×241×421 = 6189121 p×271×571 = 9439201 |
|||
p×277×2113 = 35703361 p×421×12841 = 329769721 p×541×3001 = 99036001 p×661×2521 = 101649241 |
|||
p×1301×19841 = 1574601601 p×3361×4021 = 824389441 |
|||
69 results in total. |
|||
</pre> |
</pre> |
||