8
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

40-32/2=4! みたいなやつ

Last updated at Posted at 2020-06-04

 10年ぐらい前にも見た気がしますが……。

image.png

 これを題意として検証していきましょう。

総当たり

 まずは脳死で総当たりします。以下のようなループを組むことになります。

from math import factorial

for a in range(1,100):
    for b in range(1,a):
        for c in range(1,100):
            if (a-b)%c != 0:
                continue
            d = int((a-b)/c)
            if a - b/c == factorial(d):
                print("{}-{}/{}={}!".format(a,b,c,d))

 出力。

2-1/1=1!
3-1/1=2!
3-2/1=1!
4-2/1=2!
4-3/1=1!
5-3/1=2!
5-4/1=1!
...

 $c=1$のとき、$a-b/c$も$(a-b)/c$も同じ値になります。加えて、$d=1,2$のとき、$d! = d$となるので、任意の$a,b=a-1またはa-2$について題意を満たすことがわかります。……が、これはこのトンチの本意ではないでしょう。

総当たり2

 少し条件を厳しくします。題意をリスペクトして$c \geq 2,d \geq 3$とします。

from math import factorial

for a in range(1,1000):
    for b in range(1,a):
        for c in range(2,1000):
            if (a-b)%c != 0:
                continue
            d = int((a-b)/c)
            if d <= 2:
                continue
            if a - b/c == factorial(d):
                print("{}-{}/{}={}!".format(a,b,c,d))

 出力。

25-5/5=4!
30-18/3=4!
40-32/2=4!
138-108/6=5!
230-220/2=5!
721-103/103=6!
728-416/52=6!
...

 だいぶトンチらしくなってきました。恐らく無限にありそうですが、証明はできていません。ぱっと見、$3!$が答えとなるケースがないのかが気になります。また、計算量も多くなってきたので、もっと短時間で$a,b,c,d$を生成するアルゴリズムが欲しいところです。

#数学的考察

$$a-b/c = d!$$$$(a-b)/c = d$$

 これは以下のような行列にすることができます。

\begin{pmatrix}
c & -1 \\
1 & -1
\end{pmatrix}
\times
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
c
\begin{pmatrix}
d! \\
d
\end{pmatrix}

 解きます。

\begin{pmatrix}
a \\
b
\end{pmatrix}
=
c
\begin{pmatrix}
c & -1 \\
1 & -1
\end{pmatrix}^{-1}
\times
\begin{pmatrix}
d! \\
d
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
c
\cdot
\frac{1}{-c+1}
\begin{pmatrix}
-1 & 1 \\
-1 & c
\end{pmatrix}
\times
\begin{pmatrix}
d! \\
d
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
\frac{c}{1-c}
\begin{pmatrix}
-d! + d \\
-d! + cd
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
\frac{c}{c-1}
\begin{pmatrix}
d!-d \\
d!-cd
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
\frac{cd}{c-1}
\begin{pmatrix}
(d-1)!-1 \\
(d-1)!-c
\end{pmatrix}

 これらのうち、$a,b$が整数となるような$c,d$の組み合わせが題意の条件となります。

#d=3のとき

 $d=3$のときを考えてみましょう。このとき条件は、$$a = \frac{3c}{c-1}$$$$b = \frac{3c}{c-1}(2!-c)$$ となりますが、$c \geq 2$より、$b$が正の整数にはなりえないことがわかります。よって$d=3$が題意を満たす可能性はありません。

#簡易な一般解

 ある$d$に対して$\frac{cd}{c-1}$が整数であってほしい時、少なくとも$c=d+1$はそれを満たすことがわかります。なのでcを固定した場合、条件は、$$a = (d+1) \Bigl\{(d-1)!-1\Bigr\}$$$$b = (d+1) \Bigl\{ (d-1)!-d-1\Bigr\}$$ となります。

 dは4以上の任意の整数をとることができるので、これで題意を満たす$a,b,c,d$が無数に存在することが示せました。

 ついでにプログラムで列挙していきましょう。

from math import factorial

for d in range(4,100):
    c = d+1
    a = c*(factorial(d-1)-1)
    b = c*(factorial(d-1)-c)
    print("{}-{}/{}={}!".format(a,b,c,d))

 出力

25-5/5=4!
138-108/6=5!
833-791/7=6!
5752-5696/8=7!
45351-45279/9=8!
403190-403100/10=9!
3991669-3991559/11=10!
43545588-43545456/12=11!
518918387-518918231/13=12!
6706022386-6706022204/14=13!
93405311985-93405311775/15=14!
1394852659184-1394852658944/16=15!
22230464255983-22230464255711/17=16!
376610217983982-376610217983676/18=17!
6758061133823981-6758061133823639/19=18!
128047474114559980-128047474114559600/20=19!
2554547108585471979-2554547108585471559/21=20!
...

 計算量も$O(n^3)$から$O(n)$になり、高速に生成できるようになりました。めでたしめでたし。

#簡易な一般解2

 $c=2$も、同様に常に$\frac{cd}{c-1}$が整数となります。$$a = 2d \Bigl\{(d-1)!-1\Bigr\}$$$$b = 2d \Bigl\{ (d-1)!-2\Bigr\}$$

40-32/2=4!
230-220/2=5!
1428-1416/2=6!
10066-10052/2=7!
80624-80608/2=8!
725742-725724/2=9!
7257580-7257560/2=10!
...

#より一般的な解は不明

 ある$d$について、$c$は下限は2、上限は$(d-1)!-1$になります。($c=(d-1)!$のとき$b=0$になり、これがcを上げられるぎりぎり。実際には$b=0$を不適としているので、$(d-1)-1$まで調べればよい)

 この中で$c=2またはd+1$はいかなる$d$についても整数$a,b$を返すので高速で計算できます。しかしそれ以外の数については確実に整数になるとは言えないので、この一般化は更に一歩上の考察が必要になりそうです。

8
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?