Обчисліть біноміальні коефіцієнти C(n,k) за модулем невеликого простого числа й розфарбуйте кожну клітинку за її залишком. За модулем 2 отримуємо точнісінько трикутник Серпінського — це наслідок теореми Лукаса, а інші прості числа дають власні самоподібні фрактальні візерунки.
Цей інструмент будує трикутник Паскаля рядок за рядком за рекурентою C(n,k) = C(n-1,k-1) + C(n-1,k), але замість того, щоб дозволити числам зростати безмежно, кожне додавання зводиться за модулем невеликого простого числа p. У результаті замість трикутника з величезних цілих чисел отримуємо трикутник лише з p можливих залишків, і коли ці залишки розфарбувати, з'являється разюче регулярний фрактал. Для p = 2 цей візерунок точнісінько збігається з трикутником Серпінського — наслідок теореми Лукаса про біноміальні коефіцієнти за модулем простого числа.
Кожна клітинка (n,k) трикутника містить C(n,k) mod p, обчислене за допомогою "кочівного" масиву на місці для рекуренти Паскаля, тож навіть 256 рядків обчислюються миттєво. У фрактальному режимі залишок 0 залишається порожнім, а інші p−1 залишків отримують окремі кольори, розкриваючи самоподібні трикутні візерунки, що повторюються на кожному масштабі.
Пересуньте повзунок кількості рядків, щоб обчислити більше або менше рядків, оберіть модуль 2, 3, 5 або 7 та перемикайтеся між кольоровим фрактальним виглядом і виглядом точних цілих чисел (обмежено 14 рядками, щоб числа залишалися читабельними). Спробуйте кожну з трьох колірних схем, щоб побачити структуру залишків по-різному.
Теорема Куммера каже, що точний степінь p, який ділить C(n,k), дорівнює кількості перенесень при додаванні k і n−k у системі числення за основою p — тож фрактал, який ви бачите, буквально є картинкою перенесень (або їхньої відсутності) під час додавання.
За теоремою Лукаса, C(n,k) mod 2 дорівнює 1 саме тоді, коли кожен двійковий розряд k менший або дорівнює відповідному двійковому розряду n (тобто k AND n = k). Забарвлюючи клітинки, де це виконується, і залишаючи решту порожніми, ми отримуємо, рядок за рядком, точнісінько той самий рекурсивний візерунок трикутних порожнин, що й у класичній побудові трикутника Серпінського — це не наближення, а точний збіг на рівні бітів.
Теорема Лукаса стверджує, що для простого числа p значення C(n,k) mod p можна обчислити, записавши n і k у системі числення за основою p порозрядно та перемноживши біноміальні коефіцієнти відповідних розрядів за модулем p: C(n,k) ≡ добуток C(n_i,k_i) (mod p). Якщо якийсь розряд k перевищує відповідний розряд n, один із цих множників дорівнює нулю, тож увесь добуток дорівнює нулю — саме тому порожні (нульові) клітинки з'являються там, де вони є.
Теорема Лукаса діє для будь-якого простого числа, але правило порозрядного порівняння працює в системі числення за основою p, а не за основою 2. Для p = 3 трикутник поділяється на самоподібне розташування копій, масштабованих у 3×3, а не 2×2, і можливо більше класів залишків (0, 1, 2, ...), тож візерунок має багатше внутрішнє забарвлення й іншу симетрію, ніж суто двійковий випадок Серпінського.
Справжнє значення C(256,128) має близько 75 цифр — набагато більше, ніж вміщують стандартні 32- чи 64-бітні цілі числа, і його точне обчислення вимагало б повільної арифметики довільної точності. Оскільки потрібен лише залишок за модулем p, кожну проміжну суму можна одразу звести до числа від 0 до p−1, тож усі обчислення залишаються на малих швидких цілих числах незалежно від кількості обчислених рядків.
Окрім того, що це вражаючий візуально фрактал, біноміальні коефіцієнти за модулем p відіграють центральну роль у комбінаториці над скінченними полями, теорії кодування та клітинних автоматах — трикутник Паскаля за модулем 2 тісно пов'язаний із правилом 90 у класифікації елементарних клітинних автоматів Вольфрама. Та сама порозрядна структура з теореми Лукаса також застосовується у швидких алгоритмах обчислення біноміальних коефіцієнтів за модулем простого числа в спортивному програмуванні та криптографії.