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

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

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

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

# 実行環境
* Arch Linux (x86\_64, 4.3.3-3-ARCH)
* bash (4.3.42, POSIX互換モード)
* GNU coreutils (8.24)
* gawk (4.1.3)

<!---
* bsd-games (2.17)
--->

# 問題文
[原文 ([https://projecteuler.net/problem=21](https://projecteuler.net/problem=21))]
> Let $d(n)$ be defined as the sum of proper divisors of $n$ (numbers less than $n$ which divide evenly into $n$).
> If $d(a) = b$ and $d(b) = a$, where $a \neq b$, then a and b are an amicable pair and each of a and b are called amicable numbers.
> 
> For example, the proper divisors of $220$ are $1, 2, 4, 5, 10, 11, 20, 22, 44, 55$ and $110$; therefore $d(220) = 284$. The proper divisors of $284$ are $1, 2, 4, 71$ and $142$; so $d(284) = 220$.
> 
> Evaluate the sum of all the amicable numbers under $10000$.

[日本語訳 ([http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2021))]
> $d(n)$ を $n$ の真の約数の和と定義する. (真の約数とは $n$ 以外の約数のことである. )
> もし, $d(a) = b$ かつ $d(b) = a$ ($a \neq b$ のとき) を満たすとき, $a$ と $b$ は友愛数(親和数)であるという.
> 
> 例えば, $220$ の約数は $1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110$ なので $d(220) = 284$ である.
> また, $284$ の約数は $1, 2, 4, 71, 142$ なので $d(284) = 220$ である.
> 
> それでは $10000$ 未満の友愛数の和を求めよ.


正答は、注釈[^ans]に記載する。

# 解法
```sh:prob_021.sh
1	#!/bin/sh
2	
3	seq 1 9999 \
4	| # 10000未満の自然数の生成
5	awk '
6	    ORS="";
7	    {
8	        print $0 " ";
9	        for(i=1; i*i<=$0; i++){
10	            if($0%i == 0){
11	                print i " ";
12	                if(i != $0/i && $0 != $0/i){
13	                    print $0/i " "
14	                }
15	            }
16	        };
17	        print "\n"
18	    }
19	    ' \
20	| # それぞれの自然数について約数を列挙
21	awk '{sum=0; for(i=2; i<=NF; i++){sum+=$i}; print $1, sum}' \
22	| # 真の約数の和の出力
23	awk '$1 != $2 {print $0 "\n" $2, $1}' \
24	| # 友愛数候補の生成
25	sort -n \
26	| # 数列のソート
27	uniq -d \
28	| # 友愛数の抽出
29	awk '{sum+=$1} END {print sum}'
30	  # 友愛数の総和の出力
```

以下、コマンドライン上での実行用コードである。

```sh
seq 1 9999 | awk 'ORS=""; {print $0 " "; for(i=1; i*i<=$0; i++){if($0%i == 0){print i " "; if(i != $0/i && $0 != $0/i){print $0/i " "}}}; print "\n"}' | awk '{sum=0; for(i=2; i<=NF; i++){sum+=$i}; print $1, sum}' | awk '$1 != $2 {print $0 "\n" $2, $1}' | sort -n | uniq -d | awk '{sum+=$1} END {print sum}'
```

## 解説
解答は、設問に記載してある友愛数の定義に沿って進める。

まず、10000未満の自然数について、それぞれの約数を列挙する。
この処理は、3行目の`seq`と、5~19行目の`awk`を用いておこなう。
`seq`で自然数を列挙した後、`awk`によって約数を列挙する。

次に、真の約数の和を算出する。
この処理は、21行目の`awk`によっておこなう。
1フィールド目の値は元の自然数であるため、真の約数である2フィールド目以降の総和を求める。

そして、10000未満の自然数のうち、友愛数となる組み合わせを抽出する。
ここで、友愛数の判定方法について述べる。
23行目の`awk`に入力されるデータは、"<自然数> <真の約数の和>"という形式になっている。
ここで、"<自然数>"を $P$ 、"<真の約数の和>"を $Q$ とする。
$P$ と $Q$ が友愛数であると仮定するならば、入力データの中には "$P\ \ Q$"という行と"$Q\ \ P$"という行が存在することになる。
つまり、"$P\ \ Q$"という入力行に対して、"$Q\ \ P$"という出力も追記してやり、後に入力行全体に対して重複行が存在するかどうかを調べれば、友愛数の組み合わせを抽出できる。

上記の判定処理は、23~27行目の`awk`、`sort`、`uniq`を用いておこなう。
まず、23行目の`awk`を用いて、友愛数の候補となる組み合わせを生成する。
ここでは1フィールド目と2フィールド目の値が同じ場合、友愛数ではない事が自明であるため、その行は除外している。
次に、25行目の`sort`を用いて、入力行を数値順にソートする。
これは、次の27行目の`uniq`において、重複行を識別するための下準備である。
そして、27行目の`uniq`を用いて、重複行(=友愛数)を抽出する。

最後に、友愛数の総和を出力する。
この処理は、29行目の`awk`を用いておこなう。
入力は、"<自然数>  <真の約数の和>"の形式となっており、かつどの行も友愛数の組み合わせとなっている。
そのため、純粋に1フィールド目の"<自然数>"の総和を求めれば良い。
<br>

以上が、10000未満の友愛数の総和を求める方法である。

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

* (特筆すべきことは無い問題だし、妙なテクニックも使っていないので... コメントのしようが無い。)
    - あえてコメントするなら、5~19行目の約数列挙のアルゴリズムが、ちょっと泥臭いかも？

- - -

[^pe]: About - Project Euler ([https://projecteuler.net](https://projecteuler.net))
[^def]: シェル芸の定義 >> シェル芸 - 上田ブログ ([https://blog.ueda.asia/?page_id=1434](https://blog.ueda.asia/?page_id=1434))
[^ans]: 31626