/
prog.sf
68 lines (50 loc) · 3.29 KB
/
prog.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
#!/usr/bin/ruby
# Least Lucas-Carmichael number with n prime factors.
# https://oeis.org/A216928
# Known terms:
# 399, 8855, 588455, 139501439, 3512071871, 199195047359, 14563696180319, 989565001538399, 20576473996736735, 4049149795181043839, 409810997884396741919, 46852073639840281125599
#`(
# PARI/GP program (version 1) (quite 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)));
a(n) = if(n < 3, return()); my(x=vecprod(primes(n+1))\2,y=2*x); while(1, my(v=lucas_carmichael(x,y,n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ ~~~~
# PARI/GP program (version 2) (faster):
lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, lo, k) = my(list=List()); my(hi=sqrtnint(B\m, k)); if(lo > hi, return(list)); if(k==1, forprime(p=max(lo, ceil(A/m)), hi, my(t=m*p); if((t+1)%l == 0 && (t+1)%(p+1) == 0, listput(list, t))), 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)));
a(n) = if(n < 3, return()); my(x=vecprod(primes(n+1))\2,y=2*x); while(1, my(v=lucas_carmichael(x,y,n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ ~~~~
# PARI/GP program (version 3) (fastest):
lucas_carmichael(A, B, k) = A=max(A, vecprod(primes(k+1))\2); (f(m, l, lo, k) = my(list=List()); my(hi=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)));
a(n) = if(n < 3, return()); my(x=vecprod(primes(n+1))\2,y=2*x); while(1, my(v=lucas_carmichael(x,y,n)); if(#v >= 1, return(v[1])); x=y+1; y=2*x); \\ ~~~~
)
# New terms found:
# a(15) = 6414735508880546179805759
# a(16) = 466807799396932243821123839
# a(17) = 41222773167337486494297521279
# a(18) = 5670586073047883755094926472159
# a(19) = 247499293142007885087237709213919
# a(20) = 202003815733964076599064812732611679
# a(21) = 17988631465107219093106511654427868799
# a(22) = 6260401580525839547593293275046894535199
# a(23) = 521027978053852870937320124850878216361599
# a(24) = 257685984879302905034127894788339525937551999
# a(25) = 39355410745046203120019553518734961968898942399
# a(26) = 1422206796849165887380738983840035626943341276799
# a(27) = 438252156495754541448512765942687553061536148703999
# a(28) = 333791863958043189671786617765781459382301668208175999
# New terms (24 February 2023):
# a(29) = 46521156947634673750957825164223546441200487134525859199
func a(n) {
return nil if (n < 3)
var x = pn_primorial(n+1)/2
var y = 2*x
loop {
#say "Sieving range: #{[x,y]}"
var arr = n.lucas_carmichael(x,y)
if (arr.len >= 1) {
return arr[0]
}
x = y+1
y = 2*x
}
}
for n in (3..100) {
say "a(#{n}) = #{a(n)}"
}