Project Euler Problem 383
Let f5(n) be the largest integer x for which 5^x divides n.
Solution
Answer: 22173624649806
Let
$$v_5(n!)=\sum_{k\ge1}\left\lfloor \frac{n}{5^k}\right\rfloor$$
denote the exponent of $5$ in $n!$. The problem defines
$$T_5(n)=#\left{1\le i\le n: v_5((2i-1)!)<2v_5(i!) \right}.$$
We need $T_5(10^{18})$.
Key mathematical reduction
By Legendre’s formula,
$$v_5(n!)=\frac{n-s_5(n)}{4},$$
where $s_5(n)$ is the sum of the base-5 digits of $n$.
Thus the condition becomes
$$\frac{2i-1-s_5(2i-1)}{4} < 2\cdot \frac{i-s_5(i)}{4}.$$
Multiplying by 4 and simplifying:
$$2i-1-s_5(2i-1) < 2i-2s_5(i)$$
$$s_5(2i-1)+1>2s_5(i).$$
Now analyze $s_5(2i-1)$.
When doubling $i$ in base 5:
- every carry reduces the digit sum by $4$,
- subtracting 1 from $2i$ changes the digit sum by $-1+4v_5(i)$.
Hence
$$s_5(2i-1) = 2s_5(i)-4c-1+4v_5(i),$$
where $c$ is the number of carries produced while doubling $i$ in base 5.
Substitute into the inequality:
$$2s_5(i)-4c-1+4v_5(i)+1>2s_5(i)$$
$$v_5(i)>c.$$
So the problem reduces to:
Count integers $i\le 10^{18}$ for which the number of carries when doubling $i$ in base 5 is strictly less than $v_5(i)$.
A digit-DP over base-5 digits counts numbers by carry count efficiently up to $10^{18}$.
The computation reproduces the given checks:
- $T_5(10^3)=68$
- $T_5(10^9)=2408210$
and finally gives:
Answer: 22173624649806