gcd(80, n) > gcd(50, n) でうるう年が分かるらしい

gcd(80, n) > gcd(50, n) でうるう年が分かるらしい

gcd(80, n) > gcd(50, n) でうるう年が分かるらしい

面白いツイートを見つけました。
Lynnさんのツイートです。

I don't know who needs to hear this but year "n" is a leap year iff

　　gcd(80, n) > gcd(50, n)
— Lynn (@chordbug) 2021年3月22日

簡単にいうと、「 $\gcd(80, n) > \gcd(50, n)$ が成り立つとき、 $n$ はうるう年である」ということです。

本当に？

そもそもうるう年とは？

うるう年とは2月29日が存在する年で、うるう年である年の定義は以下のようになります。

西暦年が4の倍数のときはうるう年。
ただし、西暦年が100で割り切れる年は平年（つまりうるう年でない）。
ただし、西暦年が400で割り切れる年は必ずうるう年。

ただし書きが2回も連続してうざいですね。

一応、わかりにくいという方のために、JavaとHaskellでうるう年の判定をする関数のソースコードを書いたので貼っておきます。

Java

public class Main{
    public static boolean isLeapYear(int n) {
        if (n % 400 == 0) return true;
        else if (n % 100 == 0) return false;
        else if (n %   4 == 0) return true;
        else return false;
    }
    public static void main(String[] args) {
        System.out.println(isLeapYear(1900));
        System.out.println(isLeapYear(2000));
        System.out.println(isLeapYear(2001));
        System.out.println(isLeapYear(2004));
    }
}

出力結果：

false
true
false
true

Haskell

isLeapYear n
  | n `mod` 400 == 0 = True
  | n `mod` 100 == 0 = False
  | n `mod`   4 == 0 = True
  | otherwise        = False

main = do
    print $ isLeapYear 1900
    print $ isLeapYear 2000
    print $ isLeapYear 2001
    print $ isLeapYear 2004

出力結果：

False
True
False
True

最大公約数ってなんだっけ？

最大公約数は小学校で習うのですが、僕は「小学校で習ったから覚えてるよね？」と威圧する風潮が大嫌いなので*1、ここで説明します。

例えば、12と18について

12は、1か2か3か4か6か12で割り切れます。これは「12は、1の倍数で、2の倍数で、3の倍数で、4の倍数で、6の倍数で、12の倍数である」とも言えます。

18は、1か2か3か4か6か9か18で割り切れます。これは「18は、1の倍数で、2の倍数で、3の倍数で、4の倍数で、6の倍数で、9の倍数で、18の倍数である」とも言えます。

つまり、12と18は、どちらも、1の倍数と2の倍数と3の倍数と4の倍数と6の倍数であるということになります。このとき、1と2と3と4と6を「12と18の公約数」と言います。そう、公の約数ですね。

えっなんで「"共"約数」じゃないのかって？多分、英語名のcommon divisorを訳したら「公約数」になっちゃったんじゃないんですか？（想像）

さて、話を戻しましょう。

公約数たちの中で一番大きい公約数を最大公約数と言います。

つまり、先程の例だと1と2と3と4と6の中で6が一番大きいので、「12と18の最大公約数」は6です。これを数式で、 $\gcd(12, 18) = 6$ というふうに表記します。

なんとなく2000年代の周りを調べてみる

nが1990～2030のときのgcd(80, n)の値です。

f:id:skytomo:20210325190957p:plain

一方こちらは、nが1990～2030のときのgcd(50, n)の値です。

f:id:skytomo:20210325191100p:plain

これらを重ね合わせると……

f:id:skytomo:20210325191155p:plain

オレンジの部分が見えるところが、オレンジ（ $\gcd(80, n)$ ）が青色（ $\gcd(50, n)$ ）より大きい部分です。たしかに、うるう年と一致している……？

うーん、ちゃんと証明しましょう。

さあ証明の時間だ

もっとエレガントが方法があるかもしれません。（あったら教えて）

あと数学は得意ではないので、厳密な証明とかできません。そこのところはご了承ください。

nが400である倍数のとき

まずは $n$ が $400$ の倍数であるときのことを考えてみましょう。

$400$ の倍数である数を $n_{400}$ とします。

$400 = 80 \times 5$ なので、
必ず $\gcd(80, n_{400}) = 80$ になります。

また、
$400 = 50 \times 8$ なので、
必ず $\gcd(50, n_{400}) = 50$ になります。

つまり、 $n$ が $400$ の倍数であるとき
必ず $\gcd(80, n) > \gcd(50, n)$ となります。

nが400の倍数ではないが、100の倍数であるとき

次に $n$ が $400$ の倍数ではないが、 $100$ の倍数であるときのことを考えてみましょう。
$400$ の倍数ではないが、 $100$ の倍数である数を $n_{100}$ とします。

$100 = 50 \times 2$ なので、
必ず $\gcd(50, n_{100}) = 50$ になります。

ところで、
$400$ と $100$ を素因数分解すると
$400 = 2 ^ 4 \times 5 ^ 2$
$100 = 2 ^ 2 \times 5 ^ 2$
となります。
つまり、 $n_{100}$ は、 $2$ で最大 $2$ 回もしくは $3$ 回割り切れる必要がありますね。
（これはどういうことかというと、 $n_{100}$ が $2$ で割り切れる回数が $2$ 回より少ないと $100$ の倍数でなくなってしまい、逆に $2$ で割り切れる回数が $4$ 回以上になると $400$ の倍数になってしまうということです。）

$80$ は $5$ では最大 $1$ 回までしか割り切れず、
$n_{100}$ は、 $2$ で最大 $3$ 回までしか割り切れないため、
必ず $\gcd(80, n_{100}) ≦ 40 = 5 ^ 1 \times 2 ^ 3$ になります。

つまり、 $n$ が $400$ の倍数ではないが、 $100$ の倍数であるとき
必ず $\gcd(80, n) ≦ \gcd(50, n)$ となります。

nが100の倍数ではないが、4の倍数であるとき

最後に $n$ が $100$ の倍数ではないが、 $4$ の倍数であるときのことを考えてみましょう。
$100$ の倍数ではないが、 $4$ の倍数である数を $n_4$ とします。

$100$ と $4$ を素因数分解すると
$100 = 2 ^ 2 \times 5 ^ 2$
$4 = 2 ^ 2$
となります。
つまり、 $n_4$ は、 $5$ で最大 $0$ 回もしくは $1$ 回割り切れる必要がありますね。
（ $5$ で割り切れる回数が $2$ 回以上になると $100$ の倍数になってしまいます。）

$50$ は $2$ では最大 $1$ 回までしか割り切れず、
$n_4$ が、 $5$ の倍数でない場合、必ず $\gcd(50, n) ≦ 2 = 2 ^ 1$ になります。
$n_4$ が、 $5$ の倍数である場合、必ず $\gcd(50, n) ≦ 10 = 2 ^ 1 \times 5 ^ 1$ になります。

一方で
$80 = 4 \times 4 \times 5$ なので、
$n_4$ が、 $5$ の倍数でない場合、必ず $\gcd(80, n) ≧ 4$ になります。
$n_4$ が、 $5$ の倍数であった場合、必ず $\gcd(80, n) ≧ 20$ になります。

つまり、 $n$ が $100$ の倍数ではないが、 $n$ が $4$ の倍数であるとき必ず $\gcd(80, n) > \gcd(50, n)$ となります。

nが4の倍数でないとき

（追記です。）

見事にこの証明をするのを忘れてました……

$n$ が $4$ の倍数でないのことを考えてみましょう。

$4$ の倍数でない数を $m$ とします。

$m$ が $5$ で $0$ 回割り切れ、 $2$ で $0$ 回割り切れるとき、 $\gcd(80, m) = \gcd(50, m) = 1$ となります。

$m$ が $5$ で $1$ 回割り切れ、 $2$ で $0$ 回割り切れるとき、 $\gcd(80, m) = \gcd(50, m) = 5$ となります。

$m$ が $5$ で $2$ 回以上割り切れ、 $2$ で $0$ 回割り切れるとき、 $\gcd(80, m) = 5 \lt \gcd(50, m) = 25$ となります。

$m$ が $5$ で $0$ 回割り切れ、 $2$ で $1$ 回割り切れるとき、 $\gcd(80, m) = \gcd(50, m) = 2$ となります。

$m$ が $5$ で $1$ 回割り切れ、 $2$ で $1$ 回割り切れるとき、 $\gcd(80, m) = \gcd(50, m) = 10$ となります。

$m$ が $5$ で $2$ 回以上割り切れ、 $2$ で $1$ 回割り切れるとき、 $\gcd(80, m) = 10 \lt \gcd(50, m) = 50$ となります。

といわけで、 $n$ が $4$ の倍数でないとき必ず $\gcd(80, n) ≦ \gcd(50, n)$ となります。

まとめ

$n$ が $400$ の倍数であるとき $\gcd(80, n) > \gcd(50, n)$
$n$ が $400$ の倍数ではないが、 $100$ の倍数であるとき $\gcd(80, n) ≦ \gcd(50, n)$
$n$ が $100$ の倍数ではないが、 $n$ が $4$ の倍数であるとき $\gcd(80, n) > \gcd(50, n)$
$n$ が $4$ の倍数ではないとき $\gcd(80, n) ≦ \gcd(50, n)$

見事にうるう年の定義と一致していますね。

コードの書き直し

ソースコードを書き直してみました。

Java（改）

public class Main{
    public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    public static boolean isLeapYear(int n) {
        return gcd(80, n) > gcd(50, n);
    }
}

Javaには最大公約数を求める関数がないので、自前で定義する必要があります。とはいえ、ユークリッドの互除法と再帰を使って一行で書けます。

Haskell（改）

isLeapYear n = gcd 80 n > gcd 50 n

うん、すっきりしましたね。

ちなみにコードを短くすることはできますが、パフォーマンス的にはあまりおいしくないと思うのでコードゴルフでもしない限り、普通に書いたほうがいいんじゃないでしょうか。

*1:半分冗談ですよ、半分本気ですけど。あと、わざわざここで説明するのは、日本語の「最大公約数的に」という言葉の使い方について考えてほしいというねらいもありますが、こんなことでここに書くべきことじゃないかもしれませんね。

私が気にする100の事象

気にしなければ始まらない。

gcd(80, n) > gcd(50, n) でうるう年が分かるらしい

gcd(80, n) > gcd(50, n) でうるう年が分かるらしい

そもそもうるう年とは？

Java

Haskell

最大公約数ってなんだっけ？

なんとなく2000年代の周りを調べてみる

さあ証明の時間だ

nが400である倍数のとき

nが400の倍数ではないが、100の倍数であるとき

nが100の倍数ではないが、4の倍数であるとき

nが4の倍数でないとき

まとめ

コードの書き直し

Java（改）

Haskell（改）