AtCoder ABC110 D 素数生成42424626

ABC110 のテストケース

　AtCoder の先週の ABC110 はテストケースが甘い件の悪い面が出たようで、B はテストケースが条件に合っておらず、C は文字数を数えただけの嘘解法がACしていたせいか、レーティングの対象にならなかった。よしよし。30分寝すごして C を ACしそこねた黒歴史を葬り去ることができるぞ。いいぞ。

　ABC のテストケースが甘いのは AtCoder が数学寄りで、難しい問題を作るのに頭をヒネっているので、ABC程度の簡単な問題に手間をかけていないからだろう。人のことはいえないので、これくらいにして D だ。

ABC110 D

　D は素因数分解する部分と場合の数を数え上げる部分の二つからなる。素因数分解するところまでは自力でできたが、そこからどう約数の組合わせを数えあげていけばいいのか全然思いつかず、解法をみてしまった。約数を構成する各素数毎に個数を数えあげ、それぞれで重複組み合わせを計算してかければよいと。重複組み合わせは普通の組み合わせが中身の組み合わせであるのに対し、中身の分け方の組み合わせなので、中に仕切りをいれてその仕切りの組み合わせを数えるというのでよく、普通の組み合わせの応用でできる。なるほど。なるほど。さて、そこからが問題で、ABC各問題にくらべてDはちゃんとテストケースがエグいところを突いていたのでいつまでたってもACできなかった。

ABC110 D 重複組み合わせ

　先に重複組み合わせの方のことを書いておくと、こないだやった ABC042 D の応用でついつい階乗の配列を作り階乗の逆元の配列をつくるなどという面倒なことをしていたが、ABC042 D ほど組み合わせを数えまくるわけではないので普通に逆元出してもいいようだ。というか、逆元出さずに計算の省略もせずに組み合わせの公式そのまま計算しても間に合うようだった。ところで累乗出すのに二分累乗法を自分で組まなくても python3 だと pow で剰余の処理までしてくれるのに気付かなかった。まぁいいか。

　初等整数論について、(一般人でも金出したら使える)立命館の図書館に行って開架に並んでいる初等整数論の本を読んできたが以下の本が非常にわかりやすかった。

初等整数論 (日評数学選書)

　逆元というのは群論の中で出てくる概念のようだ。数学に出てくるいろんな構造を演算の方法で分類するというもので、前に書いた記事で逆元は行列の逆行列みたいなものかと書いたが、逆にそういう考え方をするのが群論ということで、ある演算体系において結合と定義する演算があり(いわゆるかけ算に相当)、何に「結合」しても自分になるのが単位元(整数でいうところの1)、単位元以外のあるものに単位元以外のものを「結合」して単位元になるものが逆元ということのようだ。つまり行列の逆元が逆行列であるということのようだ。剰余の概念自体は昔からあるものだが、ガウスが合同式をひねり出したおかげで剰余世界の考察がしやすくなったように、そういう見方を導入したおかげで数学のある分野の知識が他の分野へ応用しやすくなったりしてるんだろうな。よく知らんが。剰余の逆元でググるといろんな人がいろんな説明をしているが、そのなかに結構誤解のようなものも含まれている。外形的なアプローチ(群論)でみる逆元と内部的なアプローチ(整数論)でみる逆元のどちらで覚えたかで説明のしかたが異なるからだろう。使えればどうでもいい。逆元の出し方にも工夫があるようだがちょっとそこまで手が及んでないので次の課題とする。

ABC110 D 素数生成42424626

　で、最初にもどって素数の出しかただが、Python3 勢では自分とおなじように2からはじめて1足していく方法でループを回しているのがほとんどだったが、中におもしろい出し方をしてる人がいた。yutote さんのこれ。

提出 #3259690 - AtCoder Beginner Contest 110

increments = itertools.chain([1,2,2],itertools.cycle([4,2,4,2,4,6,2,6]))

　1足していかずにこのように間隔で足してゆくのだが、最初見たときはある数字以下では素数を出せる式があるのだろうか、と考えてしまった。42424626でググるとなにか素数の本でも出てくる数列のようだ。この数字の性質をみるために実際に足していって出てくる数字がそれまで出てきた素数で割り切れるのかどうか試してみた。

import itertools
f = 2
p = []
increments = itertools.chain([1,2,2],itertools.cycle([4,2,4,2,4,6,2,6]))
for incr in increments:
    if  f > 121 + 20:
        break
    isPrime = True
    alist = []
    for ip in p:
        if f % ip == 0:
            isPrime = False
            alist.append(ip)
    if isPrime:
        print(f,"o",incr)
        p.append(f)
    else:
        print(f,"x",incr,','.join([str(x) for x in alist]))
    f += incr
print(','.join([str(x) for x in p]))

　こんな感じのものを書いてみるとこうなる。(変数の命名規則が違うのはもとのをそのまま使ってるのが多いから)

　出てくる数 | それまで出てきた素数で割れないか | 次足す数 | 割れるとき、割った素数

2 o 1  
3 o 2
5 o 2
7 o 4
11 o 2
13 o 4
17 o 2
19 o 4
23 o 6
29 o 2
31 o 6
37 o 4
41 o 2
43 o 4
47 o 2
49 x 4 7
53 o 6
59 o 2
61 o 6
67 o 4
71 o 2
73 o 4
77 x 2 7,11
79 o 4
83 o 6
89 o 2
91 x 6 7,13
97 o 4
101 o 2
103 o 4
107 o 2
109 o 4
113 o 6
119 x 2 7,17
121 x 6 11
127 o 4
131 o 2
133 x 4 7,19
137 o 2
139 o 4
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139

　ほぉ... つまり 42424626 は 2,3,5 の倍数の隙間にみられる規則ですな。簡易なエラトステネスの篩というところか。実はググると出てくる英語の素数の本に 42424626 は3回くりかえすまで規則が破られないとか出てくるので、11の二乗くらいから破れるんだろうとおもって上限を121+20に設定したものの、意外にも 7x7 の49で破られていた。英語の素数の本もあてにならんな。しかしこれ素数がたくさん必要なときに便利かもしれない。

　ところで昔の初等整数論の本読んでると 4n+1に素数が濃厚とか4n-1に濃厚だとかいう話題が出てくるが、これも単にエラトステネスの篩の言い換えなんじゃないかという気がしてきた。

数学入門〈上〉 (岩波新書)

現代数学入門 (ちくま学芸文庫)