65 lines
3.7 KiB
Markdown
65 lines
3.7 KiB
Markdown
---
|
||
id: 5900f50b1000cf542c51001d
|
||
title: 'Завдання 414: Стала Капрекара'
|
||
challengeType: 5
|
||
forumTopicId: 302083
|
||
dashedName: problem-414-kaprekar-constant
|
||
---
|
||
|
||
# --description--
|
||
|
||
6174 — доволі цікаве число. Якщо розмістити його цифри у порядку зростання, отримаємо 1467; якщо розмістити його цифри у порядку спадання, вийде 7641. Результатом віднімання двох отриманих чисел буде $7641 - 1467 = 6174$.
|
||
|
||
Цікавим є й те, що якщо взяти будь-яке чотиризначне число та повторити попередні дії сортування цифр та віднімання, ми отримаємо 6174 або одразу 0, якщо всі цифри однакові.
|
||
|
||
Те саме відбувається з числами, які складаються з менше ніж із 4 цифр. Але для цього до них потрібно додати нулі, щоб утворити чотиризначні числа.
|
||
|
||
Наприклад, почнемо з числа 0837:
|
||
|
||
$$\begin{align} & 8730 - 0378 = 8352 \\\\
|
||
& 8532 - 2358 = 6174 \end{align}$$
|
||
|
||
6174 називається сталою Капрекара. Сортування цифр, віднімання та повторення цього процесу поки не отримаємо 0 або сталу Капрекара, називається перетворенням Капрекара.
|
||
|
||
Можна розглядати рутину Капрекара і для інших систем числення та кількості цифр. На жаль, стала Капрекара існує не у всіх випадках. Перетворення закінчується циклом для деяких вхідних чисел або стала, отримана в результаті перетворення, інша для різних вхідних чисел. Однак для п'яти цифр та основи $b = 6t + 3 ≠ 9$ константа Капрекара існує.
|
||
|
||
Наприклад, основа 15: ${(10, 4, 14, 9, 5)}\_{15}$ основа 21: $(14, 6, 20, 13, 7)_{21}$
|
||
|
||
Нехай $C_b$ — стала Капрекара в основі $b$ для 5-ти цифр. Визначте функцію $sb(i)$:
|
||
|
||
- 0, якщо $i = C_b$, або якщо $i$, записаний в основі $b$, складається з 5-ти однакових цифр
|
||
- кількість повторень, здійснених під час перетворення Капрекара в основі $b$, щоб досягти $C_b$
|
||
|
||
Зверніть увагу, що ми можемо визначити $sb(i)$ для всіх цілих чисел $i < b^5$. Якщо $i$, записане в основі $b$ має менше, ніж 5 цифр, то до числа додаємо нулі, поки не воно не стане п'ятизначним. Аж тоді застосовуємо перетворення Капрекара.
|
||
|
||
Визначимо $S(b)$ як суму $sb(i)$ для $0 < i < b^5$. Наприклад, $S(15) = 5\\,274\\,369$ $S(111) = 400\\,668\\,930\\,299$
|
||
|
||
Знайдіть суму $S(6k + 3)$ для $2 ≤ k ≤ 300$. У відповіді запишіть 18 останніх цифр.
|
||
|
||
# --hints--
|
||
|
||
`kaprekarConstant()` має повернути `552506775824935500`.
|
||
|
||
```js
|
||
assert.strictEqual(kaprekarConstant(), 552506775824935500);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function kaprekarConstant() {
|
||
|
||
return true;
|
||
}
|
||
|
||
kaprekarConstant();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|