Comments 5
а как звучит вопрос Эрдёша 124 интересно
Вот только там опечатка на сайте в условии была. Задача не решена. Статус Open.
Статья на хабре в мусор.
А вот это реальность https://www.reddit.com/r/singularity/s/hF6Wrdn6oM
https://www.erdosproblems.com/124 там в комментах появилась подвижка
Сформулируй задачу Эрдеша 124 на русском: https://www.erdosproblems.com/124 Дай простое объяснение задачи и в каких сферах она может пригодиться?
Задача Эрдёша №124 на русском языке
Формулировка задачи:
Для любого целого числа d ≥ 1 и k ≥ 0 пусть P(d,k) обозначает множество целых чисел, которые можно представить как сумму различных степеней , где
.
Пусть
— целые числа, удовлетворяющие условию:
Первый вопрос: Можно ли представить все достаточно большие целые числа в виде суммы
,
где {
} и
?
Второй вопрос: Если дополнительно (наибольший общий делитель равен 1), то для любого
, можно ли представить все достаточно большие целые числа в виде суммы
,
где {0,1} и
?
Простое объяснение задачи
Представьте, что у вас есть несколько систем счисления с разными основаниями (3, 4, 5 и т.д.). В каждой такой системе вы можете записать число, используя только цифры 0 и 1 (как в двоичной системе, но с другим основанием).
Например, в системе с основанием 3 числа из — это числа вроде:
и т.д.
Спрашивается: если взять несколько таких систем счисления (с основаниями ), удовлетворяющих определенному математическому условию, можно ли составить любое достаточно большое число, просто складывая по одному числу из каждой системы (или не брать его вообще — отсюда коэффициенты 0 или 1)?
Второй вопрос добавляет ограничение: мы можем использовать только старшие разряды (начиная с -го) в каждой системе счисления, но требует, чтобы основания были "взаимно простыми" в совокупности.
Сферы применения
Эта задача имеет значение в нескольких областях:
1. Теория чисел — исследование свойств целых чисел, их представлений и аддитивных структур. Решение может привести к новым методам анализа числовых последовательностей.
2. Комбинаторика — задача связана с покрытием множества целых чисел комбинациями специальных подмножеств. Это имеет отношение к задачам упаковки и покрытия.
3. Компьютерная арифметика — понимание различных систем представления чисел помогает оптимизировать вычисления, особенно в специализированных процессорах и криптографических алгоритмах.
4. Кодирование информации — методы представления чисел как сумм специальных последовательностей используются в теории кодирования, сжатии данных и коррекции ошибок.
5. Криптография — аддитивные представления чисел лежат в основе некоторых криптографических систем, особенно основанных на сложности разложения чисел на специальные суммы.
6. Алгоритмическая теория — задача связана с эффективными алгоритмами представления чисел и имеет приложения в компьютерной алгебре.
Эта задача интересна тем, что соединяет абстрактную теорию чисел с практическими вычислительными вопросами, и её решение может привести как к теоретическим прорывам, так и к практическим алгоритмическим улучшениям.
«Математический сверхинтеллект» Aristotle решил 30-летнюю задачу Эрдёша