Краткое содержание
недавнего ролика на популярно-математическом канале Numberphile: Четверо аргентинских школьников пару лет назад получили новый математический результат.
Ранее было известно, что если для каждого целого положительного числа N взять минимальное простое число P, такое, что N делится на P с остатком, то получается последовательность
2,3,2,3,2,5,2,3,2,3,... (как нетрудно видеть, первая семерка будет только на 30-м месте), среднее арифметическое начальной подпоследовательности которой сходится к A = 2.920050977316134...
Новый результат заключается в том, что константа 2.920050977316134... кодирует в себе все простые числа следующим тривиальным образом: если взять функцию f(s) = [s]×(s-[s]+1), где квадратные скобки означают целую часть числа, начать с s=A, и повторно вычислять s ← f(s), то последовательность целых частей s будет последовательностью простых чисел.
Также был найден ряд, который сходится к этой константе гораздо быстрее, чем средние арифметические начал упомянутой последовательности 2,3,2,3,2,5,2,3,2,3,...
Казалось бы, мало ли чисел и арифметических функций, которые кодируют простые числа? Если взять непрерывную дробь 2+1/(3+1/(5+1/7+1/(11+1/...))) и функцию f(s) = 1/(s-[s]), то будет то же самое, разве что начальная константа
2.3130367... ни в чём другом интересном не замечена.
Попробуем сравнить эти две константы по объективному критерию: какая из них кодирует простые числа более эффективно? Другими словами, если мы начнем вычисления с приближенного значения с данным количеством цифр после запятой, то сколько верных простых чисел мы получим в каждом случае?
Оказывается, для 64-битных чисел с плавающей точкой (около 15 знаков после запятой), 2.313... даёт правильные результаты только вплоть до 23 включительно, а 2.92... - до 53.
Нетрудно видеть, что если разрешать "кусочные" записи функций, то можно любое наперед заданное количество первых простых чисел закодировать непосредственно в функции, например f(x) = if x<3 then x+1 else if x<7 then x+2 else if x<11 then x+4 else 1/(x-[x]), и только "хвост" потребует кодирования - в дробной части, но это неинтересно.
Я нашел функцию — тоже из 5 операций, как и аргентинская — которая вытаскивает из своей начальной константы, заданной 64-битным числом, простые числа аж до 61 включительно. (Попробуйте найти её и вы, это несложно.)
Возникает вопрос, насколько ещё можно улучшить этот результат, пусть и усложняя функцию, но не вводя в неё никаких магических констант и не пользуясь условными операциями.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
