-
Notifications
You must be signed in to change notification settings - Fork 0
/
new_idea_4.sf
120 lines (97 loc) · 4.62 KB
/
new_idea_4.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
116
117
118
119
120
#!/usr/bin/ruby
# Erdos construction method for Carmichael numbers:
# 1. Choose an integer L with many prime factors.
# 2. Let P be the set of primes d+1, where d|L and d+1 does not divide L.
# 3. Find a subset S of P such that prod(S) == 1 (mod L). Then prod(S) is a Carmichael number.
#var L = 720
#for L in (1e3..1e4) {
#for L in (14322, 1919190, 56786730, 140100870, 209191710, 2328255930, 2381714790, 7225713885390, 9538864545210, 21626561658972270, 446617991732222310, 115471236091149548610, 5145485882746933233510, 14493038256293268734790) {
#var good_lambda = 147090944*47*19
#var good_lambda = 1517684360192
var good_lambda = 137971305472**2
#var good_lambda = (1029636608*19*47)**2
for k in (good_lambda.divisors.flip) {
#for k in (137971305472) {
#for L in ([2, 2, 2, 2, 2, 2, 2, 2, 7, 7, 11, 13, 41].prod) {
#var L = (18386368 * k)
#var L = (4596592 * k)
var L = (good_lambda / k)
#var good_primes = [3, 5, 17, 23, 29, 53]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 353, 449, 617]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 257, 353, 617]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197]
#var good_primes = [3, 5, 17, 23, 29, 53, 89, 113, 197, 257, 353, 419, 449, 617, 2003]
#var good_primes = [3, 5, 17, 23, 29, 53, 89, 113, 197, 257, 353]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 353, 617, 1409, 2003, 2549, 10193, 16073, 202049, 275969, 18386369]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 353, 617, 1409, 2003, 2549, 10193, 16073, 202049, 18386369]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 353, 1373, 2003, 2297, 2549, 4019]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 353, 617]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 257, 353, 617, 1409, 2003, 2549]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 353, 617, 2003, 2549]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 257, 353, 449, 617, 1409, 2003, 2297, 2549, 3137, 3329, 4019]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 257, 353, 449, 617, 1409, 2003, 2297, 2549, 3137, 3329, 4019, 7547, 9857]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 353, 617, 2297, 3137, 4019, 7547, 8009, 9857]
var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 353, 617, 2003, 2549]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 257, 353, 617, 1409, 2003, 2549, 3137, 9857, 10193, 16073, 68993, 202049, 1500929, 18386369]
#var good_primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 353, 617, 2003, 2549, 3137, 9857, 10193, 16073, 68993, 202049, 1500929, 18386369]
var P = L.divisors.map { .inc }.grep { .is_odd && .is_prime }.grep {|p| L%p != 0 }
var prefix = good_primes.prod
P.prod % prefix == 0 || next
P = P.grep { is_coprime(_, prefix) }
var Q = P.grep { _ > 113 }
var t = Q.prod
say "Testing: #{L} with k = #{k}"
say "Has #{P.len} good divisors"
for k in (1..Q.len) {
good_primes.len + (Q.len-k) >= 25 || next
good_primes.len + (Q.len-k) > 35 && next
say "[1] Combination: #{k} with #{good_primes.len + (Q.len - k)} prime factors = #{binomial(Q.len, k)}"
var count = 0
Q.combinations(k, {|*S|
if (t/S.prod * prefix % L == 1) {
say (t/S.prod * prefix)
}
break if (++count >= 1e4);
})
var count = 0
Q.flip.combinations(k, {|*S|
if (t/S.prod * prefix % L == 1) {
say (t/S.prod * prefix)
}
break if (++count >= 1e4);
})
var count = 0
Q.shuffle.combinations(k, {|*S|
if (t/S.prod * prefix % L == 1) {
say (t/S.prod * prefix)
}
break if (++count >= 1e4);
})
}
for k in (P.len `downto` 1) {
good_primes.len + k >= 25 || next
good_primes.len + k > 35 && next
say "[2] Combination: #{k} with #{good_primes.len + k} prime factors = #{binomial(P.len, k)}"
var count = 0
P.combinations(k, {|*S|
if (S.prod * prefix % L == 1) {
say (S.prod * prefix)
}
break if (++count >= 1e4);
})
var count = 0
P.flip.combinations(k, {|*S|
if (S.prod * prefix % L == 1) {
say (S.prod * prefix)
}
break if (++count >= 1e4);
})
var count = 0
P.shuffle.combinations(k, {|*S|
if (S.prod * prefix % L == 1) {
say (S.prod * prefix)
}
break if (++count >= 1e4);
})
}
}