階乗基表現
元ネタ: https
1!=1
— 綿谷雫 (@kapt0nH) February 5, 2019
2!=10
3!=100
4!=1000
……
みたいな感じの表記法があるとして、10進法で表すのとこの表記法で表すのが同じになるような数が1以外にあるかな
://twitt
https://twitter.com/kapt0nH/status/1092823926416142336
er.com/kapt0nH/status/1092823926416142336
https://twitter.com/kapt0nH/status/1092823926416142336
問題: 階乗基表現と十進表記が等しくなるような自然数を全て求めよ。
解答:
1が条件を満たすことは自明である。
ある数nに対して十進表記が階乗基表現よりも「長大である」ことを次のように定義する:
(nの十進表記の桁数がnの階乗基表現の桁数より大きい)
または
(
(nの十進表記の桁数がnの階乗基表現の桁数と等しい)
かつ
(ある自然数mが存在して、
(nの十進表記と階乗基表現の上m-1桁が等しい)かつ(nの十進表記の上からm桁目は階乗基表現の上からm桁目より大きい)
)
)
また、階乗基表現が十進表記よりも「長大である」とは、十進表記が階乗基表現よりも長大でないかつ階乗基表現が十進表記と等しくないことである。
1以外の数に対して上限と下限を調べる。
n!~(n+1)!が十進表記でm~m+k桁の範囲を取るとすると、m+k<nであれば、階乗基表現が十進表記よりも長大であるため、この範囲には条件を満たす範囲は存在しない。
また、m>nであれば、十進表記が階乗基表現よりも長大であるため、この範囲には条件を満たす範囲は存在しない。
実際に計算すると、2!以上18!以下および25!以上では条件を満たす数が存在しないことがわかる。
例えば、n=17のとき、17!=355687428096000(15桁), 18!=6402373705728000(16桁)であるから、階乗基表現が長大である。
よって、18!<x<25!の範囲のxを調べればよい。
(a) 18!<x<19!
十進表記が18桁になるためには、10^17/18!>15であることからxは15*18!以上である必要があるが、このとき階乗基表現は最上位桁が16以上になるため、階乗基表現の方が長大である。
(b) 19!<=x<20!
十進表記が19桁になるためには、10^18/19!>8.2であることからxは8*18!以上である必要がある。したがって、十進表記と階乗基表現が一致するためには、十進表記の最上位桁が8である必要があるが、20!=2432902008176640000であるため、条件を満たすxは存在しない。
(c) 20!<=x<21!
十進表記が20桁になるためには、10^19/20!>4.1であることからxは4*19!以上である必要がある。したがって、十進表記と階乗基表現が一致するためには、十進表記の最上位桁が4以上である必要があるが、21!=51090942171709440000であるため、最上位桁が4または5で確定する。
このとき、階乗基表現の最上位が5であることから、4*20!<=x<6*20!である。しかし、
4*20!=9731608032706560000
6*20!=14597412049059840000
より、xの10^19の位を5にすることは出来ない。したがって、条件を満たすxは存在しない。
(d) 21!<=x<22!
十進表記が21桁になるためには、10^20/21!>1.9であることからこの議論では最上位桁を制限することはできない。
(c)と同様の議論により最上位桁を考えると、最上位桁をyとした場合に
y*10^20<=y*19!<(y+1)*10^20
が成り立つ必要がある。
これが成り立つyはy=1のみであるから、xの最上位桁は1となる。
また、2*21!=102181884343418880000であるから、上から2桁目は0で確定する。
しかし、1*21!+1*20!=53523844179886080000<10^20であるから、条件を満たすxは存在しない。
(e)22!<=x<23!
理論だけで計算するのは面倒なのでバックトラッキングを使用したプログラムを書き、全区間の探索を行った。その結果、解が存在しないことがわかった。
(f)23!<=x<24!
4*23!>10^23であるから、xの最上位桁は1,2,3のどれかであるが、2*23!>5*10^22であるため、xの最上位桁は1でなければならない。
しかし、このとき23!>2.5*10^22であるため、条件を満たすxは存在しない。
(g)24!<=x<25!
2*24!>10^24であるから、xの最上位桁は1と定まるが、24!>6*10^23であるため、条件を満たすxは存在しない。
以上より、条件を満たすxはx=1のみであることがわかった。
