Carmichael 3 strong pseudoprimes: Difference between revisions

Content added Content deleted
Line 1,303: Line 1,303:


'''Function'''
'''Function'''
<lang Julia>
<lang julia>using Primes

function carmichael{T<:Integer}(pmax::T)
function carmichael(pmax::Integer)
0 < pmax || throw(DomainError())
if pmax ≤ 0 throw(DomainError("pmax must be strictly positive")) end
car = T[]
car = Vector{typeof(pmax)}(0)
for p in primes(pmax)
for p in primes(pmax)
for h₃ in 2:(p-1)
for h₃ in 2:(p-1)
m = (p - 1)*(h₃ + p)
m = (p - 1) * (h₃ + p)
pmh = mod(-p^2, h₃)
pmh = mod(-p ^ 2, h₃)
for Δ in 1:(h₃+p-1)
for Δ in 1:(h₃+p-1)
m%Δ==0 && Δ%h₃==pmh || continue
if m % Δ != 0 || Δ % h₃ != pmh continue end
q = div(m, Δ) + 1
q = m ÷ Δ + 1
isprime(q) || continue
if !isprime(q) continue end
r = div((p*q - 1), h₃) + 1
r = (p * q - 1) ÷ h₃ + 1
isprime(r) && mod(q*r, (p-1))==1 || continue
if !isprime(r) || mod(q * r, p - 1) == 1 continue end
append!(car, [p, q, r])
append!(car, [p, q, r])
end
end
end
end
end
end
reshape(car, 3, div(length(car), 3))
return reshape(car, 3, length(car) ÷ 3)
end
end</lang>
</lang>


'''Main'''
'''Main'''
<lang Julia>
<lang julia>hi = 61
hi = 61
car = carmichael(hi)
car = carmichael(hi)


curp = 0
curp = tcnt = 0
⚫
print("Carmichael 3 (p×q×r) pseudoprimes, up to p = $hi:")
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]))
for j in sortperm(1:size(car)[2], by=x->(car[1,x], car[2,x], car[3,x]))
p, q, r = car[:,j]
p, q, r = car[:, j]
c = prod(car[:,j])
c = prod(car[:, j])
if p != curp
if p != curp
curp = p
curp = p
print(@sprintf("\n\np = %d\n ", p))
@printf("\n\np = %d\n ", p)
tcnt = 0
tcnt = 0
end
end
Line 1,347: Line 1,345:
tcnt += 1
tcnt += 1
end
end
print(@sprintf("p\u00d7%d\u00d7%d = %d ", q, r, c))
@printf("p× %d × %d = %d ", q, r, c)
end
end
println("\n\n", size(car)[2], " results in total.")
println("\n\n", size(car)[2], " results in total.")</lang>
</lang>


{{out}}
{{out}}
<pre>Carmichael 3 (p×q×r) pseudoprimes, up to p = 61:
<pre>
⚫
Carmichael 3 (p×q×r) Pseudoprimes, up to p = 61:


p = 3
p×11×17 = 561


p = 5
p = 11
p×13×17 = 1105 p×17×29 = 2465 p×29×73 = 10585
p× 29 × 107 = 34133 p× 37 × 59 = 24013

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 = 17
p×41×233 = 162401 p×353×1201 = 7207201
p× 23 × 79 = 30889 p× 53 × 101 = 91001


p = 19
p = 19
p× 59 × 113 = 126673 p× 139 × 661 = 1745701 p× 193 × 283 = 1037761
p×43×409 = 334153 p×199×271 = 1024651


p = 23
p = 23
p× 43 × 53 = 52417 p× 59 × 227 = 308039 p× 71 × 137 = 223721 p× 83 × 107 = 204263
p×199×353 = 1615681


p = 29
p = 29
p× 41 × 109 = 129601 p× 89 × 173 = 446513 p× 97 × 149 = 419137 p× 149 × 541 = 2337661
p×113×1093 = 3581761 p×197×953 = 5444489


p = 31
p = 31
p× 67 × 1039 = 2158003 p× 73 × 79 = 178777 p× 79 × 307 = 751843 p× 223 × 1153 = 7970689
p×61×211 = 399001 p×61×271 = 512461 p×61×631 = 1193221 p×151×1171 = 5481451
p× 313 × 463 = 4492489
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 = 41
p× 89 × 1217 = 4440833 p× 97 × 569 = 2262913
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 = 43
p× 67 × 241 = 694321 p× 107 × 461 = 2121061 p× 131 × 257 = 1447681 p× 139 × 1993 = 11912161
p×127×211 = 1152271 p×127×1093 = 5968873 p×127×2731 = 14913991 p×211×337 = 3057601
p× 157 × 751 = 5070001 p× 199 × 373 = 3191761
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 = 47
p× 53 × 499 = 1243009 p× 89 × 103 = 430849 p× 101 × 1583 = 7514501 p× 107 × 839 = 4219331
p×1151×1933 = 104569501 p×3359×6073 = 958762729 p×3727×5153 = 902645857
p× 157 × 239 = 1763581


p = 53
p = 53
p× 113 × 1997 = 11960033 p× 197 × 233 = 2432753 p× 281 × 877 = 13061161
p×79×599 = 2508013 p×157×521 = 4335241 p×157×2081 = 17316001


p = 59
p = 59
p× 131 × 1289 = 9962681 p× 139 × 821 = 6733021 p× 149 × 587 = 5160317 p× 173 × 379 = 3868453
p×1451×2089 = 178837201
p× 179 × 353 = 3728033


p = 61
p = 61
p× 1009 × 2677 = 164766673
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.
42 results in total.</pre>
</pre>


=={{header|Kotlin}}==
=={{header|Kotlin}}==
Retrieved from "https://rosettacode.org/wiki/Carmichael_3_strong_pseudoprimes"