Hay un buen algoritmo para hacer este cálculo, que se explica aquí.
Si $x$ es el número de los que tenemos, $f(x)$ es el número de ceros que aparecen en el intervalo de $1..x$. Mediante un sencillo programa podemos calcular el $f(x)$ para algunos valores pequeños para detectar un patrón.
public int CountZerosInRangeOneTo(int end)
{
return Enumerable.Range(1, end)
.Select(i => i.ToString())
.SelectMany(s => s.ToCharArray())
.Count(c => c == '0');
}
Por ejemplo:
f(5 ) = 0
f(52 ) = 5
f(523 ) = 102
f(5237 ) = 1543
f(52378) = 20667
Si $y$ es el nuevo single número de dígitos que se agregan al final de cada tiempo, aparecen las siguientes es verdadera:
$f(10x + y) = 10 \cdot f(x) + x$
Por ejemplo, si $x = 523$, $y = 7$, y $f(x) = 102$, entonces:
$f(10 \cdot 523 + 7) = f(5237) = 10 \cdot f(x) + x = 10 \cdot 102 + 523 = 1543$
Fantástico. Sin embargo, cuando este se rompe es cuando $x$ contiene ceros en sí. Por ejemplo:
f(3 ) = 0
f(30 ) = 3 correct
f(302 ) = 53 incorrect, expected 60, a difference of 7, or 9 - y
f(3020 ) = 823 incorrect, expected 832, a difference of 9, or 9 - y
f(30207) = 11246 incorrect, expected 11250, a difference of 4, or 2 * (9 - y)
Si $g(x)$ es el número de ceros en el número de $x$, entonces podemos modificar nuestra fórmula como esta:
$f(10x + y) = 10 \cdot f(x) + x - g(x) \cdot (9 - y)$
Y que tiene sentido. Si $x = 3020$ $y = 7$ e no $9$, que es dos menos de los números en la final de la secuencia con dos ceros cada uno.
Entonces, ¿cómo esta fórmula ayuda? Bien para una muy grande $x$ con miles de dígitos podemos ir de izquierda a derecha a través de cada dígito y calcular el $f(x)$ como vamos. Aquí un ejemplo de un programa de C# para hacer precisamente eso.
public long CountZerosInRangeOneTo(string end)
{
long x = 0;
long fx = 0;
int gx = 0;
foreach (char c in end)
{
int y = int.Parse(new string(c, 1));
// Our formula
fx = 10 * fx + x - gx * (9 - y);
fx += Modulus; // Avoid negatives
fx %= Modulus;
// Now calculate the new x and g(x)
x = 10 * x + y;
x %= Modulus;
if (y == 0)
gx++;
}
return fx;
}
La limitación (en C# de todos modos) es $x$ $f(x)$ va a hacerse muy grandes, por lo que el programa deberá calcular el resultado modulo algún número, o bien utilizar un no-nativo representación integral.
