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

概要

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

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

本記事では、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)

問題文

[原文 (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)]

$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$ 未満の友愛数の和を求めよ.

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

解法

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	  # 友愛数の総和の出力

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

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フィールド目の"<自然数>"の総和を求めれば良い。

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

雑記

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

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

---

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

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

3. 31626 ↩