Стала була відкрита у 1949 році індійським математиком Д.Р.
Капрекаром, на честь якого і отримала свою назву.
Оберемо довільне чотирицифрове число n, що більше за 1000 та
в якому не усі цифри однакові. Розташуємо цифри числа n спочатку у порядку
зростання, потім у порядку спадання. Віднімемо від більшого отриманого числа
менше. Стверджується, що повторюючи цей процес з отриманими різницями, не
більше ніж за сім кроків ми отримаємо число, яке буде відновлювати саме себе.
Таке число назвали сталою Капрекара.
Для числа 5545: 5554-4555=0999 9990-0999=8991 9981-1899=8082 8820-0288=8532 8532-2358=6174 7641-1467=6174 Отже,
число 6174 є сталою Капрекара.
Чому накладаються умова неоднаковості всіх цифр? Очевидно,
при цьому різниця буде дорівнювати нулю, випадок тривіальний, а тому нецікавий. Чому
відсікаємо число 1000? В цьому випадку кроки матимуть вигляд: 1000-0001=999 999-999=0 Що
також нецікаво.
Серед трицифрових чисел аналогічну властивість має число
495. Процедура проводиться для будь-якого трицифрового числа без цифр, що
повторюються. Для чисел з більшою, ніж 4, кількістю знаків, перетворення
Капрекара у більшості випадків рано чи пізно приводить до циклічного повторення
чисел, але не до нерухомої точки. Для 5-цифрових чисел нерухомої точки взагалі
не існує. Є два шестицифрових числа, що є сталими Капрекара (549 945
та 631 764), семицифрових чисел з такою властивістю немає.
Безпосередньою перевіркою можна довести, що будь-яке число
вигляду 633...331766...664 (де кількість
цифр у послідовності шісток та трійок однакова), але не будь-яка стала може
бути подана у такому вигляді.
Сформулюємо задачу.
Дано довільне чотирицифрове число n, більше за 1000 та в
якому не усі цифри однакові. За скільки кроків воно може перетворитися у сталу
Капрекара та чому буде дорівнювати ця стала.
Контрольний приклад:
5545 → 6
і 6174.
Постійна Капрекара — число, рівне 6174.
Функція Капрекара
Число 6174 має таку особливість. Виберемо довільне чотиризначне число n, більше за 1000, в якому не всі цифри однакові (всюди припускається використовування десяткової системи числення, якщо не обумовлено інше). Розмістимо цифри спочатку в порядку зростання, а потім в порядку спадання. Віднімемо від більшого числа менше. В процесі перестановки цифр і віднімання нулі слід зберегти. Результат назвемо функцією Капрекара K(n), а сам алгоритм - алгоритм Капрекара. Повторюючи цей процес з отриманими різницями, не більш ніж за сім кроків отримаємо число 6174, яке буде потім відтворювати саме себе: 7641 — 1467 = 6174.
Цю властивість числа 6174 було відкрито у 1949 році індійським математиком Д. Р. Капрекаром, на честь якого воно і отримало свою назву.
Основні властивості
Приклади
Для числа 3524:
- 5432 — 2345 = 3087
- 8730 — 0378 = 8352
- 8532 — 2358 = 6174
- 7641 — 1467 = 6174
Для числа 9831:
- 9831 — 1389 = 8442
- 8442 — 2448 = 5994
- 9954 — 4599 = 5355
- 5553 — 3555 = 1998
- 9981 — 1899 = 8082
- 8820 — 0288 = 8532
- 8532 — 2358 = 6174
Єдиними чотиризначними числами, для яких функція Капрекара не досягає числа 6174, є так звані репдігіти[en] , такі як 1111, 5555, 4444, …., що дають в результаті 0000 після єдиної ітерації. Всі інші чотиризначні числа зрештою приходять до 6174, якщо нулі, які містяться в цифрах, лишати, щоб число залишилось чотиризначним. Наприклад:
- 2111 — 1112 = 0999
- 9990 — 0999 = 8991 (замість 999—999 = 0)
- 9981 — 1899 = 8082
- 8820 — 0288 = 8532
- 8532 — 2358 = 6174
Чому саме 6174?
- Розв'язування за допомогою лінійних рівнянь
Цифри довільного чотиризначного числа можуть бути розташовані в порядку спадання і таким чином створювати більше число, і в порядку зростання, створюючи менше число. Тоді для цифр a,b,c,d, таких що
- 9 ≥ a ≥ b ≥ c ≥ d ≥ 0,
і a,b,c,d не всі рівні між собою, більшим числом буде abcd, а меншим - dcba. Ми можемо порахувати результат функції Капрекара, використовуючи стандартний метод віднімання в стовпчик
_ a b c d d c b a ——————— A B C D
Це дасть нам наступні співвідношення
- D = 10 + d - a (в силу того, що a > d)
- C = 10 + c - 1 - b = 9 + c - b (в силу того, що b > c - 1)
- B = b - 1 - c (в силу того, що b > c)
- A = a - d
Для цих чисел виконуються нерівності
- a>b>c>d
Ця процедура буде повторюватися за алгоритмом Капрекара, поки різницю ABCD не можна буде записати за допомогою початкових чотирьох цифр a,b,c,d. Можна знайти розв'язок системи рівнянь, перебираючи всі можливі комбінації {a,b,c,d} і перевіряючи, чи задовольняють вони вище вказаним співвідношенням. Кожна з 4! = 24 комбінацій дає систему чотирьох лінійних алгебраїчних рівнянь з чотирма невідомими, тому розв'язок для a, b, с, d існує за теоремою Кронекера — Капеллі. Виявляється, що тільки одна з цих комбінацій дає цілі розв'язки, які задовольняють 9 ≥ a ≥ b ≥ c ≥ d ≥ 0, і це ABCD = bdac. Тоді розв'язком системи рівнянь буде a=7, b=6, c=4 і d=1, а це означає, що ABCD = 6174. Інших цілих розв'язків для цієї системи не існує.
Кількість ітерацій
За допомогою комп'ютера можна швидко порахувати, яка кількість ітерацій, за яку чотиризначні числа від 1000 до 9999 дійдуть до числа 6174. Нижче приведена таблиця відповідних результатів, які були підраховані за допомогою PascalABC.
| Кількість ітерацій | Кількість чисел |
|---|---|
| Виключення | 9 |
| 1 | 357 |
| 2 | 519 |
| 3 | 2124 |
| 4 | 1124 |
| 5 | 1379 |
| 6 | 1508 |
| 7 | 1980 |
Виключеннями вважаються числа з усіма однаковими цифрами (1111, 2222, ...), бо для них на першому ж кроці алгоритму Капрекара отримаємо нуль.
Графічне представлення
Ми з'ясували, що максимальна кількість ітерацій в алгоритмі Капрекара - сім. Призначимо конкретний колір для кожної можливої кількості ітерацій: 0 - білий, 1 - жовтий, 2 - зелений, 3 - бірюзовий, 4 - блакитний, 5 - синій, 6 - рожевий, 7 - червоний. При чому вважатимемо, що кількості кроків 0 відповідають числа-виключення (0000, 1111, 2222, 3333, ...).
Якщо ми зобразимо числа від 0000 до 9999 у вигляді таблиці 100 x 100 і позначимо кількість ітерацій, що приводить до 6174, відповідним кольором, то отримаємо таку таблицю:
Яким шляхом досягається 6174?
Візьмемо чотиризначне число abcd, таке що 9 ≥ a ≥ b ≥ c ≥ d ≥ 0. Порахуємо першу різницю за алгоритмом Капрекара: від більшого числа 1000a+100b+10c+d віднімемо менше число 1000d+100c+10b+a:
1000a + 100b + 10c + d - (1000d + 100c + 10b + a) = 1000(a-d) + 100(b-c) + 10(c-b) + (d-a) = 999(a-d) + 90(b-c).
Число (a-d) набуває значень від 1 до 9, а число (b-c) - від 0 до 9. Перебираючи всі комбінації, можна побачити всі можливі результати першого кроку алгоритму Капрекара.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 0 | 999 | 1998 | 2997 | 3996 | 4995 | 5994 | 6993 | 7992 | 8991 |
| 1 | 1089 | 2088 | 3087 | 4086 | 5085 | 6084 | 7083 | 8082 | 9081 |
| 2 | 2178 | 3177 | 4176 | 5175 | 6174 | 7173 | 8172 | 9171 | |
| 3 | 3267 | 4266 | 5265 | 6264 | 7263 | 8262 | 9261 | ||
| 4 | 4356 | 5355 | 6354 | 7353 | 8352 | 9351 | |||
| 5 | 5445 | 6444 | 7443 | 8442 | 9441 | ||||
| 6 | 6534 | 7533 | 8532 | 9531 | |||||
| 7 | 7623 | 8622 | 9621 | ||||||
| 8 | 8712 | 9711 | |||||||
| 9 | 9801 |
Нас цікавлять тільки ті числа, всі цифри яких не однакові, а також a ≥ b ≥ c ≥ d, в силу цього розглядатимемо тільки ті числа, для яких (a-d) ≥ (b-c). Тому можна опустити частину чисел в таблиці (ті, що викреслені), бо для цих чисел виконується нерівність (a-d) < (b-c). Тепер розташуємо цифри в числах у порядку спадання, щоб отримати максимальні числа виду abcd, 9 ≥ a ≥ b ≥ c ≥ d ≥ 0, для яких знову застосуємо алгоритм Капрекара.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 0 | 9990 | 9981 | 9972 | 9963 | 9954 | ||||
| 1 | 9810 | 8820 | 8730 | 8640 | 8550 | ||||
| 2 | 8721 | 7731 | 7641 | 7551 | 9711 | ||||
| 3 | 7632 | 6642 | 6552 | 8622 | 9621 | ||||
| 4 | 6543 | 5553 | 7533 | 8532 | 9531 | ||||
| 5 | 5544 | 6444 | 7443 | 8442 | 9441 | ||||
| 6 | |||||||||
| 7 | |||||||||
| 8 | |||||||||
| 9 |
Викреслюємо ті числа, які повторюються, і, врешті, залишається 30 чисел, які знову перетворюємо, як і попередні; продовжуємо процес. На наступному малюнку показано, як ці числа приходять до 6174. Легко бачити, що максимальна кількість ітерацій дорівнює семи.
Інші властивості
Зазначимо, що на кожній ітерації два числа, що віднімаються одне від одного, мають однакову суму цифр, таким чином і однакову остачу за модулем 9. З цього випливає, що результат кожної ітерації буде кратний 9.
6174 — число харшад, оскільки воно ділиться на суму своїх цифр:
- 6174 = (6 + 1 + 7 + 4) × 343.
6174 — практичне число[en], оскільки довільне число, менше за 6174, можна подати у вигляді суми різних дільників числа 6174. Найближчі числа з такою властивістю — 6160, 6162, 6180, 6188. Крім того, 6174 — число Цумкелера (англ. Zumkeller number), оскільки множину дільників числа 6174 можна розбити на дві підмножини з рівними сумами (7800).
Не існує натурального числа, при діленні якого на суму його цифр виходить 6174. Найближчі числа з такою властивістю — 6123, 6150, 6185, 6189.
Число 6174 можна представити у вигляді суми трьох перших натуральних степенів числа 18:
- 18³ + 18² + 18 = 5832 + 324 + 18 = 6174.
Сума квадратів простих множників числа 6174 — точний квадрат:
- 2² + 3² + 3² + 7² + 7² + 7² = 4 + 9 + 9 + 49 + 49 + 49 = 169 = 13².
Узагальнення
Серед тризначних чисел аналогічною властивістю володіє 495 (процедура сходиться до нього максимум через шість ітерацій для довільного тризначного числа з різними цифрами). Для чисел з більшою, ніж 4, кількістю знаків, перетворення Капрекара в більшості випадків рано чи пізно приводить до циклічних повторень чисел, але не до нерухомої точки n = K(n). Для п'ятизначних чисел нерухомої точки не існує. Є два шестизначных числа, які є нерухомими точками перетворення Капрекара (549 945 і 631 764), семизначных чисел з такою властивістю не існує.
Легко довести безпосередньою перевіркою, що довільне число вигляду 633…331766…664 (де кількість цифр в послідовностях шісток і трійок однакова) є нерухомою точкою n = K(n). Сама постійна Капрекара теж є числом цього вигляду. Однак не всяка нерухома точка може бути записана в такому вигляді.
Немає коментарів:
Дописати коментар