"브럼 브럼 셔브(Blum Blum Shub)"라 불리는 유사 난수 생성기를 이용한 수열을 만듭니다:

이 난수들을 차례로 연결하여 s₀s₁s₂… 무한 길이의 숫자열 w를 만듭니다.
그래서, w = 14025256741014958470038053646…입니다

k가 자연수일 때, 만일 w의 어떤 부분 숫자열의 자릿수 합도 k와 일치하는게 없다면 p(k)를 0으로 정의합니다. 만일 w의 어떤 부분 숫자열 하나라도 자릿수의 합이 k라면, p(k) = z라 정의합니다. 여기서, z는 가장 먼저 나오는 부분 숫자열의 시작 위치입니다.

예로:

부분 숫자열 1, 14, 1402, …
각각의 자릿수의 합은 다음과 같습니다 1, 5, 7, …
모두 시작 위치 1에서 시작하므로 p(1) = p(5) = p(7) = … = 1입니다.

부분 숫자열 4, 402, 4025, …
각각의 자릿수의 합은 다음과 같습니다 4, 6, 11, …
모두 시작 위치 2에서 시작하므로 p(4) = p(6) = p(11) = … = 2입니다.

부분 숫자열 02, 0252, …
각각의 자릿수의 합은 다음과 같습니다 2, 9, …
모두 시작 위치 3에서 시작하므로 p(2) = p(9) = … = 3입니다.

위치 3에서 시작하는 부분 숫자열 025는 자릿수의 합이 7이지만 더 일찍(위치 1에서) 시작하는 부분 숫자열 중에 자릿수 합의 7인 것이 있기 때문에 p(7) = 1이지 3이 아닙니다.

0 < k ≤ 10³일 때, ∑ p(k) = 4742입니다.

0 < k ≤ 2×10¹⁵일 때, ∑ p(k) 값을 구하세요.