画像っぽい素数をシェル芸でつくる


[画像っぽい素数をつくる](https://qiita.com/sage-git/items/274fcfd515082ffa1ee2)という記事を見て、面白かったのでシェル芸でできないかためしてみました。
やってみると楽しかったです。ただ…数学詳しくないので無駄な計算が多い気がします。。。

## 求めたい数字

[画像っぽい素数をつくる](https://qiita.com/sage-git/items/274fcfd515082ffa1ee2)の記事にありますが、良い感じの場所で折り返すと、画像になる素数です。

```text
700000000000000007000000222222000000000022222222220000000222000002222000000000000022220000000000000222200000000000002222000000000000222200000000000022220000000000000222222222222000000222222222222000700000000000000003
```
![prime_out.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/155890/1784320e-23e0-eb36-7169-efb7bb1bb510.png)

わかりやいように色をつけてみました。

こういう任意の画像に対して存在するはずの素数を求めるワンライナーを作ります。

## 画像のリサイズ 

[ImageMagick](https://imagemagick.org/)のconvertコマンドを使います。
また変換後に使いやすいppm形式に変換します。

```bash
$ cat example.jpg | convert - -resize 67x37! -depth 1 -compress none ppm:-
P3
67 37
255
189 222 251 191 222 250 193 226 249 ……
226 241 239 228 212 255 253 251 250 ……
……
```
一応説明すると-compress noneのオプションを指定したppm形式はテキストとして扱いやすい形になるので、ワンライナーで遊ぶときに楽になります。

詳しく知りたい方はPNMについて調べると良いかもしれません。
https://ja.wikipedia.org/wiki/PNM_(画像フォーマット)

## 画像の減色
[画像っぽい素数をつくる](https://qiita.com/sage-git/items/274fcfd515082ffa1ee2)の記事では[k-means](https://ja.wikipedia.org/wiki/K%E5%B9%B3%E5%9D%87%E6%B3%95)を利用していましたが、それをやってくれるコマンドも見つからずPythonのワンライナーも得意ではないので、3bitのカラーに変換することで強引に解決します。

```bash
$ cat example.jpg | convert - -resize 67x37! -depth 1 -compress none ppm:-
P
P3
67 37
255
255 255 255 255 255 255 255 255 ……
255 255 255 255 255 255 255 255 ……
……
```
また、このままでは扱いにくいので0~7の各画素値を数字に割り当てます。

```bash
$ cat example.jpg | convert - -resize 67x37! -depth 1 -compress none ppm:- | sed '1,3d;s/255/1/g'|tr -d ' \n'|sed -r 's/.../ibase=2;&\n/g'|bc|tr -d '\n'
77777777777777777777………
```
ここまで来るとターミナルで表示できるようになるので表示させます。
また、ターミナルの3bitで表せるエスケープ文字色は、画像RGBとRとBの割当が逆？のようなので少し修正して表示してみます。

```bash
$ cat example.jpg | convert - -resize 67x37! -depth 1 -equalize -compress none ppm:- | sed '1,3d;s/255/1/g'|tr -d ' \n'|sed -r 's/(.)(.)(.)/ibase=2;\3\2\1\n/g'|bc|tr -d '\n'|awk -F '' '{for(i=1;i<=NF;i++){printf (($i!=7)*7)$i}}'|sed -r 's/(.)(.)/\\e[3\1;4\2m\2\\e[0m/g'|sed -r "s/.{$((67 * 15))}/echo -e '&'\n/g"|bash

## 長すぎるので改行いれます……
$ cat example.jpg |\
 convert - -resize 67x37! -depth 1 -equalize -compress none ppm:- |\
 sed '1,3d;s/255/1/g'|\
 tr -d ' \n'|\
 sed -r 's/(.)(.)(.)/ibase=2;\3\2\1\n/g'|bc|tr -d '\n'|\
 awk -F '' '{for(i=1;i<=NF;i++){printf (($i!=7)*7)$i}}'|\
 sed -r 's/(.)(.)/\\e[3\1;4\2m\2\\e[0m/g'|\
 sed -r "s/.{$((67 * 15))}/echo -e '&'\n/g"|\
 bash
```

![example_out.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/155890/8dfc3fbc-348d-a872-7164-cda8ddaad9b8.png)

この数字は2で終わっているので素数では無いですね。
また、k-meansで画像を生成していないため色が良い感じに割り当てられていませんね。

なるほど…そのためにk-meansを利用するのですか。
実装してみると学びがありますね。


## 素数を求める

あとは、openssl primeを利用して求めるだけですね。

```bash
$ seq 99999|egrep '.{5}' | sed -rf<(seq 0 9|sed 's@.@/&.*&/d@')|sed 's@.*@y/01237/&/@'|N=$(cat example.jpg | convert - -resize 67x37! -depth 1 -compress none ppm:- | sed '1,3d;s/255/1/g'|tr -d ' \n'|sed -r 's/(.)(.)(.)/ibase=2;\3\2\1\n/g'|bc|tr -d '\n') xargs -L1 -I_ bash -c 'echo -n "$N ";openssl prime $(echo $N|sed "_")' 2>/dev/null|grep 'is prime'|head -1|sed 's/ .*(/ /;s/).*//'|awk -F '' '{a=(NF-1)/2;for(i=1;i<=a;i++){printf (($i!=7)*7)$i$(i+a+1)}}'|sed -r 's/(.)(.)(.)/\\e[3\1;4\2m\3\\e[0m/g'|sed -r "s/.{$((67 * 15))}/echo -e '&'\n/g"|bash

## 長すぎるので改行いれます
$ seq 99999|egrep '.{5}' | sed -rf<(seq 0 9|sed 's@.@/&.*&/d@')|\
 sed 's@.*@y/01237/&/@'|\
 N=$(cat example.jpg | convert - -resize 67x37! -depth 1 -compress none ppm:- |\
    sed '1,3d;s/255/1/g'|tr -d ' \n'|sed -r 's/(.)(.)(.)/ibase=2;\3\2\1\n/g'|bc|tr -d '\n') \
 xargs -L1 -I_ bash -c 'echo -n "$N ";openssl prime $(echo $N|sed "_")' 2>/dev/null|\
 grep 'is prime'|head -1|\
 sed 's/ .*(/ /;s/).*//'|\
 awk -F '' '{a=(NF-1)/2;for(i=1;i<=a;i++){printf (($i!=7)*7)$i$(i+a+1)}}'|
 sed -r 's/(.)(.)(.)/\\e[3\1;4\2m\3\\e[0m/g'|\
 sed -r "s/.{$((67 * 15))}/echo -e '&'\n/g"|\
 bash
```

~~……と思ったのですが未だにこの画像の素数は見つかってないです。~~
~~画像のサイズを変更し桁数を変えるワンライナーで求めているのですがCPUが熱くなるばかりで素数はみつからないです。。。誰か任意の桁数における素数がどれくらいあるか教えてください[^1]~~

何時間かCPU回していたら発見できました！

```text
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777771777117777777777777777777777777777777777777777777777777777777771488784887777777777777777777777777777777777777777777777777777777187788477887777777777777777777777777777777777777777777777777777777777777777177777777777777777777777777777777777777777777777777771177777777777771777777777777777777777777777777777777777777777777711177777777717777777777777177777777777777777777777777777777777177711177777777117777711177777177771777777777777777777777777777711777711117777711777777111111771171111777777777777777777777777771177777771411111177777771111111111111117777777777777777777777771111777774881411111448877777111111111111117777777777777777777711711114777778877111177788877771411111111111117777777777777777777111111177778814777177774148777714411411111111177777777777777777711171111777774147777777711177777117714111111111177777777777777777111111144777777777777777777777777771441111144111777777777777777777111111144777777777777777777777114444411114441417777711777777777771441111444177777777777777777144444441111444114177777771117777777111444114444411777777777771144411444111144484411111777777777777777717777777711144111777771441117774444111777777777771777777188177187777777771111111111441111111777777777777777711111111178888888888888888888881777777771177777777777777771111111111111111144444488888888888487777777777777777777777777711111111111111111111111711111118888888177777777777777777777777777711111111111111111111111111111111111117777777777777777777777777777711111111111111111111111111111111111777777777777777777777777777777111111111111111111111111111111111117777777777777777777777777777777771111221111111111111111111111117777777777777777777777777777777777712222222222211111111111111111177777777777777777777777777777777777121111112221221
```

![prime_serval.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/155890/31f1cf64-e0d6-5005-554b-3068623981e9.png)

サーバル素数！素晴らしい素数ですね！

きちんと求められていますね。。。
…結構適当にコード書いていたため駄が多く、気が向いた方は良いコードを教えていただけると幸いです。

## まとめとか

半日がかりになってしまいましたが、結構たのしかったです。
~~わーい！たーのし!ー~~

素数を求める部分ではなくてターミナルに3bitカラーの画像を表示する部分とかが難しかったので、だれかの参考になれば嬉しいです。

##追記: quantizeオプションで素数を探す

@sage-gitさんにImageMagickのquantizeオプションで減色すると良さそうとのことでためしてみました。
全体的にコードを書き換えます。

```bash
$ seq 99999999|egrep '.{8}'|sed -rf<(seq 0 9|sed 's@.@/&.*&/d@')|sed 's@.*@y/12345678/&/@'|N=$(cat example.jpg | convert - -resize 30x15! +dither -colors 8 -compress none ppm:-| sed -r '1,3d;s/([^ ]+ ){3}/&\n/g'|awk 'NF>0{if(!h[$0]){i=i+1;h[$0]=i;};print $0""h[$0]}') xargs -L1 -I@ bash -c 'M=$(echo $N|tr " " "\n"|awk "NR%4==0{printf \$0}"|sed '@');echo $(openssl prime $M) $M $N' 2>/dev/null|sed 's/.*is/is/'|grep 'is prime'|head -1|awk '{for(i=1;i<=length($3);i++){print $(i*4),$(i*4+1),$(i*4+2),substr($3,i,1)}}'|awk '{printf "\e[3"($1+$2+$3<255)*7";48;2;"$1";"$2";"$3"m"$4"\e[0m"}NR%30==0{printf "\n"}'|sed "s/.*/echo -e '&'/"|bash
```

かなり桁数の小さい数ですがサーバル素数を見つけました！

```text
111111111111000011111111111112111111111111000011110111111111111111111110308000110111111111111111110008888800000011111111111111101030000000000000111111111111000033000301330000011111111110033027533882033333301111111110353187230278139333330111222223035100111001103933953222822229539301100110399939998222222228888995303385889538888882777777787800003000012888888888888887778111111111111888888888888858881111112111100038888888888888811011112111101118777777
```

![prime_serval_30x15.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/155890/1256cc13-e3df-3302-6e03-e976c6e8284d.png)

## 追記: 画質の良い大きなサーバル素数

関数を使うためシェル芸ぽくなくなりますが、任意の画像の素数を求めたい場合は下記で求められます。
最後のserval.jpgを書き換えるだけで多分いけます。
xargsで並列化しているので少しは早く見つけられるかもしれません。


```bash
$ prime_img(){ seq 99999999|egrep '.{8}'|sed -rf<(seq 0 9|sed 's@.@/&.*&/d@')|sed 's@.*@y/12345678/&/@'|N=$(cat $2 | convert - -resize $((60+$1))x$((30+$1/2))! +dither -colors 8 -compress none ppm:-| sed -r '1,3d;s/([^ ]+ ){3}/&\n/g'|awk 'NF>0{if(!h[$0]){i=i+1;h[$0]=i;};print $0""h[$0]}') xargs -L1 -I@ bash -c 'M=$(echo $N|tr " " "\n"|awk "NR%4==0{printf \$0}"|sed '@');echo $(openssl prime $M) $M $N' 2>/dev/null|sed 's/.*is/is/'|grep 'is prime'|head -1|awk '{for(i=1;i<=length($3);i++){print $(i*4),$(i*4+1),$(i*4+2),substr($3,i,1)}}'|awk '{printf "\e[3"($1+$2+$3<255)*7";48;2;"$1";"$2";"$3"m"$4"\e[0m"}NR%'$((60+$1))'==0{printf "\n"}'|sed "s/.*/echo -e '&'/"|bash;};export -f prime_img;seq 10|xargs -L1 -P10 -i bash -c 'prime_img {} serval.jpg'
```

背景のない白抜きの画像で見つけてみました。

```text
11111111111111111001111110222222221110000002111111111111111111111111111111111111100111111022223222111110000201111111111111111111111111111111111112011111102222322211111100002111111111111111111111111111111111111200111110222232220111111000211111111111111111111111111111111111120011110222322223200111100021111111111111111111111111111111111110000002234222332222222000000111111111111111111111111111111111111122222288992989922222222223211111111111111111111111111111111111102222269239982399222222222322201111111111111111111111111111111000022324222222222422222222222222201111111111111111111111111111000022264222222222222442242222223222201111111111111111111111111020002024442022022224222222220222242222211111111111111111111111122222423366602210222663002246222222422222111111111111111111111102222464323468422222462000026864442242244421111111111111111111102222463340023486422463320003666646424444444011111111111111111112324468403239996886668399930223886644444444441111111111111111111242466882030399306883103999300268864664446444211111111111111111042246663321996830043019868912008884686444666441111111111111111126422688330138480000001384831003862388644468646011111111111111113864446883000030000000000300000323488864468886601111111111111111268644468820000000000000000000344888864646886681111111111111111106888644888420000033330000023688888886668883683111111111111111111386346688888643220000023386888008886688840183111111111111111111113011111103648844433334688440110888643011110111111111111111111111111111111136446446884464444011001111111111111111111111111111111111111111002001030363302000232000111111111111111111111111111111111111111001001100000300001100200021111111111111111111111111111111111111011101100000030000001030000211111111111111111111111111111111111001100110000003000000003000000111111111111111111111111111111111101113010000000300000000330002301111111111111111111111111111111023201300000000030000000003222200021111111111111111111111111111100002230000000003000000000300111112111111111111111111111111111100111110000000000300000000000111111211111111111111
```

![serval_white_prime.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/155890/ad0e7f4b-0f66-95de-5eba-c5d3156c4e64.jpeg)


素晴らしいサーバル素数ですね！






[^1]: [リーマン予想](https://ja.wikipedia.org/wiki/リーマン予想) を証明したら分かる気がしますが…どうなんでしょう？数学の方面には明るくなくて……