Project Eulerをシェル芸で解いてみる(Problem 12)

概要

Project Euler¹は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。

しかし、シェル芸²による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。

本記事では、Project EulerのProblem 12を、シェル芸で解いた際の過程を述べる。

実行環境

• Arch Linux (x86_64, 4.3.3-2-ARCH)
• bash (4.3.42, POSIX互換モード)
• GNU coreutils (8.24)
• gawk (4.1.3)

問題文

[原文 (https://projecteuler.net/problem=12)]

The sequence of triangle numbers is generated by adding the natural numbers. So the $7^{th}$ triangle number would be $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2012)]

三角数の数列は自然数の和で表わされ, 7番目の三角数は $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$ である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, \dots

となる.
最初の7項について, その約数を列挙すると, 以下のとおり.

1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.
では, 500個より多く約数をもつ最初の三角数はいくつか.

正答は、注釈³に記載する。

解法

1	#!/bin/sh
2	
3	yes 高須クリニック \
4	| # お約束のやつ
5	sed -n '=' \
6	| # 自然数の生成
7	sed -e 's;[0-9]\{1,\};&*(&+1) / 2;' \
8	| # 三角数の導出式の生成
9	bc \
10	| # 三角数の出力
11	factor \
12	| # 三角数の素因数分解
13	awk '{
14	        sol=1;
15	        for(i=2; i<=NF; i++){d[$i]++};
16	        for(n in d){sol*=(d[n]+1); delete d[n]};
17	        print $1, sol;
18	    }' \
19	| # 各三角数について約数の個数を出力
20	gawk '500 < $2 {print gensub(/:/, "", "g", $1); exit}'
21	  # 約数の個数が初めて500を超える三角数の出力

解説

まず、解答方針を述べる。

ある自然数の素因数と約数の個数の関係を利用する。

ある自然数 $n$ の素因数分解が

n = P_1^{a_{1}} P_2^{a_{2}} \dots P_m^{a_{m}}

であるとき、 $n$ の約数の個数 $d(n)$ は、以下の式で表せる。(参考サイト1)

d(n) = (a_1 + 1)(a_2 + 1) \dots (a_m + 1) \hspace{5em} (1)

具体例として、 $84$ の約数の個数を導出する。

まず、 $84$ を素因数分解すると、以下のようになる。

84 = 2^2 \times 3^1 \times 7^1

この結果より、 $84$ の素因数は $2, 3, 7$ の3種類である。
ここで、それぞれの素因数について、指数部の値に注目する。
$2, 3, 7$ の指数部の値は、それぞれ $2, 1, 1$ である。

これを前述した式 $(1)$ に当てはめて考えると、

d(84) = (2+1)(1+1)(1+1)
      = 12

となる。
よって、$84$ の約数の個数は、 $12$ 個である。

本設問では、上記の性質を実装すれば良い。

---

次に、ソースコードの解説を述べる。

初めに、三角数の数列を生成する。
三角数を出力するために、まずは自然数を生成することにする。

自然数の生成は、3~5行目のyesとsedによっておこなう。
yesで高須クリニックを無限に生成し、それをsedのパターンスペース自動出力の抑制オプションと現在の行番号を出力するコマンドを適用し、自然数の数列を生成する。

次に、自然数を三角数に変換する。
$n$番目の三角数は、 $n(n+1)/2$ で算出することができる。(参考サイト2)
よって、生成した自然数の数列に対して、この算出式を適用していけば、三角数の数列が得られる。
この処理は、7~9行目のsedとbcによっておこなう。
sedによって上記の算出式を生成し、それをbcに渡すことによって、三角数の数列を出力している。

そして、前述した性質を利用し、三角数に対してそれぞれの約数の個数を求めていく。
まず、各三角数について、素因数分解をおこなう。
この処理は、11行目のfactorによっておこなう。
次に、各三角数の素因数から、約数の個数を求める。
この処理は、13~18行目のawkによっておこなう。
awkのコードは、前述した式 $(1)$ を実装したものである。
以上の処理によって、各三角数について約数の個数を求めることができる。

最後に、約数の個数が初めて500を超える三角数を出力する。
この処理は、20行目のgawkによっておこなう。
処理系をgawkと明示した理由は、gawkのみに実装されている組込関数、gensub()を利用するためである。

以上が、500個より多く約数をもつ最初の三角数を求める方法である。

参考にしたもの

1. 約数の個数の公式と平方数の性質 | 高校数学の美しい物語 〈http://mathtrain.jp/numberofd〉
2. 三角数とは，三角数定理，平方数との関係 | 高校数学の美しい物語 〈http://mathtrain.jp/sankakusu〉

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh

• 何のひねりも無い解答...
  • ただ、段々とシェル芸的に面白い問題になってきた気がする。
  • こう、入力をゴニョゴニョ弄り回してから集計するような問題が、個人的には好き。Unixツールの本領が発揮できるので。
• (参考にしたものは、Webサイトじゃなくて、できれば書籍にするべきだったのかも...)
  • 個人的にだけれど、書籍は一番信頼できる情報源なので。
  • けれど、素因数と約数の個数の関係が解説してある書籍、見つからなかったんだよね...

---

1. About - Project Euler (https://projecteuler.net) ↩

2. シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩

3. 76576500 ↩