-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlucas-carmichael_numbers_in_range.sf
115 lines (81 loc) · 4.56 KB
/
lucas-carmichael_numbers_in_range.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#!/usr/bin/ruby
# Daniel "Trizen" Șuteu
# Date: 29 August 2022
# https://github.com/trizen
# Generate all the Lucas-Carmichael numbers with n prime factors in a given range [a,b]. (not in sorted order)
# See also:
# https://en.wikipedia.org/wiki/Almost_prime
# https://trizenx.blogspot.com/2020/08/pseudoprimes-construction-methods-and.html
#`{
# PARI/GP program (up to n) (slow):
lucas_carmichael_upto(n, k) = my(A=vecprod(primes(k+1))\2, B=n); (f(m, l, p, k, u=0, v=0) = my(list=List()); if(k==1, forprime(p=u, v, my(t=m*p); if((t+1)%l == 0 && (t+1)%(p+1) == 0, listput(list, t))), forprime(q = p, sqrtnint(B\m, k), my(t = m*q); my(L=lcm(l, q+1)); if(gcd(L, t) == 1, my(u=ceil(A/t), v=B\t); if(u <= v, my(r=nextprime(q+1)); if(k==2 && r>u, u=r); list=concat(list, f(t, L, r, k-1, u, v)))))); list); vecsort(Vec(f(1, 1, 3, k)));
# PARI/GP program (in range [A,B]) (slow):
lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, p, k, u=0, v=0) = my(list=List()); if(k==1, forprime(p=u, v, my(t=m*p); if((t+1)%l == 0 && (t+1)%(p+1) == 0, listput(list, t))), forprime(q = p, sqrtnint(B\m, k), my(t = m*q); my(L=lcm(l, q+1)); if(gcd(L, t) == 1, my(u=ceil(A/t), v=B\t); if(u <= v, my(r=nextprime(q+1)); if(k==2 && r>u, u=r); list=concat(list, f(t, L, r, k-1, u, v)))))); list); vecsort(Vec(f(1, 1, 3, k)));
# PARI/GP program (in range [A, B]) (fast):
lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); my(max_p=sqrtint(B+1)-1); (f(m, l, lo, k) = my(list=List()); my(hi=min(max_p, sqrtnint(B\m, k))); if(lo > hi, return(list)); if(k==1, lo=max(lo, ceil(A/m)); my(t=lift(-1/Mod(m,l))); while(t < lo, t += l); forstep(p=t, hi, l, if(isprime(p), my(n=m*p); if((n+1)%(p+1) == 0, listput(list, n)))), forprime(p=lo, hi, if(gcd(m, p+1) == 1, list=concat(list, f(m*p, lcm(l, p+1), p+1, k-1))))); list); vecsort(Vec(f(1, 1, 3, k)));
# PARI/GP program to generate all the Lucas-Carmichael numbers <= n (fast):
lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); my(max_p=sqrtint(B+1)-1); (f(m, l, lo, k) = my(list=List()); my(hi=min(max_p, sqrtnint(B\m, k))); if(lo > hi, return(list)); if(k==1, lo=max(lo, ceil(A/m)); my(t=lift(-1/Mod(m,l))); while(t < lo, t += l); forstep(p=t, hi, l, if(isprime(p), my(n=m*p); if((n+1)%(p+1) == 0, listput(list, n)))), forprime(p=lo, hi, if(gcd(m, p+1) == 1, list=concat(list, f(m*p, lcm(l, p+1), p+1, k-1))))); list); f(1, 1, 3, k);
upto(n) = my(list=List()); for(k=3, oo, if(vecprod(primes(k+1))\2 > n, break); list=concat(list, lucas_carmichael(1, n, k))); vecsort(Vec(list));
}
func lucas_carmichael_numbers_in_range(A, B, k, callback) {
A = max(pn_primorial(k+1)/2, A)
# Largest possisble prime factor for Lucas-Carmichael numbers <= B
var max_p = B.isqrt
func (m, L, lo, k) {
var hi = idiv(B,m).iroot(k)
if (lo > hi) {
return nil
}
if (k == 1) {
hi = max_p if (hi > max_p)
lo = max(lo, idiv_ceil(A, m))
lo > hi && return nil
var t = mulmod(m.invmod(L), -1, L)
t > hi && return nil
t += L*idiv_ceil(lo - t, L) if (t < lo)
t > hi && return nil
for p in (range(t, hi, L)) {
p.is_prime || next
with (m*p) {|n|
if (p.inc `divides` n.inc) {
callback(n)
}
}
}
return nil
}
each_prime(lo, hi, {|p|
m.is_coprime(p+1) || next
__FUNC__(m*p, lcm(L, p+1), p+1, k-1)
})
}(1, 1, 3, k)
return callback
}
# High-level implementation (unoptimized):
func lucas_carmichael_numbers_in_range_unoptimized(A, B, k, callback) {
func F(m, L, p, k) {
if (k == 1) {
each_prime(max(p, ceil(A/m)), min(B.isqrt, floor(B/m)), {|q|
if (lcm(L, q+1) `divides` (m*q + 1)) {
callback(m*q)
}
})
}
elsif (k >= 2) {
for q in (primes(p, (B/m)**(1/k))) {
if (gcd(lcm(L, q+1), m*q) == 1) {
F(m*q, lcm(L, q+1), q.next_prime, k-1)
}
}
}
}
F(1, 1, 3, k)
}
# Generate all the 5-Lucas-Carmichael numbers in the range [100, 2*10^7]
var k = 5
var from = 100
var upto = 2e7
say gather { lucas_carmichael_numbers_in_range(from, upto, k, { take(_) }) }.sort
say gather { lucas_carmichael_numbers_in_range_unoptimized(from, upto, k, { take(_) }) }.sort
__END__
[588455, 1010735, 2276351, 2756159, 4107455, 4874639, 5669279, 6539819, 8421335, 13670855, 16184663, 16868159]