-
Notifications
You must be signed in to change notification settings - Fork 0
/
new_idea.sf
165 lines (103 loc) · 14.9 KB
/
new_idea.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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#!/usr/bin/ruby
# Try to generate an abundant Carmichael number.
func a(n) {
n.divisors.map{.inc}.grep{.is_odd && .is_prime}
}
var arr = [
#6, 12, 24, 30, 60, 120, 180, 210, 420, 840, 1260, 2310, 4620, 9240, 13860, 27720, 30030, 60060, 120120, 180180, 360360, 510510, 1021020, 2042040, 3063060, 6126120, 9699690, 19399380, 38798760, 58198140, 116396280, 223092870, 446185740, 892371480, 1338557220, 2677114440, 5354228880, 6469693230, 12939386460, 25878772920, 38818159380, 77636318760, 155272637520, 194090796900, 200560490130, 401120980260, 802241960520, 1203362940780, 2406725881560, 4813451763120, 6016814703900, 7420738134810, 14841476269620, 29682952539240, 44524428808860, 89048857617720, 178097715235440, 222622144044300, 304250263527210, 608500527054420, 1217001054108840, 1825501581163260, 3651003162326520, 7302006324653040, 9127507905816300, 13082761331670030, 26165522663340060, 52331045326680120, 78496567990020180, 156993135980040360, 313986271960080720, 392482839950100900, 614889782588491410, 1229779565176982820, 2459559130353965640, 3689338695530948460, 7378677391061896920, 14757354782123793840, 18446693477654742300, 32589158477190044730, 65178316954380089460, 130356633908760178920, 195534950863140268380, 391069901726280536760, 782139803452561073520, 977674754315701341900, 1922760350154212639070, 3845520700308425278140, 7691041400616850556280, 11536562100925275834420, 23073124201850551668840, 46146248403701103337680, 57682810504626379172100, 115365621009252758344200, 117288381359406970983270, 234576762718813941966540, 469153525437627883933080, 703730288156441825899620, 1407460576312883651799240, 2814921152625767303598480
# 2, 12, 24, 48, 60, 168, 180, 240, 360, 720, 840, 1260, 2880, 3360, 5040, 7560, 10080, 21840, 33600, 35280, 37800, 55440, 100800, 110880, 166320, 262080, 327600, 415800, 665280, 831600, 1081080, 1441440, 2827440, 3326400, 4989600, 6320160, 6486480, 10533600, 11309760, 12972960, 20540520, 24504480, 32432400, 53721360, 61261200, 82162080, 136936800, 214885440, 232792560, 273873600, 397837440, 410810400
#4, 6, 8, 12, 18, 20, 30, 42, 72, 180, 182, 240, 420, 702, 840, 882, 1260, 1872, 2162, 2522, 4160, 5040, 7562, 10080, 13442, 13860, 20162, 22680, 30242, 35282, 45362, 55440, 65520, 110880, 138600, 151202, 166320, 226800, 262080, 327600, 332642, 415802, 665280, 831600, 942480, 1081080, 1441440, 2827440, 3326400, 4324322, 6320160, 10533600, 11309760, 12972960, 14414402, 21067202, 23284800, 24504480, 32432400, 41081042, 43243202, 61261200, 68468400, 82162080, 108108000, 110270162, 136936800, 164324162, 183783602, 248648402, 273873600, 302702402, 367567202, 410810400, 627026400, 698377680, 735134400, 1074427200, 1102701600, 1163962802, 1396755360, 1470268802, 2205403200, 2818015200, 3381618242, 3859455600, 4227022800, 4655851202, 7558911362, 8031343320, 8147739600, 8454045602, 9777287522, 12681068400, 12681068402, 13967553602, 20951330400, 29331862562, 32125373280
# 4, 6, 10, 16, 18, 28, 40, 70, 178, 180, 238, 418, 700, 838, 880, 1258, 1870, 2160, 2520, 4158, 5038, 7560, 10078, 13440, 13858, 20160, 22678, 30240, 35280, 45360, 55438, 65518, 110878, 138598, 151200, 166318, 226798, 262078, 327598, 332640, 415800, 665278, 831598, 942478, 1081078, 1441438, 2827438, 3326398, 4324320, 6320158, 10533598, 11309758, 12972958, 14414400, 21067200, 23284798, 24504478, 32432398, 41081040, 43243200, 61261198, 68468398, 82162078, 108107998, 110270160, 136936798, 164324160, 183783600, 248648400, 273873598, 302702400, 367567200, 410810398, 627026398, 698377678, 735134398, 1074427198, 1102701598, 1163962800, 1396755358, 1470268800, 2205403198, 2818015198, 3381618240, 3859455598, 4227022798, 4655851200, 7558911360, 8031343318, 8147739598, 8454045600, 9777287520, 12681068398, 12681068400, 13967553600, 20951330398, 29331862560, 32125373278
#24, 80, 125, 224, 2400, 3024, 4224, 4374, 6655, 9800, 10647, 123200, 194480, 336140, 601425, 633555, 709631, 5142500, 5909760, 11859210, 1611308699
#25, 81, 126, 225, 2401, 3025, 4225, 4375, 6656, 9801, 10648, 123201, 194481, 336141, 601426, 633556, 709632, 5142501, 5909761, 11859211, 1611308700
# 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 332640, 498960, 554400, 665280, 720720, 831600, 1081080, 1441440
# 60, 360, 1260, 2520, 27720, 138600, 360360, 831600, 10810800, 75675600, 183783600, 1286485200, 24443218800, 38594556000, 424540116000, 733296564000, 8066262204000, 185524030692000, 1693915062840000, 5380196890068000, 38960046445320000, 166786103592108000
#24, 96, 120, 480, 840, 3360, 7560, 30240, 83160, 272160, 332640, 1081080, 2993760, 4324320, 17297280, 38918880, 69189120, 73513440, 294053760, 661620960, 1176215040, 1396755360, 5587021440, 12570798240, 22348085760, 32125373280, 128501493120
#36, 105, 120, 210, 630, 5460, 25200, 73920, 97020, 157080, 1185030, 2031120, 2162160, 17907120, 76576500, 236215980, 7534947420, 12249176940, 78091322400, 203522319000, 666365279580, 2427046221600, 3638780505360, 12112252031880
#120, 128, 144, 180, 192, 210, 216, 240, 256, 288, 360, 384, 420, 432, 480, 512, 576, 720, 768, 840, 864, 900, 960, 1024, 1080, 1152, 1260, 1296, 1440, 1536, 1680, 1728, 1800, 1920, 2048, 2160, 2304, 2310, 2520, 2592, 2880, 3072, 3360, 3456, 3600, 3840, 4096, 4320, 4608, 4620, 5040, 5184, 5400, 5760, 6144, 6300, 6480, 6720, 6912, 7200, 7560, 7680, 7776, 8192, 8640, 9216, 9240, 10080, 10368, 10800, 11520, 12288, 12600, 12960, 13440, 13824, 13860, 14400, 15120, 15360, 15552, 16384, 17280, 18432, 18480, 20160, 20736, 21600, 23040, 24576, 25200, 25920, 26880, 27000, 27648
#792, 720, 864, 1440, 5040, 50400, 11232, 30240, 30240, 30240, 4320, 5040, 10080, 10080, 7560, 55440, 10080,
#13440,
#30240
#15120,,
# 9648, 9696, 9744, 9792, 9840, 9888, 9936, 9984, 10032, 10080, 10128, 10176, 10224, 10272, 10320, 10368, 10416, 10464, 10512, 10560, 10608, 10656, 10704, 10752, 10800, 10848, 10896, 10944, 10992, 11040, 11088, 11136, 11184, 11232, 11280, 11328, 11376, 11424, 11472, 11520, 11568, 11616, 11664, 11712, 11760, 11808, 11856, 11904, 11952, 12000, 12048, 12096, 12144, 12192, 12240, 12288, 12336, 12384, 12432, 12480, 12528, 12576, 12624, 12672, 12720, 12768, 12816, 12864, 12912, 12960, 13008, 13056, 13104, 13152, 13200, 13248, 13296, 13344, 13392, 13440, 13488, 13536, 13584, 13632, 13680, 13728, 13776, 13824, 13872, 13920, 13968, 14016, 14064, 14112, 14160, 14208, 14256, 14304, 14352, 14400
#16016, 32032, 48048, 64064, 80080, 96096, 112112, 128128, 144144, 160160, 176176, 192192, 208208, 224224, 240240, 256256, 272272, 288288, 304304, 320320, 336336, 352352, 368368, 384384, 400400, 416416, 432432, 448448, 464464, 480480, 496496, 512512, 528528, 544544, 560560, 576576, 592592, 608608, 624624, 640640, 656656, 672672, 688688, 704704, 720720, 736736, 752752, 768768, 784784, 800800, 816816, 832832, 848848, 864864, 880880, 896896, 912912, 928928, 944944, 960960, 976976, 992992, 1009008, 1025024, 1041040, 1057056, 1073072, 1089088, 1105104, 1121120, 1137136, 1153152, 1169168, 1185184, 1201200, 1217216, 1233232, 1249248, 1265264, 1281280, 1297296, 1313312, 1329328, 1345344, 1361360, 1377376, 1393392, 1409408, 1425424, 1441440, 1457456, 1473472, 1489488, 1505504, 1521520, 1537536, 1553552, 1569568, 1585584, 1601600
#45584, 91168, 136752, 182336, 227920, 273504, 319088, 364672, 410256, 455840, 501424, 547008, 592592, 638176, 683760, 729344, 774928, 820512, 866096, 911680, 957264, 1002848, 1048432, 1094016, 1139600, 1185184, 1230768, 1276352, 1321936, 1367520, 1413104, 1458688, 1504272, 1549856, 1595440, 1641024, 1686608, 1732192, 1777776, 1823360, 1868944, 1914528, 1960112, 2005696, 2051280, 2096864, 2142448, 2188032, 2233616, 2279200, 2324784, 2370368, 2415952, 2461536, 2507120, 2552704, 2598288, 2643872, 2689456, 2735040, 2780624, 2826208, 2871792, 2917376, 2962960, 3008544, 3054128, 3099712, 3145296, 3190880, 3236464, 3282048, 3327632, 3373216, 3418800, 3464384, 3509968, 3555552, 3601136, 3646720, 3692304, 3737888, 3783472, 3829056, 3874640, 3920224, 3965808, 4011392, 4056976, 4102560, 4148144, 4193728, 4239312, 4284896, 4330480, 4376064, 4421648, 4467232, 4512816, 4558400
#2024, 1188, 7201568, 15542912, 285824, 5789168,
#4352299952
#95064844951195944056039808
#112112, 224224, 336336, 448448, 560560, 672672, 784784, 896896, 1009008, 1121120, 1233232, 1345344, 1457456, 1569568, 1681680, 1793792, 1905904, 2018016, 2130128, 2242240, 2354352, 2466464, 2578576, 2690688, 2802800, 2914912, 3027024, 3139136, 3251248, 3363360, 3475472, 3587584, 3699696, 3811808, 3923920, 4036032, 4148144, 4260256, 4372368, 4484480, 4596592, 4708704, 4820816, 4932928, 5045040, 5157152, 5269264, 5381376, 5493488, 5605600, 5717712, 5829824, 5941936, 6054048, 6166160, 6278272, 6390384, 6502496, 6614608, 6726720, 6838832, 6950944, 7063056, 7175168, 7287280, 7399392, 7511504, 7623616, 7735728, 7847840, 7959952, 8072064, 8184176, 8296288, 8408400, 8520512, 8632624, 8744736, 8856848, 8968960, 9081072, 9193184, 9305296, 9417408, 9529520, 9641632, 9753744, 9865856, 9977968, 10090080, 10202192, 10314304, 10426416, 10538528, 10650640, 10762752, 10874864, 10986976, 11099088, 11211200
#5789168, 11578336, 17367504, 23156672, 28945840, 34735008, 40524176, 46313344, 52102512, 57891680, 63680848, 69470016, 75259184, 81048352, 86837520, 92626688, 98415856, 104205024, 109994192, 115783360, 121572528, 127361696, 133150864, 138940032, 144729200, 150518368, 156307536, 162096704, 167885872, 173675040, 179464208, 185253376, 191042544, 196831712, 202620880, 208410048, 214199216, 219988384, 225777552, 231566720, 237355888, 243145056, 248934224, 254723392, 260512560, 266301728, 272090896, 277880064, 283669232, 289458400, 295247568, 301036736, 306825904, 312615072, 318404240, 324193408, 329982576, 335771744, 341560912, 347350080, 353139248, 358928416, 364717584, 370506752, 376295920, 382085088, 387874256, 393663424, 399452592, 405241760, 411030928, 416820096, 422609264, 428398432, 434187600, 439976768, 445765936, 451555104, 457344272, 463133440, 468922608, 474711776, 480500944, 486290112, 492079280, 497868448, 503657616, 509446784, 515235952, 521025120, 526814288, 532603456, 538392624, 544181792, 549970960, 555760128, 561549296, 567338464, 573127632, 578916800
#1188, 7201568, 15542912, 285824, 5789168, 4352299952
#31085824, 46628736, 62171648, 77714560, 93257472, 108800384, 124343296, 139886208, 155429120, 170972032, 186514944, 202057856, 217600768, 233143680, 248686592, 264229504, 279772416, 295315328, 310858240, 326401152, 341944064, 357486976, 373029888, 388572800, 404115712, 419658624, 435201536, 450744448, 466287360, 481830272, 497373184, 512916096, 528459008, 544001920, 559544832, 575087744, 590630656, 606173568, 621716480, 637259392, 652802304, 668345216, 683888128, 699431040, 714973952, 730516864, 746059776, 761602688, 777145600, 792688512, 808231424, 823774336, 839317248, 854860160, 870403072, 885945984, 901488896, 917031808, 932574720, 948117632, 963660544, 979203456, 994746368, 1010289280, 1025832192, 1041375104, 1056918016, 1072460928, 1088003840, 1103546752, 1119089664, 1134632576, 1150175488, 1165718400, 1181261312, 1196804224, 1212347136, 1227890048, 1243432960, 1258975872, 1274518784, 1290061696, 1305604608, 1321147520, 1336690432, 1352233344, 1367776256, 1383319168, 1398862080, 1414404992, 1429947904, 1445490816, 1461033728, 1476576640, 1492119552, 1507662464, 1523205376, 1538748288, 1554291200
#30240
#8788661445, 17577322890, 52731968670, 210927874680, 1054639373400, 6327836240400
#45584, 91168, 273504, 1094016, 5470080, 32820480
#28800, 25200, 1920, 57600, 3456, 1260, 1440, 9216, 41472, 30240, 6300, 1728, 44100, 18480, 2160, 27000, 43200, 8192, 1680, 3840, 24576, 14400, 25920, 1800, 5760, 30030, 36864, 46080, 10080, 12960, 51840, 20160, 6720, 32768, 1536, 1080, 50400, 4320, 2310, 13824, 53760, 60480, 36960, 37800, 16384, 8640, 10800, 18432, 49152, 30720, 21600, 7200, 6144, 40320, 15120, 32400, 13860, 20736, 1296, 17280, 3600, 2592, 4620, 2048, 34560, 31104, 38880, 27648, 15552, 23040, 7776, 4096, 4608, 1024, 11520, 55296, 26880, 2304, 2520, 46656, 3072, 5184, 7560, 12600, 9240, 10368, 1152, 5040, 7680, 2880, 45360, 60060, 3360, 15360, 55440, 13440, 12288, 6912, 6480, 5400, 27720, 54000
#36, 60, 72, 108, 112, 120, 180, 198, 216, 240, 288, 300, 360, 420, 504, 528, 540, 600, 720, 1224, 1320, 1980, 2024, 2268, 2320, 6120, 8568
#2230272, 1734656, 3717120, 3717120, 2230272, 15611904, 11151360, 11151360, 3717120, 2230272, 37914624, 5699584, 3717120, 18585600, 11151360, 2230272, 35932160, 6690816, 18585600, 6690816, 11151360, 265402368, 743424, 26019840, 189573120, 140507136, 33454080
#1584, 13200, 55440, 3168, 34320, 80784, 90288, 182160, 1148400, 245520, 683760, 3182256, 476784, 521136, 326480, 4143216, 161040, 3714480, 562320, 154176, 291984, 394416, 1174800, 10157840, 799920
#12600, 15120, 2016, 6912, 674784, 584496, 22274208, 14256, 145805616, 175824, 726983136, 139678448
#277200, 166320, 22176, 76032, 674784, 584496, 22274208, 14256, 145805616, 175824, 726983136, 1536462928
#80, 2024, 1188, 7201568, 15542912, 285824, 5789168, 4352299952
#218229867580032
#(1e5 .. 1e5+100)...
#2..100 -> map { _* 7771456}...
#15542912
#~ 2..10000 -> map {
#~ #lcm(1240624, _.dec)
#~ lcm(16016, _)
#~ }...
#100 .. 1000 ->grep{.is_prime} -> map { 2626624 * _ }...
#42025984
#2626624 * 32
#10506496
2..100 -> grep{.is_odd}.map{_ * 10506496}...
].map{ lcm(_, 16016); _ }.uniq.sort_by{a(_).len}
# 16016 -- lcm
# 720, 792, 864, 1440, 4320, 5040, 7560, 10080, 11232, 30240, 50400, 55440
# 1440, 5040, 8640, 10080, 11232, 12960, 13440, 14400, 15120, 30240, 50400, 846720
for n in (arr) {
if (n.sigma0 > 1e6) {
say "n = #{n} has too many divisors -- stopping"
break
}
var primes = a(n) #.grep{.inc.is_smooth(20)}
next if (primes.len < 20)
say "# Primes: #{n} -> #{primes.len}"
# 176
#for k in (min(primes.len>>1, 24) `downto` 3) {
#var good_primes = Set(3, 5, 17, 23, 89)
#var good_primes = Set(3, 5, 17, 23, 29, 53, 83, 89)
#var good_primes = Set(3, 5, 17, 23, 29, 53, 89, 113, 127)
var good_primes = Set(3, 5, 17, 23, 29, 53, 89, 113, 257, 353)
#var good_primes = Set(3, 5, 17)
var good_prod = good_primes.prod
primes -= good_primes
var t = primes.prod
#~ for k in (4..8) {
#~ var count = 0
#~ primes.grep{!good_primes.has(_)}.combinations(k, {|*list|
#~ var v = list.prod*good_prod
#~ if (v > 18446744073709551616) {
#~ say v if v.is_carmichael
#~ }
#~ break if (++count > 1e4)
#~ })
#~ }
#~ next
#var good_primes = Set(3, 5, 17, 23, 29, 53, 89)
for k in (primes.len-(9-good_primes.len) `downto` 1) {
next if (primes.len-k + good_primes.len > 20)
var count = 0
primes.flip.combinations(k, {|*list|
var v = (good_prod * t/list.prod)
if (is_carmichael(v)) {
say v if (v > 2**64)
if (is_abundant(v)) {
die "Found abundant: #{v}"
}
}
break if (++count > 1e5)
})
}
}