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

概要

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

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

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

実行環境

• Arch Linux (x86_64, 4.3.3-3-ARCH)
• bash (4.3.42)
• GNU coreutils (8.24)
• gawk (4.1.3)

問題文

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

Non-abundant sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of $28$ would be $1 + 2 + 4 + 7 + 14 = 28$ , which means that $28$ is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As $12$ is the smallest abundant number, $1 + 2 + 3 + 4 + 6 = 16$ , the smallest number that can be written as the sum of two abundant numbers is $24$ . By mathematical analysis, it can be shown that all integers greater than $28123$ can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

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

非過剰数和

完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, $28$ の真の約数の和は, $1 + 2 + 4 + 7 + 14 = 28$ であるので, $28$ は完全数である.
真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ.
$12$ は, $1 + 2 + 3 + 4 + 6 = 16$ となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上限よりも小さいことは分かっているのだが, この上限を減らすことが出来ていない.
2つの過剰数の和で書き表せない正の整数の総和を求めよ.

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

解法

1   #!/bin/bash
2   
3   seq 1 28122 \
4   | # 1~28122の整数の生成
5   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"}' \
6   | # 各数値における約数の列挙
7   awk '{s=0; for(i=2; i<=NF; i++){s+=$i}; print $1, s}' \
8   | # 各数値における約数の総和の算出
9   awk '$1 < $2 && $0=$1' \
10  | # 過剰数の抽出
11  awk '{arr[NR]=$0} END {for(i=1; i<=NR; i++){for(j=i; j<=NR; j++){n=arr[i]+arr[j]; print (n <= 28122) ? n : ""}}}' \
12  | # 2つの過剰数の和の組合せの列挙
13  sort -n \
14  | # 組合せを数値順にソート
15  uniq \
16  | # 重複した組合せの除去
17  diff - <(seq 1 28122) \
18  | # 2つの過剰数の和で表せない数値の列挙
19  sed -n 's/> //p' \
20  | # 出力の整形
21  awk '{s+=$0} END {print s}'
22    # 総和の出力

以下、コマンドライン上での実行用コードである。
下記コードは、bashもしくはzshでしか動作しない点に留意すること。

seq 1 28122 | 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 '{s=0; for(i=2; i<=NF; i++){s+=$i}; print $1, s}' | awk '$1 < $2 && $0=$1' | awk '{arr[NR]=$0} END {for(i=1; i<=NR; i++){for(j=i; j<=NR; j++){n=arr[i]+arr[j]; print (n <= 28122) ? n : ""}}}' | sort -n | uniq | diff - <(seq 1 28122) | sed -n 's/> //p' | awk '{s+=$0} END {print s}'

解説

該当する範囲にある過剰数について、それらの中から2つの数値の和を全て列挙し、整数全体から過剰数の和で表せない整数を求めていく。

まず、1から28122の整数を出力する。
これは、問題文より、該当する過剰数は1以上28123未満になるためである。
この処理は、3行目のseqを用いておこなう。

次に、各数値について、過剰数のみを抽出する。
この処理は、5~9行目のawkを用いておこなう。
5行目のawkで、過剰数であるかどうかを判定するために、約数を全て列挙する。
7行目のawkで、約数の総和を求める。
9行目のawkで、過剰数のみを出力する。

そして、抽出した過剰数について、2つの数値の和の組合せを列挙する。
この処理は、11行目のawkを用いておこなう。
具体的には、過剰数を連想配列に格納した後、二重ループを用いて28122以下となる過剰数の和の組合せを出力している。

その後、2つの過剰数の和で表せない数値を列挙する。
この処理は、13~19行目のsort、uniq、diff、sedを用いておこなう。
まず、13~15行目のsortとuniqで、重複している和の組合せを除去する。
次に、17行目のdiffで、1から28122の整数群と比較し、差分を出力する
ここでは、コードを簡潔にするために、bash固有の機能であるプロセス置換を用いている。
そして、19行目のsedで、パイプからの入力のみに含まれる値、2つの過剰数の和で表せない数値を抽出する。

最後に、2つの過剰数の和で表せない数値の総和を求める。
この処理は、21行目のawkを用いておこなう。

以上が、2つの過剰数の和で書き表せない正の整数の総和を求める方法である。

雑記

• 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺

• 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh
  
  

• 今回の解法は、かなり時間がかかる...

  $ cat /proc/cpuinfo | grep 'model name' | uniq
  model name  : AMD FX(tm)-8320 Eight-Core Processor
  $ time seq 1 28122 | 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 '{s=0; for(i=2; i<=NF; i++){s+=$i}; print $1, s}' | awk '$1 < $2 && $0=$1' | awk '{arr[NR]=$0} END {for(i=1; i<=NR; i++){for(j=i; j<=NR; j++){n=arr[i]+arr[j]; print (n <= 28122) ? n : ""}}}' | sort -n | uniq | diff - <(seq 1 28122) | sed -n 's/> //p' | awk '{s+=$0} END {print s}'
  4179871
  seq 1 28122  0.00s user 0.00s system 0% cpu 0.415 total
  awk   0.81s user 0.01s system 99% cpu 0.827 total
  awk '{s=0; for(i=2; i<=NF; i++){s+=$i}; print $1, s}'  0.22s user 0.00s system 27% cpu 0.826 total
  awk '$1 < $2 && $0=$1'  0.04s user 0.00s system 5% cpu 0.826 total
  awk   11.41s user 0.05s system 61% cpu 18.655 total
  sort -n  13.88s user 0.31s system 63% cpu 22.491 total
  uniq  1.07s user 0.09s system 5% cpu 22.491 total
  diff - <(seq 1 28122)  0.01s user 0.00s system 0% cpu 22.500 total
  sed -n 's/> //p'  0.00s user 0.00s system 0% cpu 22.498 total
  awk '{s+=$0} END {print s}'  0.00s user 0.00s system 0% cpu 22.498 total
  

  • やっぱりというか何と言うか、11行目の組合せを列挙するawk部分が、すっごく遅い...
  • 他に良い方法は、きっとあるはず。...どなたかお願いしますorz

• ちなみに、2つの過剰数の和で表せない最大の整数は、現在では $20161$ だそう。 >> http://mathworld.wolfram.com/AbundantNumber.html (2016年 1月 31日 日曜日 22:29:04 JST アクセス)

  • なので、初めに生成する数値は、seq 1 20161でOK。
  • といっても、アルゴリズムの計算量が多い問題に対する、根本的な解決にはなっていないのだけれど...

• 今回はbash依存のスクリプト。

  • でも、一時ファイルを使えば、shでも動く汎用シェルスクリプトに書き換えられる。
  • まあ、面倒臭いので、bashのプロセス置換をば。
    
    

• 今回のソースのコメント、"の"が妙に多い気がするの...

  $ echo "2つの過剰数の和の組合せの列挙" | mecab | grep '助詞,連体' | grep -c ''
  4
  

  • 表記を統一しつつ、もうちょっと宜しい表現に書き換えられるようにしたい。
  • 日本語力、というか言語技術、だいじ。

---

---

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

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

3. 4179871 ↩