jusのシェル勉強会4月分

SoftwareDesingの2018年7月号にでていた課題やってみました。

こんなの。

素因数分解したときに23より大きい素因数を持たない自然数を1985個抽出

上記で作成した自然数をファイルaに保存し、この中から4つの数字を選んで掛け算したとき、その値がある自然数の4乗になっている組合せを1つ以上探す。

まず上の方から。
これは簡単。とりえあず1985個みつかるまでfactorで素因数分解していけばいい。「23より大きい素因数を持たない」のところはfactorの結果をgrepで判定する。

#!/bin/bash
i=1
count=0
while [ $count -lt 1985 ]
do
        i=$(expr $i + 1)
        factor $i | awk -F: '{print $2}' | grep -vP '( \d{3,}| 2[3-9]| [3-9]\d)' > /dev/null
        if [ $? == 0 ]; then
                echo $i
                count=$(expr $count + 1)
        fi
done

iを1からインクリメント。でもってfactorで素因分解。factorの出力は以下みたいなものなので、

$ factor 100
100: 2 2 5 5

コロンから後ろをawkで抽出して、grepで23より大きい数字が含まれていないか判定する。

次の課題。4つを選んで掛け算ってことでファイル中から4つランダムに選択して掛け算。
でもって、bcのsqrtに二回かけて、小数点以下が全部0になっていれば、求める数字。ってことで正直に工夫もナシに書いたコードがこちら。

#!/bin/bash
i=1
while [ 1 ]
do
        a=$(expr $(($RANDOM % 1985)) + 1)
        b=$(expr $(($RANDOM % 1985)) + 1)
        c=$(expr $(($RANDOM % 1985)) + 1)
        d=$(expr $(($RANDOM % 1985)) + 1)

        aa=`sed -ne "$a"p ./b`
        bb=`sed -ne "$b"p ./b`
        cc=`sed -ne "$c"p ./b`
        dd=`sed -ne "$d"p ./b`

        number=$(expr $aa \* $bb \* $cc \* $dd)
        echo "sqrt(sqrt($number))" | bc -l | grep '.00000000000000000000'
        if [ $? == 0 ]; then
                echo $aa,$bb,$cc,$dd
                exit
        fi
done

1985で割ったあまりに1を足せば1〜1985までのランダムな数字がでる。
sedで該当行の数字をとりだして、すべてかけ合わせる。
でもって、sqrtに二度かけして、結果を0いっぱいでgrep。マッチしたらそれでOK。
ですが、これとっても遅い。そりゃそうで、一旦乗算した数字を再度sqrtしてるんですから計算量すごいことになってる。
1985個から4つ選ぶって組合せは644,937,012,560もあるので、そりゃ時間かかる。

ランダムに選ぶところはいいとして、判定するところをなんとかしたい。
数学的に考えると、任意の自然数の4乗になっているってことは、素因数分解したときに任意の整数が4の倍数だったらいいってこと。
例えば上記の解の一つとして 19773,2662,858,3072 という組みあせがありますが、これは
3の4乗、2の12乗、11の4乗、13の4乗に素因数分解できます。

そういう観点で作り直したのがこちら。

#!/bin/bash
i=1
while [ 1 ]
do
        a=$(expr $(($RANDOM % 1985)) + 1)
        b=$(expr $(($RANDOM % 1985)) + 1)
        c=$(expr $(($RANDOM % 1985)) + 1)
        d=$(expr $(($RANDOM % 1985)) + 1)

        aa=`sed -ne "$a"p ./b`
        bb=`sed -ne "$b"p ./b`
        cc=`sed -ne "$c"p ./b`
        dd=`sed -ne "$d"p ./b`

        lc1=$(factor $aa $bb $cc $dd | awk -F: '{print $2}' | sed -e 's/ /\n/g' | sed -e '/^$/d' | sort | uniq -c | grep -P '^\W+(4|8|12|16)' | wc -l)
        lc2=$(factor $aa $bb $cc $dd | awk -F: '{print $2}' | sed -e 's/ /\n/g' | sed -e '/^$/d' | sort | uniq -c | wc -l)
        if [ $lc1 ==  $lc2 ]; then
                echo $aa,$bb,$cc,$dd
                exit
        fi

done

選択した数字をすべて素因数分解した上で、それぞれの素因数を1行1文字に。sort uniq -c すると素因数の数を数えられます。
44,2662,18816,5292の場合、こんな出力。

$ factor 44 2662 18816 5292 |  awk -F: '{print $2}' | sed -e 's/ /\n/g' | sed -e '/^$/d' | sort | uniq -c
      4 11
     12 2
      4 3
      4 7

でてくる数字部分を4の倍数でgrepした場合と行数が同じならば、それは自然数の4乗。
うーん、速度的にはそれほど変わらないような。組合せを減らす方向か、素因数分解した数を選択する方向かなんだろうなぁ。