123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175 |
- #!/usr/bin/ruby
- # Idea: for each number `n` in `arr` and for each lambda `l` in `arr`, replace large prime factors of `l` with other prime divisors from lambda `l`.
- var arr = [
- 487954732492026166035814706202314376705
- 141934960805533535384100259905
- 2609668563371076823446624111609234945
- 22321294006753093794484119100782564881584237146952694846489144434824034305
- 72148620605333310080719701812041760839024918297692839329815300886091224428394819515628545
- 967037403232220731074074563038316755517610240570658812669537184604036430235566311331012838883641380865
- 406402829025353014759868508514893182061635216385
- 15076244937897319383799036175429336548625369631595367899653198961989759434810928251355411574785
- 871005264581548962932418919531990803260747265
- 610012201694720081796846702960249688144417680786846465
- 278162906898013748642772019172998608839057854602841254854175736240572851175099616062424065
- 2963658210542356083852877246926416492931527804540089510269883905
- 1692492088492238622532768569558090666689925078386295740708067178336619326186090793391105
- 644811775887535379664225513644980219319376317839497786625735944865592422785
- 2845358328636614328617082131255054540223949221002124433109986305
- 74875990602425226938138664024259158432269224416705
- 1018329989576989704159754753835889677652405111555820545
- 71967245196653338257378864734797608168672816153312963139871238665985
- 19666546275088335320957353962363201658812107005039715284928928608628170883585
- 129959381219943649417033775959204959948797179242551459265680758859265
- 463149379463251167706230703520995680069543921166639491398457345
- 19948738964527549499432007591778845447137932958457586625953063419475941273954097665
- 165502573617193579886078524884554371013787876466850820614145
- 382314270322310985139418831028955559235551077239363319937510690579825910692881422216705
- 2853450403236152332571821875265293508017495635204070217869999840422343584089739265
- 14701083488299057530174696885922722686956286485260401577115414785
- 61751285336040585295804391670071058142224865543324607243406589162503580666870926270465
- 37839385943068863406967633413004957540054532539686888463944906014566240419460804270776358938980032660929917901837033235462145
- 772459017179480479061611372132330246001039753130436193419524315193543873326133868681083905
- 321030150905393790929751720043602006651739765349595158023943724894346115208705
- ]
- var bern = Hash(
- 1 0
- 2 1
- 3 2
- 4 4
- 5 6
- 6 10
- 7 12
- 8 30
- 9 36
- 10 60
- 11 72
- 12 108
- 13 120
- 14 144
- 15 180
- 16 240
- 17 360
- 18 420
- 19 540
- 20 840
- 21 1008
- 22 1080
- 23 1200
- 24 1260
- 25 1620
- 26 1680
- 27 2016
- 28 2160
- 29 2520
- 30 3360
- 31 3780
- 32 5040
- 33 6480
- 34 7560
- 35 8400
- 36 10080
- 37 12600
- 38 15120
- 39 25200
- 40 30240
- 41 42840
- 42 45360
- 43 55440
- 44 60480
- 45 75600
- 46 85680
- 47 100800
- 48 110880
- 49 128520
- 50 131040
- 51 166320
- 52 196560
- 53 257040
- 54 332640
- 55 393120
- 56 514080
- 57 655200
- 58 665280
- 59 786240
- 60 831600
- 61 917280
- 62 982800
- 63 1081080
- 64 1179360
- 65 1285200
- 66 1310400
- 67 1441440
- 68 1663200
- 69 1965600
- 70 2162160
- 71 2751840
- 72 2827440
- 73 3326400
- 74 3341520
- 75 3603600
- 76 3931200
- 77 4324320
- 78 5654880
- 79 6652800
- 80 6683040
- 81 7207200
- 82 8648640
- 83 10810800
- 84 12972960
- 85 14414400
- 86 18378360
- 87 21621600
- 88 36756720
- 89 43243200
- 90 64864800).values.sort
- var nf = [80, 120, 144, 2520, 5760, 6480, 7920, 15120, 30240, 94248, 110880, 285120, 597168, 604800, 1441440, 1663200, 1738800, 2217600, 5216400, 13305600, 43243200, 64864800, 648648000, 4034016000, 8951342400, 12070749600, 67541947200]
- #say arr.join(' ')
- #var primes = [3, 5, 17, 23, 29, 53, 83, 89, 113, 197, 353, 617]
- #var primes = [3, 5, 17, 23, 29, 53, 83, 89, 113]
- var primes = [3, 5, 17, 23, 29, 83]
- #var primes = [3, 5, 17, 23, 29, 43, 53, 89, 113, 127, 157, 257]
- var P = primes.prod
- for n in (arr) {
- say "# n = #{n.len}"
- var f = n.factor.grep { !primes.has(_) }
- for k in (f.len ^.. f.len-5 ) {
- say "# Combination: #{k}"
- f.combinations(k, {|*a|
- with (a.prod * P) {|c|
- if (c.is_carmichael) {
- say "\n\t\t\tFound: #{c}\n"
- }
- }
- })
- }
- }
- __END__
- for n in (arr.map{.lambda}.uniq.sort) {
- say "# Bern = #{n}"
- var d = n.divisors.grep{ _ > 1}.map{.inc}.grep{.is_prime}.grep{!primes.has(_)}.grep{ _ > primes.max}.grep{ _ < 1e6}
- for k in (1..d.len) {
- say "# Combination: #{k}"
- d.combinations(k, {|*a|
- with (a.prod * P) {|c|
- if (c.is_carmichael) {
- say "\n\t\t\tFound: #{c}\n"
- }
- #say c if c.is_pseudoprime
- }
- })
- }
- }
|