[PYTHON] Something like 40-32 / 2 = 4!

I think I saw it about 10 years ago ...

Let's examine this as the subject.

Brute force

First of all, brute force with brain death. The following loop will be formed.

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

output.

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!
...

When $ c = 1 $, both $ a-b / c $ and $ (a-b) / c $ have the same value. In addition, when $ d = 1,2 $, then $ d! = D $, so we know that we meet the subject for any $ a, b = a-1 or a-2 $. …… But this is not the intention of this Tonchi.

Brute force 2

Make the conditions a little stricter. Respect the subject and make it $ 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))

output.

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!
...

It's becoming more like Tonchi. Probably infinite, but not proven. At first glance, I'm wondering if there are any cases where ** $ 3! $ Is the answer **. Also, since the amount of calculation has increased, I would like an algorithm that generates $ a, b, c, d $ in a shorter time.

Mathematical consideration

This can be a matrix like this:

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

I will solve it.

\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}

Of these, the condition of the subject is a combination of $ c and d $ such that $ a and b $ are integers.

When d = 3

Consider the case of $ d = 3 . At this time, the condition is $ a = \ frac {3c} {c-1} $ $ b = \ frac {3c} {c-1} (2! -c) $, but $ c \ From geq 2 $, we can see that $ b $ cannot be a positive integer. Therefore, $ d = 3 $ is unlikely to satisfy the subject.

Simple general solution

When you want $ \ frac {cd} {c-1} $ to be an integer for a $ d $, you know that at least $ c = d + 1 $ fills it. So if you fix c, the condition is $ a = (d + 1) \ Bigl \\ {(d-1)! -1 \ Bigr \\} $ $ b = (d + 1) \ Bigl \\ {(d-1)! -D-1 \ Bigr \\} $.

Since d can take any integer greater than or equal to 4, we have shown that there are innumerable $ a, b, c, d $ that satisfy the subject.

By the way, let's enumerate them programmatically.

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

output

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!
...

The amount of calculation has also changed from $ O (n ^ 3) $ to $ O (n) $, and it can be generated at high speed. I'm happy.

Simple general solution 2

Similarly for $ c = 2 $, $ \ frac {cd} {c-1} $ is always an integer. $ 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!
...

More general solution unknown

For a $ d $, $ c $ has a lower limit of 2 and an upper limit of $ (d-1)! -1 $. (When $ c = (d-1)! $, $ B = 0 $, which is just before c can be raised. Actually, $ b = 0 $ is unsuitable, so $ (d-1) -1 You can look up to $)

Of these, $ c = 2 or d + 1 $ returns integers $ a, b $ for any $ d $, so it can be calculated at high speed. However, other numbers cannot be said to be integers, so this generalization is likely to require further consideration.