Anonymous user
Carmichael 3 strong pseudoprimes: Difference between revisions
→{{header|Julia}}: A new entry for Julia
(C Solution addition) |
(→{{header|Julia}}: A new entry for Julia) |
||
Line 408:
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>
| |||