Défi Turing

Pour tout entier positif n, on définit la fonction F par F(n)=k où k est le plus petit entier positif tel que n + k n'est pas divisible par k + 1.

Exemples

1. 13 est divisible par 1, 14 est divisible par 2, 15 est divisible par 3, 16 est divisible par 4, mais 17 N’EST PAS divisible par 5. Donc F(13) = 4.
2. 120 est divisible par 1, mais 121 n'est PAS divisible par 2. Donc F(120) = 1.

On définit P(s, N) comme étant le nombre d'entiers n (1 < n < N) pour lesquels F(n) = s.
Ainsi P(3, 14) = 1 et P(6, 10⁶) = 14286.

Que vaut la somme, pour i allant de 1 à 1000, des P(i, 10ⁱ) ? On saisira les 12 derniers chiffres du résultat.