阶乘的最小非零数字

Question

我将尝试计算阶乘中最不显著的非零数字。

---

我有以下代码片段：

$(document).ready(function() {
  $('#submit').click(function() {
    var n = $('#number').val();
    get_result(n);
  });
});

function get_result(n) {
  var factorial = 1;
  var factorial2 = 1;
  for (i = 1; i <= n; i++) {
    factorial = factorial * i;
  }
  var count_5 = 0;
  for (j = 1; j <= n; j++) {
    if (j % 5 != 0) {
      factorial2 = factorial2 * (j % 10);
      factorial2 = factorial2 % 10;
    } else if (j % 5 == 0) {
      count_5 = 1;
    }
  }
  if (count_5 == 1) {
    factorial2 = factorial2 * 5;
  }
  console.log(factorial2);
  factorial2 = factorial2.toString();
  var digit = 0;
  for (i = 0; i < factorial2.length; i++) {
    if (factorial2[i] != '0') {
      digit = factorial2[i];
    }
  }
  $('#display').text("Factorial of " + n + " is " + factorial);
  $('#display2').text("Least significant digit of Factorial of " + n + " is " + digit);
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="display">

</div>
<div id="display2">

</div>
<input type="text" value="" id="number">
<input type="submit" id="submit">

作为上述代码的一部分，为了计算最不重要的非零数字，我首先忽略所有5的倍数，其次，在阶乘计算的每个步骤中，我从10中取余数来保留计算过程中每个步骤的非零数字。最后，我将factorial2的最终值乘以5，然后将其转换为字符串并查找字符串中最后一次出现的非零数字。

上述代码似乎对n = 1,2 ... ... 8的值运行良好。但是在n = 9时，该代码返回的最少重要的非零数字为3，而应该返回8。

例如：Factorial(9) = 362880，因此最不重要的非零数字= 8。

错误可能是什么，我应该如何进行更正？还有没有另一种更有效的方法来计算这个结果？

注意：我只是为了验证目的而包含计算阶乘的代码，我的最终目标是计算最不重要的非零数字，并且当n为十亿（实际计算和读取阶乘不可行或不可取）的最坏情况时。

- stark

---

忽略5的倍数的原因是什么？是否有数学上的原因，导致5的倍数表现出奇怪的行为？ - Marc

这里有一个小代码片段，其中有很多数字都能够正确处理。但是在某些数字上它会出错，具体来说是在15、24和35这几个数字上（我进行了1到40的测试）。也许你知道为什么这些数字会出问题的原因（链接中有相关解释）。在代码里，我尝试使用了一种丑陋的方法来解决这些问题。链接：https://jsfiddle.net/cwsoejLr/ - Marc

@Marc 我忽略5的倍数是因为它们是阶乘中导致零的因子，但由于我只想要非零的有效数字，所以我可以忽略5的倍数，从而减少问题所需的计算量。 - stark

你可以尝试理解这篇文章：http://www.mathpages.com/home/kmath489.htm - Marc

Answer 1

问题在于数字5不会消失，它们会与数字2结合形成数字0。因此，在数字5的倍数（如15或35）或具有许多2次幂的数字（如24）后，您将遇到问题。最好的方法可能是计算2的数量，并对每个5的倍数减少该数量（总是有比5更多的2）。 （另外，一旦您费力地找到了没有0的数字，就不需要将其转换为字符串。）

$(document).ready(function() {
  $('#submit').click(function() {
    var n = $('#number').val();
    get_result(n);
  });
});

function get_result(n) {
  var factorial = 1;
  var factorial2 = 1;
  for ( var i = 1; i <= n; i++ ) {
    factorial = factorial * i;
  }
  var extra2s = 0;
  for ( var j = 1; j <= n; j++ ) {
    var jcopy = j;
    while( jcopy%10 == 0 ) {
      jcopy /= 10;
    }
    while( jcopy%2==0 ) {
      extra2s++;
      jcopy /= 2;
    }
    while( jcopy%5==0 ) {
      extra2s--;
      jcopy /= 5;
    }
    jcopy %= 10;
    factorial2 = (factorial2 * jcopy)%10;
  }
  for ( var k = 0 ; k < extra2s ; k++ ) {
    factorial2 = (factorial2 * 2)%10;
  }
  var digit = factorial2;
  $('#display').text("Factorial of " + n + " is " + factorial);
  $('#display2').text("Least significant digit of Factorial of " + n + " is " + digit);
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="display">

</div>
<div id="display2">

</div>
<input type="text" value="" id="number">
<input type="submit" id="submit">

- Teepeemm