0%

Problem 486


Problem 486


Palindrome-containing strings

Let F5(n) be the number of strings s such that:

  • s consists only of ‘0’s and ‘1’s,
  • s has length at most n, and
  • s contains a palindromic substring of length at least 5.

For example, F5(4) = 0, F5(5) = 8, F5(6) = 42 and F5(11) = 3844.

Let D(L) be the number of integers n such that 5 ≤ n ≤ L and F5(n) is divisible by 87654321.

For example, D(107) = 0 and D(5·109) = 51.

Find D(1018).


包含回文的数串

记F5(n)是满足下列条件的数串s的数目:

  • s仅包含0和1;
  • s的长度至多为n;
  • s包含有一个长度至少为5的回文子串。

例如,F5(4) = 0,F5(5) = 8,F5(6) = 42,F5(11) = 3844。

记D(L)是所有满足5 ≤ n ≤ L且F5(n)能被87654321整除的整数n的数目。

例如,D(107) = 0,D(5·109) = 51。

求D(1018)。