Сегодня у нас достаточно простая статья, связанная с занимательной математикой. Я думаю, все прекрасно, знают, что такое факториал:
Более изощренные любители математики знают и про такое понятие, как субфакториал:
Субфакториал
Субфакториал (или subfactorial) - обозначается символом !n и представляет собой количество перестановок n элементов, в которых ни один элемент не остается на своем месте (по сути - это аналогия полного беспорядка). Для небольших значений n это можно проиллюстрировать следующим образом:
Для n = 1: !1 = 0. Единственный элемент не может "переставляться" сам с собой.
Для n = 2: !2 = 1. Всего две возможные перестановки (1, 2) и (2, 1), и только одна из них соответствует требованию "ни один не остается на своем месте".
Для n = 3: !3 = 2. Возможные перестановки: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). В двух из них ни один элемент не остается на своем месте: (2, 3, 1) и (3, 1, 2).
Более жизненная интерпретация субфакториала: профессор дал тест 4 студентам – 1, 2, 3 и 4 – и хочет, чтобы они оценили тесты друг друга. Конечно, ни один студент не должен оценивать свой собственный тест. Сколько существует способов, чтобы никто не получил обратно свой собственный тест для проверки?
Первые десять значений субфакториалов натуральных чисел:
!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
!7 = 1854
!8 = 14833
!9 = 133496
!10 = 1334961
Если внимательно присмотреться к формуле субфакториала, то можно увидеть, что она очень похожа на формулу разложения экспоненты в ряд Тейлора:
Если подставить "-1" вместо n, то можно получить любопытное отношение между факториалом и субфакториалом:
Эта величина - предел вероятности того, что выбранная во множестве перестановка является полным беспорядком. А еще можно увидеть, что !n является ближайшим целым числом к n!/e:
Субфакторион
Теперь перейдем к субфакторионам - числам, которые равны сумме субфакториалов своих цифр. Для начала определим верхнюю границу таких чисел. Итак:
Теперь нам нужен простейший код на Python и онлайн-компилятор:
Итоговый результат, который выдала программа :
И это единственное число, которое носит гордое название "субфакторион". Первые его следы можно найти в достаточно интересной книжке 1966 года "Математика на каникулах":
На странице 167 есть упоминание этого факта:
Покопавшись еще в сети, удалось найти превью статьи из "Mathematical Magazine" с упоминанием факта, что субфакторион впервые был найден в 1966 году с применением ЭВМ:
Однако, стоит заметить, что мой "топорный" код выполнялся бы на компьютерах середины 70-х очень долго. Так что стоит отдать почести простым студентам-энтузиастам за программирование решения такой интересной задачки.
Больше математики в Telegram - "Математика не для всех".
Комментарии (73)
pavel_kudinov
30.08.2023 14:50+128какой-то искусственный этот субфакторион, он зависит от системы счисления
обычно математические объекты (например, простые числа, факториал, субфакториал) - одни и те же в разных системах счисления
когда начинают анализ "цифр из которых составлено число" - imho, как правило, это не имеющая прикладного смысла экзотика, близкая к нумерологии"настоящая" математика про числа как таковые, а то, в какой системе счисления мы их выражаем - должно быть не принципиально в большинстве случаев
inkelyad
30.08.2023 14:50+14"настоящая" математика про числа как таковые, а то, в какой системе счисления мы их выражаем - должно быть не принципиально в большинстве случаев
Теперь смотрим на разные системы кодирования (для связи) и контрольные суммы. Там очень всех интересует и влияет как длинное число на кусочки (не цифры, конечно, сложнее обычно) нарезать, чтобы какое-то полезное свойство получить.
SUNsung
30.08.2023 14:50+10Вы теплое с мягким путаете
Это как сравнивать эталонный килограм с килограмом кирпичей.
Для науки важно знать 1кг будь то в жидкой или газообразной форме, но в прикладных задачах уже важна фактическая реализация так сказать.
В разрезе кирпичей это все равно что сделать кирпич с массой в килограм расказывать о чуде что сумма его граней будет равна 1000.
p07a1330
30.08.2023 14:50+6когда начинают анализ "цифр из которых составлено число" - imho, как правило, это не имеющая прикладного смысла экзотика, близкая к нумерологии
Банальный пример - признаки делимости
Так что не всегда
ShadowTheAge
30.08.2023 14:50+23Признаки делимости такая штука, чтобы понять делится ли число - надо сначла поделить (ведь цифры в системе счисления получаются делением)
Вот такой напримнер признак: Число делится на N если в N-й системе счисления последняя цифра 0
Верно? - да. Полезно? Не особо.
arokettu
30.08.2023 14:50+3А такой - Число делится на N-1 если в N-й системе счисления сумма цифр делится на N-1?
Смысл признаков делимости в сведении сложного деления к более простому, вы просто привели тривиальный пример.
iig
30.08.2023 14:50+5Полезно? Не особо
bool is_odd = ( x & 0b1); bool is_even = ! is_odd;Полезное свойство. А для ассемблерного битоложества - незаменимое.
tenzink
30.08.2023 14:50+5А вот это на ваш взгляд настоящая математика - Статистика первых цифр степеней двойки и передел мира (В. И. Арнольд) ?
alexxz
30.08.2023 14:50+4Я, хоть и не адресат вопроса, считаю, что это не математика. Это - применение математического аппарата к физическим явлениям. И действительно есть некоторое тяготение к единице в начале. На эту тему есть много рассуждений, большинство из которых - полная чушь. Например рост взрослого человека в сантиметрах в подавляющем большинстве случаев начинается с единицы. Например, физики не считают первую единицу значащей "цифрой" в формулировке "до первой значащей цифры". Отношения к математике это все не имеет.
tenzink
30.08.2023 14:50+2Я увидел точный подсчёт доли чисел в геометрической последовательности начинающихся с 1 (в пределе), основанный на том, что десятичный логарифм от 2х - иррациональное число. На мой взгляд симпатичный математический результат, хотя и простой.
Это - применение математического аппарата к физическим явлениям
Думаю, странно не считать математикой то, у чего есть практическое применение. По такой логике и теория чисел не математика, так как она вдруг нашла применение в криптографии. Про диффуры и говорить нечего
Tyusha
30.08.2023 14:50+5Такие рассуждения о первой цифре будут верны в любой позиционной системе счисления и потому это "настоящая математика".
Ostrie_Brevna
30.08.2023 14:50Ну, Арнольд вообще считал, что математика - экспериментальная наука, сродни физике. (Его мнение было даже ещё более радикальным: математика - часть физики.) По его мнению "разница между математикой и физикой состоит только в том, что в физике эксперименты стоят миллионы или даже миллиарды долларов, а в математике — единицы рублей или копеек". Но можно добавить, что всё же не каждый математический эксперимент дёшев - для проведения некоторых математических экспериментов требуются дорогие вычислительные ресурсы. В общем, статистические методы тут должны наводить на мысль, что это уже настоящая физика :)
Tyusha
30.08.2023 14:50+2Как минимум тысячи людей, 400 лет работавших над теоремой Ферма, дожны были всë это время что-то есть.
tenzink
30.08.2023 14:50В статье в Кванте раздел про геометрические прогрессии - строгое математическое утверждение, объяснённое "на пальцах". А про площади и население уже действительно рассуждения в стиле психоистории Азимова - попытка построить модель эволюции, описывающую наблюдаемое распределение.
NooneAtAll3
30.08.2023 14:50+3какой-то искусственный этот субфакторион, он зависит от системы счисления
Такого полно. Человекам "чото" десятиричная система больше всех приглянулась
Цифры перемножаем, Из цифр числа собираем, Цифры у простых чисел отрезаем итд
andreybrylb Автор
30.08.2023 14:50+2Но она может породить алгоритмы, опровергнуть другие гипотезы или доказать их. А потом ...мало ли что выстрелит. По мне - это игра в долгую
Finesse
30.08.2023 14:50+8Можно смотреть на это как на частный случай более обширной задачи: нахождение субфакторионов в разных системах счисления
domix32
30.08.2023 14:50+3какой-то искусственный этот субфакторион, он зависит от системы счисления
Так фактически десятичные субфакторионы это лишь часть более общего класса n-субфакторионов, что вас не устраивает? Живут же люди с p-адиками при конкретных p и прекрасно себя чувствуют. Ну а так-то вся математика довольно искуственная.
flx0
30.08.2023 14:50+2Анализ цифр из которых составлено число не то чтобы прямо совсем бесполезен. Если число состоит из бесконечного количества цифр, то системы счисления совсем не эквивалентны друг другу, у них совершенно разная алгебраическая структура.
stan_volodarsky
30.08.2023 14:50+1p-адические числа, которые "... находят широкое применение в теоретической физике", - бесконечные цепочки цифр.
MountainGoat
30.08.2023 14:50+22В природе нет системы счисления. Если при смене системы счисления особые свойства числа пропадают, значит они и были придуманы с потолка. Например, 999 - это единственное число, которое при умножении составляющих его цифр на число единиц, равное корню суммы составляющих его цифр, даёт себя. Называется козлионом в честь первоизобретателя.
AllexIn
30.08.2023 14:50-4В природе и математики нет.
Системы счисления вполне себе "физичная" вещь и многие свойства интересные вылезают именно применимо к системам счисления.MountainGoat
30.08.2023 14:50То есть как это нет? Два камня плюс два камня всегда будет 4 камня. При этом четыре камня = four stones = 4????. Но если из этого делаются математические же выводы, то следует быть очень внимательным чтобы не получить очень сложное и изощрённое доказательство что 4 = 4, и ничего больше.
p07a1330
30.08.2023 14:50+12Не всегда
Например, если 2 камня положить в кольцо вычетов по модулю 3, то 2 камня + 2 камня = 1 камень
saboteur_kiev
30.08.2023 14:50А 1 капля + 1 капля будет что? две капли или капля побольше?
Физика не занимается математическими расчетами, которые каким-либо образом подвержены проблемам конкретной системы исчислений или их нотаций.
lil_master
30.08.2023 14:50Ага, а теперь попробуйте перемножить два камня на два камня) Потом представить результат)
А потом найти два одинаковых камня в природе.
Refridgerator
30.08.2023 14:50+1Ну если так ставить вопрос, то два камня перемножаются не на другие два камня, а на два ящика (в каждом из котором лежат по два камня). Или на два килограмма. В физике нельзя игнорировать единицы измерения при вычислениях, не все сочетания этих единиц имеют смысл.
Gummilion
30.08.2023 14:50+5Получится 4 квадратных камня, а с учетом того, что камни изначально трехмерны - 4 четырехмерных камня!
rinac
30.08.2023 14:50+2Это для вас это 4 камня. А так это просто некий упорядоченный массив атомов, которые находятся в каком-то порядке, который, может быть, отличается от остальных вокруг.
Нет никакой природы. Нет никаких камней вокруг вас. Все, что вы видите это то, свет различной интенсивности, попадающий на сетчатку. Все эти камни, растения, животные и прочее существует только в вашей голове, а в реальности это просто сгустки атомов различной структуры.
Sayonji
30.08.2023 14:50+3Корень суммы составляющих его цифр, т.е. корень из 27, иррационален. Также, "... умножении составляющих его цифр на ..." описывает умножение массива на число, т.е. а итоге одно число не выходит.
tenzink
30.08.2023 14:50+4Мне кажется, утверждение про природу абсурдно. Есть ли в природе алгоритмы, матрицы, многочлены, отрицательные, вещественные и комплексные числа, топология, кольца, поля, группы, категории, дифференциальные уравнения и т.п.?
Способ представления чисел очень нетривиален. Позиционные системы исчисления открыли недавно. До этого перемножать даже небольшие числа могли только очень образованные люди (например XIX * CCLXXXIII). Даже "быстрые" алгоритмы перемножения больших чисел в позиционных системах счисления ещё до 1960-го года был неизвестны (https://ru.wikipedia.org/wiki/Алгоритм_Карацубы). А лучший алгоритм неизвестен даже сейчас (https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science)
В 1960 году Андрей Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух n n-разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало O(n^{2}) элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше n^{2} по порядку величины
И ещё есть способы представлять числа в позиционных системах счисления с другими базисами (https://ru.wikipedia.org/wiki/Фибоначчиева_система_счисления, ...). Уверен, что есть ещё неоткрытые способы представления с удивительными и полезными свойствами, например для использования в квантовых компьютерах
Lepidozavr
30.08.2023 14:50Математика это же абстракция. В ней свои пост-свойства возникают, которые тоже могут быть (скорее всего и являются) абстракцией какого-то процесса, свойства в мире. То, что вы перечисляете - абстракции. Или чего вам не хватает? Не может же там быть звёздочки и мелкого шрифта "это многочлен"?)
oleg_rico
30.08.2023 14:50Ну вообще-то есть такое понятие как натуральные числа. Они потому и натуральные что используется для пересчёта предметов природы.
Ostrie_Brevna
30.08.2023 14:50А ноль - натуральное число? ;)
oleg_rico
30.08.2023 14:50+1Ноль в натуральные числа не входит.
wataru
30.08.2023 14:50В общепринятом в российской школе определении не входит. На западе учат — что входит. Включать 0 в натруральные числа гораздо логчнее, имхо.
oleg_rico
30.08.2023 14:50Конечно, уже имея ноль можно рассуждать о том что эта штука для обозначения что нет ничего. Но на самом деле ноль значительно более важное изобретение. Однако человеку которому нужно что-то посчитать вроде числа козочек в загоне число 0 не пригодится.
Есть такой фантастический роман про попаданцев из тех времён когда это ещё не было трендом "да не опуститься тьма". Там попаданец как раз и начал влиять на реальность внедряя вместо римских арабские цифры. Заодно ещё двойную бухгалтерскую запись.
wataru
30.08.2023 14:50+2Это проблема исключительно определений. Во многих школах, ноль — натруальное число. В других — нет, но есть категория whole numbers, которая влючает и 0. Путаница тут возникла из-за того, что ноль люди придумали совсем не сразу. Потому что 10 коров — вот они, их видно. А 0 коров — не видно, пощупать нельзя.
Но физическое свойство количества объектов от разных определений не пропадает.
bolk
30.08.2023 14:50Вряд ли в семидесятые перебирали с использованием рекурсии.
Finesse
30.08.2023 14:50Достаточно добавить функции
subfactorialкеш, и сложность сведётся кO(n). Ну или можно «снизу-вверх» посчитать (начать с малыхnи постепенно увеличивать, храня результаты предыдущих вычислений).bolk
30.08.2023 14:50Я разве говорю, что это нельзя сделать? Я говорю о том, что в 70-е вряд ли вычисляли так, как сейчас в коде. В статье написано:
Однако, стоит заметить, что мой "топорный" код выполнялся бы на компьютерах середины 70-х очень долго
longclaps
30.08.2023 14:50+2Теперь нам нужен простейший код на Python и онлайн-компилятор
Рассказать вам о разнице между компилятором и интерпретатором, или предпочитаете остаться при своих заблуждениях?
n0isy
30.08.2023 14:50+1Чтобы не ошибаться, можно всё называть термином из семидесятых: транслятор (это общее слово, обозначающее компиляторы и интерпретаторы). Сейчас и не разберешься, где компилятор: вот nodejs - это что? Вроде бы внутри компилируется в V8, но бинарника нет.
Guul
30.08.2023 14:50+2Рассказать о разнице между питоном и его байткодом? Или предпочитаете остаться при своих заблуждениях?
Finesse
30.08.2023 14:50+1Почему субфакториал считается именно так?
return (n - 1) * (subfactorial(n - 1) + subfactorial(n - 2))Первая часть
(n - 1)понятна, в текущей позиции может быть любой элемент кроме одного. А дальше не могу понять.
Deosis
30.08.2023 14:50+1Рассмортим генерацию такой перестановки для n элементов:
выбираем случайное число от 2 до n (n-1 вариант)
меняем местами 1 и выбранное число
А) если в дальнейшем 1 будет перемещена, значит каждое из оставшихся чисел изменит положение, что соответствует значению
subfactorial(n - 1)Б) если 1 останется в том положении, куда её переместили, то остается посчитать количество вариантов для оставшихся n-2 чисел
Alexandroppolus
30.08.2023 14:50Ещё можно напрямую подставить формулу для !n вместо subfactorial(n - 1) и subfactorial(n - 2), и там всё удачно сокращается, если сгруппировать как
n * !(n-1) - !(n-1) + (n-1) * !(n-2)
wataru
30.08.2023 14:50+3Хорошо бы добавить в статью описание, как эта формула в начале выводится. Например, это можно сделать по формуле включения исключения: возьмем n!, вычтем все перестановки, где хотя бы одно число на своем месте. добавим те, где хотя бы 2 числа на своем месте, потому что они по 2 раза вычлись раньше, и т.д. Количество перестановок хотя бы с i элементами на своем месте n!/i!/(n-i)! * (n-i)! — количество сочетаний из n по i, и оставшиеся n-i чисел могут быть перетасованы как угодно).
А вот еще интересно бы посмотреть объяснение, почему !n = Floor(n! / e)
Alexandroppolus
30.08.2023 14:50+1А вот еще интересно бы посмотреть объяснение, почему !n = Floor(n! / e)
Это, кстати, не всегда верно. Например, для четных n получается !n > Floor(n! / e), там похоже округление вверх.
А в целом доказать не сложно.
Между !n и n!/e разница D = n! * ( 1/(n+1)! - 1/(n+2)! + 1/(n+3)! - 1/(n+4)! + ...). Если в этом ряду в каждом отрицательном слагаемом слегка увеличить знаменатель, то сумма вырастет и будет X = n! * ( 1/(n+1)! - 1/(n+3)! + 1/(n+3)! - 1/(n+5)! + ...) = 1/(n+1). Ну и заметим, что D < X < 1. Т.е. между !n и n!/e целых нет.
akhalat
30.08.2023 14:50+3Это, кстати, не всегда верно. Например, для четных n получается !n > Floor(n! / e), там похоже округление вверх.
В тексте статьи верно написано "ближайшим целым", т.е. не floor а round.
lgorSL
30.08.2023 14:50А вот еще интересно бы посмотреть объяснение, почему !n = Floor(n! / e)
Мне вообще кажется, что рядом скрыта очень красивая математика. Например гиперболический синус единицы можно предствить как сумму 1 + 1 / 3! + 1 / 5! ..., а гиперболический косинус единицы - сумму 1 + 1/2! + 1/4! и если я нигде не ошибаюсь, то для n, стремящихся к бесконечности получается
почему именно округление вниз - не знаю.
LF69ssop
30.08.2023 14:50+1!9=133496, значит max=133496*6=800976
Я что-то не понял этой логической связи.
А почему не
!9=133496, значит max=133496*7=934472 например?
По какой причине все что выше 6 не подходит то?
Finesse
30.08.2023 14:506 цифр. Максимальная цифра 9. Поэтому !9 * 6. Для 7 цифр значение !9 * 7 имеет меньше 7 цифр, поэтому никакое число из 7 не цифр не может быть субфакторионом.
TeiSinTai
30.08.2023 14:50+1Потому что минимальное 7-значное число (1 000 000) больше 934472 (максимальной суммы для 7 цифр 9 999 999). А дальше "минимальное число, выражаемое X цифр", растет экспоненциально относительно X, а "максимальная сумма субфакториалов числа с X цифр" - линейно.
wataru
30.08.2023 14:50+1Самое большое число, которое можно получить от одной цифры — !9. Взяв n цифр мы получим максимум n*!9. А число из n цифр будет как минимум 10^(n-1). 10^(n-1) растет быстрее n*!9, поэтому при каком-то количестве цифр число всегда будет больше даже верхней оценки суммы субфакториалов цифр.
Примерно оценить это количество можно как раз найдя такое n, что n*!9 состоит из менее чем n цифр. 7*!9 — 6-ти значное число, значит никакое 7 и более значное число обладать искомым свойсвом не будет.
zag2art
Не понятно и где тут что осталось на своем месте?
datacompboy
В варианте (1, 2) 1 на 1м месте а 2 на втором, то есть остались на своих местах; а в (2, 1) два на первом и 1 на втором -- то есть ни одно не на своём месте.