Niveau énigmes

Dernier chiffre non nul

Posté par
Vassillia 12-11-23 à 22:19

Bonjour tout le monde,

Le produit $n!=n(n-1)(n-2)...1$ se termine par plein de zéros mais juste avant quel est le dernier chiffre non nul ?
1) Pour $10!$
2) Pour $100!$
3) Pour $2023!$
Et plus si affinités...

Posté par re : Dernier chiffre non nul 13-11-23 à 11:26

Le calculer avec un programme est extrèmement simple pour de petits n comme 2023.
Mais je suppose que ça ce complique pour de grand n.
Il y a des programmes sur l'oeis:

Voici ma proposition:

On peut écrire n! sous la forme: $n! = x2^a5^b$ , la réponse cherchée est $(x2 ^{a-b})\mod10$ .

On peut donc garder en mémoire et updater $x \mod 10$ et $a-b$ . On aura un algorithme en O(nlog(n)).
Note: l'algorithme python proposé sur l'oeis est en O(log(n)).

def get_last_non_zero(n):
    x, c = 1, 0
    for i in range(2, n + 1):
        a, b = 0, 0
        while i % 2 == 0:
            a += 1
            i //= 2
        while i % 5 == 0:
            b += 1
            i //= 5
        x = (x * i) % 10
        c += (a - b)
    return (x * pow(2, c, 10)) % 10


if __name__ == "__main__":
    print(get_last_non_zero(10))
    print(get_last_non_zero(100))
    print(get_last_non_zero(2023))

Posté par re : Dernier chiffre non nul 13-11-23 à 12:55

Si tu regardes la séquence des 2^k mod 10, tu verras qu'elle est périodique
k = 1 : 2
k = 2 : 4
k = 3 : 8
k = 4 : 6
k = 5 : 2

Donc $2^k\mod 10 = u[ (k-1)\mod 4 ]$ , où $u = [2,4,8,6]$

Tu peux donc simplifier ton algorithme. Pour calculer a et b, tu peux utiliser la formule de Legendre
$a = E(n/2) + E(n/2^2) + E(n/2^3) + \cdots$
et $b = a = E(n/5) + E(n/5^2) + E(n/5^3) + \cdots$

de façon effectivement logarithmique.
Tu calcules ensuite m = 1 if a == b else u[ (a-b-1)%4] et x%10 et le résultat sera ((x %10)* m)%10.
Pour calculer x%10 sans utiliser de bigint ou de divisions/modulo, tu peux par exemple utiliser un crible d'Eratosthène et faire le produit de toutes les factorisations des entiers <= n en omettant les puissances de 2 et de 5 pour avoir la factorisation de x. Ensuite, tu calcules $3^{a_3}\mod 10$ , $7^{a_7}\mod 10$ , etc en utilsant à nouveau des suites périodiques prédéfinies. Et enfin tu fais le produit de tout ça et de m, modulo 10.
Ceci dit, si tu utilises un crible d'Erathostène, tu peux te passer de la formule de Legendre pour calculer a et b

Posté par re : Dernier chiffre non nul 14-11-23 à 09:42

Oui, oui j'avais vu. Mais comme l'exponentiation rapide est en O(log(n)), ce n'est pas le terme déterminant.

Je ne pense pas que factoriser tous les termes du produit soit plus efficace que n modulo.

On a en O(n):

def get_last_non_zero(n):
    x, c = list(range(n + 1)), 0
    b = 2
    while b <= n:
        c += n // b
        for i in range(b, n + 1, b):
            x[i] //= 2
        b *= 2
    b = 5
    while b <= n:
        c -= n // b
        for i in range(b, n + 1, b):
            x[i] //= 5
        b *= 5
    m = 1 if c == 0 else (6, 2, 4, 8)[c % 4]
    for i in x[3:]:
        m = (m * i) % 10
    return m

Posté par re : Dernier chiffre non nul 14-11-23 à 11:32

Bonjour,

c'est une question qui avait été posée au championnat FFJM il y a trente ans (on le demandait pour 1993!).

Quelques années après j'ai écrit un programme pour ma calculatrice (TI92) qui me donne par exemple en moins de 30s le chiffre 6 pour la factorielle de $10^{200}$ .