190815

Ruby


(m * 10)^n - 1 の素因数分解

Q. 728999999を素因数分解せよ.

という問題をtwitter で見て触発された。

require 'prime'

def show(n, ary)
  print "#{n} = "
  (0..ary.size - 1).each{|i|
    print " * " if i > 0
    print "#{ary[i][0]}"
    j = ary[i][1]
    print "^#{j}" if j > 1
  }
  puts
end

(2..10).each{|i|
  (1..20).each{|j|
    k = (j * 10) ** i - 1
    show(k, k.prime_division)
  }
}

出力結果
99 = 3^2 * 11
399 = 3 * 7 * 19
899 = 29 * 31
1599 = 3 * 13 * 41
2499 = 3 * 7^2 * 17
3599 = 59 * 61
4899 = 3 * 23 * 71
6399 = 3^4 * 79
8099 = 7 * 13 * 89
9999 = 3^2 * 11 * 101
12099 = 3 * 37 * 109
14399 = 7 * 11^2 * 17
16899 = 3 * 43 * 131
19599 = 3 * 47 * 139
22499 = 149 * 151
25599 = 3 * 7 * 23 * 53
28899 = 3^2 * 13^2 * 19
32399 = 179 * 181
36099 = 3^3 * 7 * 191
39999 = 3 * 67 * 199
999 = 3^3 * 37
7999 = 19 * 421
26999 = 7^2 * 19 * 29
63999 = 3^2 * 13 * 547
124999 = 7^2 * 2551
215999 = 7 * 59 * 523
342999 = 3^2 * 23 * 1657
511999 = 79 * 6481
728999 = 89 * 8191
999999 = 3^3 * 7 * 11 * 13 * 37
1330999 = 109 * 12211
1727999 = 7 * 13 * 17 * 1117
2196999 = 3^2 * 7 * 43 * 811
2743999 = 19 * 139 * 1039
3374999 = 149 * 22651
4095999 = 3^2 * 31 * 53 * 277
4912999 = 7 * 13^2 * 4153
5831999 = 31 * 179 * 1051
6858999 = 3^4 * 7 * 12097
7999999 = 7 * 199 * 5743
9999 = 3^2 * 11 * 101
159999 = 3 * 7 * 19 * 401
809999 = 17 * 29 * 31 * 53
2559999 = 3 * 13 * 41 * 1601
6249999 = 3 * 7^2 * 17 * 41 * 61
12959999 = 13 * 59 * 61 * 277
24009999 = 3 * 13^2 * 23 * 29 * 71
40959999 = 3^4 * 37 * 79 * 173
65609999 = 7 * 13 * 89 * 8101
99999999 = 3^2 * 11 * 73 * 101 * 137
146409999 = 3 * 37 * 109 * 12101
207359999 = 7 * 11^2 * 17 * 14401
285609999 = 3 * 43 * 131 * 16901
384159999 = 3 * 17 * 47 * 139 * 1153
506249999 = 149 * 151 * 22501
655359999 = 3 * 7 * 23 * 53 * 25601
835209999 = 3^2 * 13^2 * 19 * 28901
1049759999 = 179 * 181 * 32401
1303209999 = 3^3 * 7 * 13 * 191 * 2777
1599999999 = 3 * 13 * 17 * 67 * 181 * 199
99999 = 3^2 * 41 * 271
3199999 = 11 * 19 * 61 * 251
24299999 = 29 * 837931
102399999 = 3 * 13 * 2625641
312499999 = 7^2 * 6377551
777599999 = 11 * 59 * 1198151
1680699999 = 3 * 11 * 23 * 31 * 61 * 1171
3276799999 = 11 * 79 * 751 * 5021
5904899999 = 89 * 281 * 236111
9999999999 = 3^2 * 11 * 41 * 271 * 9091
16105099999 = 109 * 147753211
24883199999 = 7 * 17 * 209102521
37129299999 = 3 * 11^2 * 43 * 2378711
53782399999 = 31 * 139 * 541 * 23071
75937499999 = 149 * 331 * 1539721
104857599999 = 3 * 41 * 53 * 991 * 16231
141985699999 = 11 * 13^2 * 151 * 505811
188956799999 = 11 * 41 * 61 * 179 * 38371
247609899999 = 3^3 * 7 * 11 * 31 * 1231 * 3121
319999999999 = 199 * 3361 * 478441
999999 = 3^3 * 7 * 11 * 13 * 37
63999999 = 3^2 * 7 * 19 * 127 * 421
728999999 = 7^2 * 13 * 19 * 29 * 31 * 67
4095999999 = 3^2 * 7 * 13 * 41 * 223 * 547
15624999999 = 3^2 * 7^2 * 17 * 19 * 43 * 2551
46655999999 = 7 * 59 * 61 * 523 * 3541
117648999999 = 3^2 * 23 * 71 * 1657 * 4831
262143999999 = 3^5 * 7^2 * 43 * 79 * 6481
531440999999 = 7 * 13 * 89 * 8011 * 8191
999999999999 = 3^3 * 7 * 11 * 13 * 37 * 101 * 9901
1771560999999 = 3^2 * 7 * 37 * 109 * 571 * 12211
2985983999999 = 7 * 11^2 * 13 * 17 * 1117 * 14281
4826808999999 = 3^2 * 7 * 31 * 43 * 131 * 541 * 811
7529535999999 = 3^2 * 13 * 19 * 47 * 139 * 499 * 1039
11390624999999 = 7 * 31 * 103 * 149 * 151 * 22651
16777215999999 = 3^2 * 7 * 13 * 19 * 23 * 31 * 53 * 103 * 277
24137568999999 = 3^3 * 7 * 13^2 * 19 * 61 * 157 * 4153
34012223999999 = 7 * 31 * 179 * 181 * 1051 * 4603
47045880999999 = 3^4 * 7 * 191 * 12097 * 35911
63999999999999 = 3^2 * 7 * 67 * 199 * 5743 * 13267
9999999 = 3^2 * 239 * 4649
1279999999 = 19 * 29 * 71 * 32719
21869999999 = 29 * 71 * 113 * 93997
163839999999 = 3 * 13 * 4201025641
781249999999 = 7^3 * 2277696793
2799359999999 = 59 * 47446779661
8235429999999 = 3 * 23 * 20693 * 5767847
20971519999999 = 79 * 265462278481
47829689999999 = 43 * 89 * 18803 * 664679
99999999999999 = 3^2 * 11 * 239 * 4649 * 909091
194871709999999 = 29 * 109 * 156157 * 394787
358318079999999 = 7^2 * 17 * 430153757503
627485169999999 = 3 * 43 * 911 * 5339435921
1054135039999999 = 29 * 43 * 139 * 6081560003
1708593749999999 = 43 * 149 * 59879 * 4453583
2684354559999999 = 3 * 53 * 16882733081761
4103386729999999 = 13^2 * 29 * 43 * 19471046393
6122200319999999 = 179 * 34202236424581
8938717389999999 = 3^3 * 7^2 * 29^2 * 71 * 2017 * 56099
12799999999999999 = 199 * 213361 * 301468441
99999999 = 3^2 * 11 * 73 * 101 * 137
25599999999 = 3 * 7 * 19 * 401 * 160001
656099999999 = 17 * 29 * 31 * 53 * 241 * 3361
6553599999999 = 3 * 13 * 41 * 769 * 1601 * 3329
39062499999999 = 3 * 7^2 * 17 * 41 * 61 * 97 * 64433
167961599999999 = 13 * 17 * 59 * 61 * 277 * 281 * 2713
576480099999999 = 3 * 13^2 * 17 * 23 * 29 * 71 * 353 * 4001
1677721599999999 = 3^4 * 37 * 79 * 173 * 40960001
4304672099999999 = 7 * 13 * 89 * 8101 * 65610001
9999999999999999 = 3^2 * 11 * 17 * 73 * 101 * 137 * 5882353
21435888099999999 = 3 * 17^2 * 37 * 109 * 12101 * 506609
42998169599999999 = 7 * 11^2 * 17 * 41 * 14401 * 5057561
81573072099999999 = 3 * 43 * 97 * 131 * 16901 * 2944433
147578905599999999 = 3 * 17 * 47 * 139 * 1153 * 384160001
256289062499999999 = 41 * 149 * 151 * 193 * 22501 * 63977
429496729599999999 = 3 * 7 * 23 * 53 * 25601 * 655360001
697575744099999999 = 3^2 * 13^2 * 19 * 457 * 28901 * 1827593
1101996057599999999 = 179 * 181 * 32401 * 1049760001
1698356304099999999 = 3^3 * 7 * 13 * 89 * 191 * 1753 * 2777 * 8353
2559999999999999999 = 3 * 13 * 17 * 67 * 181 * 199 * 1889 * 847009
999999999 = 3^4 * 37 * 333667
511999999999 = 19 * 421 * 64008001
19682999999999 = 7^2 * 19 * 29 * 729027001
262143999999999 = 3^3 * 13 * 163 * 547 * 8376409
1953124999999999 = 7^2 * 2551 * 15625125001
10077695999999999 = 7 * 59 * 523 * 46656216001
40353606999999999 = 3^3 * 23 * 37 * 1657 * 1059903991
134217727999999999 = 19 * 79 * 181 * 1531 * 6481 * 49789
387420488999999999 = 37 * 89 * 8191 * 14363289973
999999999999999999 = 3^4 * 7 * 11 * 13 * 19 * 37 * 52579 * 333667
2357947690999999999 = 73 * 109 * 12211 * 24267977137
5159780351999999999 = 7 * 13 * 17 * 19 * 37 * 1117 * 4247490367
10604499372999999999 = 3^3 * 7 * 19 * 43 * 811 * 84680898193
20661046783999999999 = 19 * 139 * 163 * 1039 * 46193489227
38443359374999999999 = 19 * 73 * 149 * 433 * 1801 * 10531 * 22651
68719476735999999999 = 3^3 * 31 * 37 * 53 * 277 * 613 * 246567907
118587876496999999999 = 7 * 13^2 * 4153 * 102673 * 235091737
198359290367999999999 = 19 * 31 * 179 * 199 * 379 * 1051 * 1171 * 20269
322687697778999999999 = 3^5 * 7 * 12097 * 15681962619667
511999999999999999999 = 7 * 199 * 5743 * 64000008000001
9999999999 = 3^2 * 11 * 41 * 271 * 9091
10239999999999 = 3 * 7 * 11 * 19 * 61 * 251 * 152381
590489999999999 = 11 * 29 * 31 * 71261 * 837931
10485759999999999 = 3 * 11^2 * 13 * 41 * 20641 * 2625641
97656249999999999 = 3 * 7^2 * 11 * 17 * 557041 * 6377551
604661759999999999 = 11 * 31 * 59 * 61 * 411211 * 1198151
2824752489999999999 = 3 * 11 * 23 * 31 * 61 * 71 * 131 * 1171 * 180701
10737418239999999999 = 3^4 * 11 * 79 * 751 * 5021 * 40454321
34867844009999999999 = 7 * 11 * 13 * 89 * 281 * 571 * 10331 * 236111
99999999999999999999 = 3^2 * 11 * 41 * 101 * 271 * 3541 * 9091 * 27961
259374246009999999999 = 3 * 37 * 109 * 461 * 491 * 641 * 147753211
619173642239999999999 = 7 * 11^2 * 17 * 31 * 2531 * 2621 * 209102521
1378584918489999999999 = 3 * 11^2 * 43 * 131 * 9391 * 30181 * 2378711
2892546549759999999999 = 3 * 11 * 31 * 47 * 139 * 211 * 541 * 23071 * 164341
5766503906249999999999 = 11 * 149 * 151 * 241 * 331 * 189701 * 1539721
10995116277759999999999 = 3 * 7 * 11 * 23 * 41 * 53 * 991 * 16231 * 59208131
20159939004489999999999 = 3^2 * 11 * 13^2 * 19 * 31 * 151 * 505811 * 26784701
35704672266239999999999 = 11 * 41 * 61 * 179 * 181 * 38371 * 1043960221
61310662578009999999999 = 3^3 * 7 * 11 * 31 * 191 * 661 * 1231 * 3121 * 1961251
102399999999999999999999 = 3 * 11 * 67 * 199 * 3361 * 478441 * 144730891