freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/project-euler/problem-238-infinite-string-tour.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5900f45b1000cf542c50ff6d	Завдання 238: Нескінченна подорож по рядках	5	301883	problem-238-infinite-string-tour

--description--

Створіть послідовність чисел, використовуючи генератор псевдовипадкових чисел "Блум Блум Шуба":

$$ s_0 = 14025256 \\ s_{n + 1} = {s_n}^2 \; mod \; 20\,300\,713 $$

Об'єднайте ці числа s_0s_1s_2\ldots, щоб створити рядок w нескінченної довжини. Тоді w = 14025256741014958470038053646\ldots

Для додатного цілого числа 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) = \ldots = 1.

Підрядки 4, 402, 4025, … суми цифр яких дорівнюють 4, 6, 11, … починаються з позиції 2, отже, p(4) = p(6) = p(11) = \ldots = 2.

Підрядки 02, 0252, … суми цифр яких дорівнюють 2, 9, … починаються з позиції 3, отже, p(2) = p(9) = \ldots = 3.

Зауважте, що підрядок 025, що починається з позиції 3, має суму чисел, що дорівнює 7, проте перед ним маємо підрядок (що починається з позиції 1) з сумою чисел, що дорівнює 7, тому p(7) = 1, не 3.

Можемо перевірити, що для 0 < k ≤ {10}^3, \sum p(k) = 4742.

Знайдіть \sum p(k), для 0 < k ≤ 2 \times {10}^{15}.

--hints--

infiniteStringTour() має повернути 9922545104535660.

assert.strictEqual(infiniteStringTour(), 9922545104535660);

--seed--

--seed-contents--

function infiniteStringTour() {

  return true;
}

infiniteStringTour();

--solutions--

// solution required