-
Notifications
You must be signed in to change notification settings - Fork 0
/
prog.sf
102 lines (71 loc) · 2.41 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
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
#!/usr/bin/ruby
# Least prime p such that p^n + 1 is the product of n distinct primes.
# https://oeis.org/A280005
# Similar sequence: A242786
# Known terms:
# 2, 3, 13, 43, 73, 47, 457, 1697, 109, 8161, 10429, 13183, 30089, 66569, 5281
# Lower-bounds:
# a(16) > 1746439
# a(17) > 43889
# Upper-bounds:
# a(16) <= 206874667
include("../../../factordb/auto.sf")
func check_partial_factors(f,n) {
f.uniq.len == f.len || return false
f.sum {|p| p.is_prime ? 1 : 2 } > n && return false
if (f.all_prime) {
if (f.len == n) {
return true
}
return false
}
return true
}
func a(n, from=2) {
for (var p = from; true ; p.next_prime!) {
var v = (p**n + 1)
v.is_prob_squarefree(1e6) || next
say "[#{n}] Checking: #{p}"
var tf = v.trial_factor(1e6)
check_partial_factors(tf, n) || next
tf.len.dec + tf.last.ilog(1e6) + 1 >= n || next
tf = v.trial_factor(1e7)
check_partial_factors(tf, n) || next
tf.len.dec + tf.last.ilog(1e7) + 1 >= n || next
if (tf.last > 1e60) {
tf = v.trial_factor(1e8)
check_partial_factors(tf, n) || next
tf.len.dec + tf.last.ilog(1e8) + 1 >= n || next
}
say "Many factors (at least #{tf.len-1 + (tf.last.is_prime ? 1 : 2)} with C#{tf.last.len}): #{v}"
var ff = v.special_factor
check_partial_factors(ff, n) || next
var f = factordb(v)
check_partial_factors(f, n) || next
var f3 = gcd_factors(v, tf + ff + f)
check_partial_factors(f3, n) || next
if ((f3.last > 1e65) && f3.last.is_composite) {
tf = v.trial_factor(1e9)
check_partial_factors(tf, n) || next
tf.len.dec + tf.last.ilog(1e9) + 1 >= n || next
say "Strong candidate..."
f3 = gcd_factors(v, tf + ff + f)
check_partial_factors(f3, n) || next
var pf = f3.grep{.is_prime}
var c = (v / pf.prod)
pf.len + c.ilog(1e9) + 1 >= n || next
say "Factoring C#{c.len}: #{c}"
}
f3 = f3.map{ .is_prime ? _ : factordb(_) }.flat
check_partial_factors(f3, n) || next
f3 = f3.map{ .factor }.flat
check_partial_factors(f3, n) || next
if (f3.len == n) {
return p
}
}
}
#var from = 2
var n = 16
var from = 1746439
say "a(#{n}) = #{a(n, from)}"