How can I know if there exist three consecutive integers $a$, $b$ and $c$ such that $a$.$b$.$c$ = $n$!. I am supposed to write an algorithm for this so using $n$! or trying to find $a,b,c$ do not work.
Asked
Active
Viewed 93 times
3
-
1What about $a=1,b=2,c=3$? – Frank Oct 10 '16 at 13:44
-
@Frank $a = 4, b = 5, c = 6$ and $a = 8, b = 9, c = 10$, also work but a program needs an algorithm to find out if such numbers exist for any n(like $n < 1000$ at least) – David Asryan Oct 10 '16 at 13:51
2 Answers
2
Let $m=\lfloor\sqrt[3]{n!}\rfloor$. Since you are looking for three consecutive integers whose product $(k-1)k(k+1)$ is $n!$, you need only consider $k=m$ and $k=m+1$. That's because you can't have $k-1\gt\sqrt[3]{n!}$ nor $k+1\lt\sqrt[3]{n!}$. (Note, $n!$ is never a perfect cube for $n\gt1$. This easily follows from Bertrand's Postulate, and possibly for other, more elementary reasons.)
For example, $\sqrt[3]{3!}=1.817$, for which $k=2$ works, $\sqrt[3]{4!}=2.884$, for which $k=3$ works, $\sqrt[3]{5!}=4.932$, for which $k=5$ works, $\sqrt[3]{6!}=8.96$, for which $k=9$ works, but $\sqrt[3]{7!}=17.145$, for which neither $k=17$ nor $k=18$ works (because in either case $17$ is a factor of $(k-1)k(k+1)$ but not a factor of $7!$).
Barry Cipra
- 79,832
-
Thank you, I would love to find a solution which does not include counting the factorial but I think it may be impossible. – David Asryan Oct 10 '16 at 15:35
-
@DavidAsryan, you're welcome. By "counting" do you mean computing the factorial? I agree it'd be nice to avoid doing so, but it seems unlikely, unless there's a theorem saying, for instance, that $m$ (which is necessarily one of the three consecutive numbers) always has a prime factor greater than $n$ for $n\ge7$. – Barry Cipra Oct 10 '16 at 15:49
-
An amusing update on my previous comment: Playing around with small examples, I just found that when $n=15$, $m=10395=3^7\cdot5$... (but $m+1$ and $m-1$ both have prime factors greater than $15$). – Barry Cipra Oct 10 '16 at 15:58
0
Assume that $n!$ is the product of three consective integers: $k-1,k,k+1.$ In such a case, it is $$k^3-k-n!=0.$$
So, you have to check if the equation $x^3-x-n!=0$ has an integer solution $k.$ In such a case $n!=(k-1)k(k+1).$
How to implement this in an algorithm? Well, since $k^3-k=n!<k^3$ it is enough to consider values $k>\sqrt[3]{n!}.$ On the other hand it is
$$k^3-k=n!\implies k^3=n!+k<n!+n\implies k<\sqrt[3]{n!+n}.$$
So, a possible way is to test if for $\sqrt[3]{n!} < k <\sqrt[3]{n!+n}$ it is $k^3-k-n!=0.$
mfl
- 29,399
-
This indeed will be very inefficient for $n$ big. Since the instructions of the program did not give an upper bound of n I am not really sure if this problem has to be solved for big integers or not. In fact, the factorial of 20 already exists 64 bit integer so my question was if it is possible to find a formula or algorithm whcih does not use n!. – David Asryan Oct 10 '16 at 14:12