Lucas-Carmichael numbers: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added mul_inv() link) |
(→{{header|Sidef}}: Added Wren) |
||
Line 579: | Line 579: | ||
acc += c |
acc += c |
||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
{{out}} |
|||
<pre> |
|||
Least Lucas-Carmichael number with n prime factors: |
|||
3: 399 |
|||
4: 8855 |
|||
5: 588455 |
|||
6: 139501439 |
|||
7: 3512071871 |
|||
8: 199195047359 |
|||
9: 14563696180319 |
|||
10: 989565001538399 |
|||
11: 20576473996736735 |
|||
12: 4049149795181043839 |
|||
Number of Lucas-Carmichael numbers less than 10^n: |
|||
1: 0 |
|||
2: 0 |
|||
3: 2 |
|||
4: 8 |
|||
5: 26 |
|||
6: 60 |
|||
7: 135 |
|||
8: 323 |
|||
9: 791 |
|||
10: 1840 |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
{{trans|Julia}} |
|||
{{libheader|Wren-psieve}} |
|||
{{libheader|Wren-math}} |
|||
{{libheader|Wren-big}} |
|||
{{libheader|Wren-fmt}} |
|||
<syntaxhighlight lang="wren">import "./psieve" for Primes |
|||
import "./math" for Int, Nums |
|||
import "./big" for BigInt |
|||
import "./fmt" for Fmt |
|||
var lucasCarmichael = Fn.new { |A, B, k| |
|||
var LC = [] |
|||
var maxP = (B+1).sqrt.floor - 1 |
|||
var p = Primes.nthAfter(k+1, 1) |
|||
var primes = Primes.between(2, p) |
|||
var x = (Nums.prod(primes)/2).floor |
|||
A = A.max(x) |
|||
var M = 1 |
|||
var P = 1 |
|||
var F |
|||
F = Fn.new { |m, L, lo, k| |
|||
var hi = (B/m).floor.pow(1/k).round |
|||
if (lo > hi) return [] |
|||
if (k == 1) { |
|||
hi = hi.min(maxP) |
|||
lo = lo.max((A/m).ceil).round |
|||
if (lo > hi) return [] |
|||
var t |
|||
if (m <= Num.maxSafeInteger) { |
|||
t = L - Int.modInv(m, L) |
|||
} else { |
|||
var bm = BigInt.new(M) * P |
|||
t = L - bm.modInv(L).toNum |
|||
} |
|||
if (t > hi) return [] |
|||
while (t < lo) t = t + L |
|||
p = t |
|||
while (p <= hi) { |
|||
if (Int.isPrime(p)) { |
|||
var n = m * p |
|||
if (n + 1 <= Num.maxSafeInteger) { |
|||
if ((n+1) % (p+1) == 0) LC.add(n) |
|||
} else { |
|||
var bn = BigInt.new(M) * P * p |
|||
if ((bn+1) % (p+1) == 0) LC.add(bn) |
|||
} |
|||
} |
|||
p = p + L |
|||
} |
|||
return [] |
|||
} |
|||
for (p in Primes.between(lo, hi)) { |
|||
if (Int.gcd(m, p+1) == 1) { |
|||
M = m |
|||
P = p |
|||
F.call(m*p, Int.lcm(L, p+1), p+1, k-1) |
|||
} |
|||
} |
|||
} |
|||
F.call(1, 1, 3, k) |
|||
if (LC.any { |e| e is BigInt }) { |
|||
for (i in 0...LC.count) { |
|||
if (LC[i] is Num) LC[i] = BigInt.new(LC[i]) |
|||
} |
|||
} |
|||
return LC.sort() |
|||
} |
|||
var lcWithNPrimes = Fn.new { |n| |
|||
if (n < 3) return [] |
|||
var p = Primes.nthAfter(n+1, 1) |
|||
var primes = Primes.between(2, p) |
|||
var x = (Nums.prod(primes)/2).floor |
|||
var y = 2 * x |
|||
while (true) { |
|||
var LC = lucasCarmichael.call(x, y, n) |
|||
if (LC.count >= 1) return LC[0] |
|||
x = y + 1 |
|||
y = 2 * x |
|||
} |
|||
} |
|||
var lcCount = Fn.new { |A, B| |
|||
var count = 0 |
|||
for (k in 3..1e6) { |
|||
var p = Primes.nthAfter(k+1, 1) |
|||
var primes = Primes.between(2, p) |
|||
var x = (Nums.prod(primes)/2).floor |
|||
if (x > B) break |
|||
count = count + lucasCarmichael.call(A, B, k).count |
|||
} |
|||
return count |
|||
} |
|||
System.print("Least Lucas-Carmichael number with n prime factors:") |
|||
for (n in 3..12) { |
|||
Fmt.print("$2d: $i", n, lcWithNPrimes.call(n)) |
|||
} |
|||
System.print("\nNumber of Lucas-Carmichael numbers less than 10^n:") |
|||
for (n in 1..10) { |
|||
Fmt.print("$2d: $d", n, lcCount.call(1, 10.pow(n))) |
|||
} </syntaxhighlight> |
|||
{{out}} |
{{out}} |