4のベキ乗を用いた数式の作り方

質問

±1,±4,±16,±64,±256を使って答えが1～500となる
数式を作ろうと思っています。

条件として
数式は+のみ

１～500までが答えとなるように
一番短い式と二番目に短い式を出す方法を
考えたいのですが、1番短い式と
2番目に短い式を出すのに何か良い手順はないでしょうか？

宜しくお願いします。

ちょっと例を載せてみます。

答えが1になる数式
最も短い数式　+1
2番目に短い数式　+1+(-1)+1

答えが12になる数式
最も短い数式　+16+(-4)
2番目に短い数式　+4+4+4

答えが160になる数式
最も短い数式　+64+64+16+16
2番目に短い数式　+64+64+16+16+(-1)+1(他にもありますが‥)

回答No.2

rabbit_cat

４進数で表わしたときの２の扱いをもうちょっと考えないといけません。

答えが160になる数式
最も短い数式　+64+64+16+16
は、別解として、256-64-16-16　てのもあります。
２番目に短い数式は、+64+64+16+16+(-1)+1 ではなくて、64+64+64-16-16 です。

例えば、＃１さんの表記で書けば、
168 = 222[4]
だと一番短い表記は、
64+64+16+16+4+4
ではなくて、
256-64-16-4-4
ですね。

回答No.1

yumitsuki

4進法で考えてはいかがでしょうか。

ここで、説明のために、10進法表現では最後に[10]、4進法表現では最後に[4]と書くことにします。

例えば、
1[10]=1[4]
12[10]=30[4]
160[10]=2200[4]
となります。つまり、
1[10]=1×4^0=1[4]
12[10]=3×4^1+0×4^0=1[4]
160[10]=2×4^3+2×4^2+0×4^1+0×4^0=2200[4]
という訳です。

さて、「1番短い式」について考えますと、ローマ数字の記法が参考になります。
4進法表現の各桁について、
・その桁の値が「0」なら、何もしない。ただし、数値全体で「0」であれば、「0[4]」を表記する。
・その桁の値が「1」なら、その桁に対応する4の乗数を1回加算する。
・その桁の値が「2」なら、その桁に対応する4の乗数を2回加算する。
・その桁の値が「3」なら、その桁に対応する4の乗数を1回減算して、さらにその次の桁に対応する4の乗数を1回加算する。

上の例では、
1[10]=1[4]=(4^0)
12[10]=30[4]=(4^2)-(4^1)=(+16)+(-4)
160[10]=2200[4]=(4^3)+(4^3)+(4^2)+(4^2)=(+64)+(+64)+(+32)(+32)
となります。

次に、「2番目に短い式」について考えます。「1番短い式」に1手だけ加える変更が出来れば、それは間違いなく「2番目に短い式」であると言えます。
4進法表現において、
・「2」があれば、その桁に対応する4の乗数を2回減算して、さらにその次の桁に対応する4の乗数を1回加算する。当然ながら、この変更は1回だけ行う。
・「3」があれば、その桁に対応する4の乗数を3回加算する。当然ながら、この変更は1回だけ行う。

上の例では、
12[10]=30[4]=(4^1)+(4^1)+(4^1)=(+4)+(+4)+(+4)
160[10]=2200[4]=(4^3)+(4^3)+(4^3)-(4^2)-(4^2)=(+64)+(+64)+(+64)+(-16)+(-16)
となります。

しかし、4進法表現において、全ての桁が「0」または「1」であった場合は、このように1手だけ加える変更が不可能です。そこで、「1番短い式」に2手だけ加える変更を行うことで「2番目に短い式」とします。加える2手は、同じ数を加算して減算すれば良いので、何でも構いません。

上の例では、
1[10]=(4^1)+(4^1)-(4^1)=(+4)+(+4)+(-4)
となります。

最後の補足です。使用可能な数字の絶対値に上限(±256)があるので、4進法における4桁目の値が「2」であるときは、上で説明した変更が不可能となる場合があります。例えば、
2000[4]=(4^4)+(4^4)
を、
2000[4]=(4^5)-(4^4)-(4^4)
に変更することが出来ないのです(4^5=1024)。
4進法表記において、4桁目の値が「2」で、かつ、それより下の桁に「2」または「3」が無い場合は、上で説明したように2手追加する必要があります。

これでいかがでしょうか。