1
$\begingroup$

I want to find the largest factorial whose decimal representation contains only three distinct digits. I am using the following Python code to compute the above, but no results up to 16000!:

def check(x):
    s=str(x)
    m=0
    if s.count('0')>0:
        m=m+1
    if s.count('1')>0:
        m=m+1
    if s.count('2')>0:
        m=m+1
    if s.count('3')>0:
        m=m+1
    if s.count('4')>0:
        m=m+1
    if s.count('5')>0:
        m=m+1
    if s.count('6')>0:
        m=m+1
    if s.count('7')>0:
        m=m+1
    if s.count('8')>0:
        m=m+1
    if s.count('9')>0:
        m=m+1
    if m==3:
        return True
    else:
        return False
dp=[1,2]
for i in range(3,99999):
    x=dp[i-2]*i
    if check(x)==True:
        print x
    dp.append(x)

Is there a better approach?

$\endgroup$
  • 1
    $\begingroup$ Simply calculating factorial and check number of digits. x=dp[i-2]*i is where factorial is calculated using dynamic programming. $\endgroup$ – n00bcoder123 Jan 23 '15 at 8:54
  • 1
    $\begingroup$ Presumably "composed of only 3 digits" means the decimal representation contains only 3 of the digits 0,1,2,3,4,5,6,7,8,9. $\endgroup$ – Robert Israel Jan 23 '15 at 8:54
  • 2
    $\begingroup$ Thus $5!$, $6!$ and $7!$ qualify. $\endgroup$ – Robert Israel Jan 23 '15 at 8:56
  • 2
    $\begingroup$ It seems that from $n=42!$ onward all $10$ digits occur (I checked up to $n=10000!$). See also A137580 $\endgroup$ – vuur Jan 23 '15 at 10:59
  • 2
    $\begingroup$ This might be one of those questions that is simple to ask but very very difficult to answer. The answer appears to be $7!=5040$. But it is conceivable (although I don't believe it) that there is no such largest factorial. $\endgroup$ – TonyK Mar 11 '15 at 12:44
-1
$\begingroup$

Update:

Here is a table of the first $50$ factorials (in base 10 = decimal representation): link.

Its format is $$ n: (n!)_{10}, l=\mbox{number of places}, di =\mbox{number of diverse digits} $$

As noted by fellow user vuur in the comments, the number of diverse digits of $(n!)_{10}$ is listed in OEIS as A137580. The related sequence of non pandigital numbers (pandigital number = number with all digits of the base occurring) A182049 is conjectured to end with entry $n=41$.

Following is an heuristic argument, why it is likely that for larger $n$ the decimal representation $(n!)_{10}$ is pandigital, and thus not tridigital anymore, as searched for in the question, making 7! candidate for the largest tridigital factorial.

For this we need to look at the development of a fixed place $k$ with increasing $n$, e.g. $k = 3$, counting from the end of the string, first index being a zero.

This place is implicitly zero until $n = 7$, where $(n!)_{10}$ got large enough to reach this place and it takes the digit $d_3 = 5$, then changes its values a couple of times until it will stay $0$ for $n \ge 16$. $$ d_3^{(n)}: 0, 0, 0, 0, 0, 0, 0, 5, 0, 2, 8, 6, 1, 0, 1, 8, 8, 6, 8, 2, 0, 0, 0, \ldots $$ All places will sooner or later stay at the digit $0$ because the number of zeroes at the end of $n!$ grows with increasing $n$, as new factors $n$ introduce new factors $2$ and $5$ to the factorial, the number of trailing zeroes of $(n!_{10})$ corresponding to the power $j$ in $5^j$ of the prime factorization of $n!$.

The place $k = 3$ has a run of $r_3 = 13$ variable digits until it gets flooded by the trailing zeroes. As the length of $(n!)_{10}$ seems to grow faster than the number of trailing zeroes, those runs $r_k$ should get longer for places with increasing $k$.

The digits change with increasing $n$ from $d_k^{(n)}$ to $d_k^{(n+1)}$ according to the multiplication with carry algorithm is: \begin{align} d_0^{(n+1)} &= (n+1) \cdot d_0^{(n)} \mod 10 \\ d_k^{(n+1)} &= \left((n+1)\cdot d_k^{(n)} + c_k^{(n)}\right) \mod 10 \\ c_0^{(n)} &= 0 \\ c_{k+1}^{(n)} &= \left((n+1) \cdot d_k^{(n)} + c_k^{(n)}\right) - 10 \cdot d_k^{(n+1)} \end{align} The above recursion scheme is similar to the one used in linear congruential pseudo random number generators or MWC generators.

The quality of the random numbers regarding their cycle length (they go into a cycle after length iterations) or the distribution of their generated numbers varies with the choice of the parameters and initial value.

My heuristic argument is, that the digits $d_k^{(n)}$ of $(n!)_{10}$ behave similar like those pseudo random number generators and the longer the $(n!)_{10}$ string gets with increasing $n$, the more of those generators get introduced and start generating until caught by the flood of trailing zeroes. Nonetheless their number increases with increasing $n$ and they vary with parameters and initial values. So they produce all base digits, turning $(n!)_{10}$ pandigital. It would be highly unlikely that all those generators are such synched for a certain $n^*$ that they stick just to $3$ digits out of the $10$ possible.

My guess is that if one would apply the statistical tools of the analysis of pseudorandom number generators to the digits evolution of $(n!)_{10}$ one could show or at least better argue for this argument.

$\endgroup$
  • $\begingroup$ You just formalised the question. :/ $\endgroup$ – n00bcoder123 Jan 23 '15 at 10:34
  • $\begingroup$ Exactly. I move it to the comment section. Can't remember if I wanted to exetend it to an answer. $\endgroup$ – mvw Mar 11 '15 at 11:43
  • $\begingroup$ OK, I have updated it into an argument. $\endgroup$ – mvw Mar 11 '15 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.