Faktorion

Faktorion, liczba faktorialna – liczba naturalna, która w danym systemie pozycyjnym jest równa sumie silni swoich cyfr^[1].

Faktorion nazywa się:

• trywialnym, jeżeli jest równa ${\displaystyle 1}$ lub ${\displaystyle 2}$,
• nietrywialnym, jeżeli jest inną liczbą faktorialną^[2].

Dla liczby naturalnej ${\displaystyle n}$, podstawy systemu pozycyjnego ${\displaystyle b\in \mathbb {N} _{\geqslant 2}}$ oraz ${\displaystyle d_{k}:={\frac {n{\bmod {b}}^{k+1}-n{\bmod {b}}^{k}}{b^{k}}}}$ definiuje się funkcję ${\displaystyle \operatorname {SFD} _{b}(n):\mathbb {N} \rightarrow \mathbb {N} }$ sumy silni cyfr (ang. sum of the factorials of the digits)^[3]:

${\displaystyle \operatorname {SFD} _{b}(n):=\sum _{k=0}^{\lfloor \log _{b}n\rfloor }d_{k}!=\sum _{k=0}^{\lfloor \log _{b}n\rfloor }({\frac {n{\bmod {b}}^{k+1}-n{\bmod {b}}^{k}}{b^{k}}})!}$ jest wartością ${\displaystyle k}$-tej cyfry liczby.

Liczba naturalna ${\displaystyle n}$ jest liczbą faktorialną w podstawie ${\displaystyle b}$, jeżeli spełnia warunek:

${\displaystyle \operatorname {SFD} _{b}(n)=n}$.

Przykładowo w systemie dziesiętnym:

${\displaystyle 145=1!+4!+5!}$,

dlatego liczba ${\displaystyle 145}$ jest faktorionem.

Faktorion spełnia następujące zależności:

• ${\displaystyle 1}$ oraz ${\displaystyle 2}$ są liczbami faktorialnymi dla każdej podstawy ${\displaystyle b}$,
• dla ustalonej podstawy ${\displaystyle b}$ istnieje skończona liczba liczb faktorialnych,
• iterowanie funkcji ${\displaystyle \operatorname {SFD} _{b}}$ prowadzi do punktu stałego lub cyklu.

Pierwsze nietrywialne liczby faktorialne w systemie dziesiętnym:

${\displaystyle n}$	Rozwinięcie
${\displaystyle 145}$	${\displaystyle 1!+4!+5!}$
${\displaystyle 40585}$	${\displaystyle 4!+0!+5!+8!+5!}$

W informatyce liczba faktorialna jest definiowana względem podstawy systemu pozycyjnego ${\displaystyle b}$. Sprawdzenie, czy liczba jest faktorionem, polega na obliczeniu sumy silni jej cyfr i porównaniu otrzymanego wyniku z liczbą wyjściową.

#include <iostream>
using namespace std;

long long factorial(int n) {
    long long result = 1;

    for (int i = 2; i <= n; i++) {
        result *= i;
    }

    return result;
}

long long sfd(long long number, int base = 10) {
    if (number == 0) return factorial(0);

    long long sum = 0;

    while (number > 0) {
        sum += factorial(number % base);
        number /= base;
    }

    return sum;
}

bool is_factorion(long long number, int base = 10) {
    return sfd(number, base) == number;
}

Algorytm odwzorowuje bezpośrednio definicję funkcji ${\displaystyle \operatorname {SFD} _{b}}$. Polega na wyznaczeniu kolejnych cyfr liczby w systemie o podstawie base, obliczeniu ich silni oraz zsumowaniu otrzymanych wartości. Złożoność obliczeniowa wynosi ${\displaystyle O(k\cdot b)}$, gdzie ${\displaystyle k}$ oznacza liczbę cyfr liczby.