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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/677b28ea-9d61-4206-4043-e8a6e415879f.png)

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

# 総当たり

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

```python
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))
```

　出力。

```python
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$とします。

```python
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))
```

　出力。

```python
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$$

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

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

　解きます。


```math
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
c
\begin{pmatrix}
c & -1 \\
1 & -1
\end{pmatrix}^{-1}
\times
\begin{pmatrix}
d! \\
d
\end{pmatrix}
```
```math
\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}
```
```math
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
\frac{c}{1-c}
\begin{pmatrix}
-d! + d \\
-d! + cd
\end{pmatrix}
```
```math
\begin{pmatrix}
a \\
b
\end{pmatrix}
=
\frac{c}{c-1}
\begin{pmatrix}
d!-d \\
d!-cd
\end{pmatrix}
```
```math
\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$が無数に存在することが示せました。

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

```python
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))
```

　出力

```python
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\\}$$

```python
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$を返すので高速で計算できます。しかしそれ以外の数については確実に整数になるとは言えないので、この一般化は更に一歩上の考察が必要になりそうです。