Známs проблема - Známs problem

Графическая демонстрация того, что 1 = 1/2 + 1/3 + 1/11 + 1/23 + 1/31 + 1 / (2 × 3 × 11 × 23 × 31). Каждый ряд из k квадратов со стороной 1 / k имеет общую площадь 1 / k, и все квадраты вместе в точности покрывают больший квадрат с площадью 1. Нижний ряд из 47058 квадратов со стороной 1/47058 слишком мал, чтобы его можно было увидеть на картинке. на рисунке а не показано.

В теория чисел, Проблема Знама спрашивает, какие наборы k целые числа обладают тем свойством, что каждое целое число в наборе является собственный делитель произведения других целых чисел в наборе плюс 1. Задача Знама названа в честь словацкого математика Штефан Знам, который предложил это в 1972 году, хотя другие математики рассматривали аналогичные задачи примерно в то же время. Одна тесно связанная с этим проблема отбрасывает предположение о правильности делителя и в дальнейшем будет называться несобственной проблемой Znám.

Одно решение неправильной проблемы Znám легко найти для любого k: первый k условия Последовательность Сильвестра иметь необходимое имущество. Солнце (1983) показал, что существует по крайней мере одно решение (собственной) проблемы Знама для каждого k ≥ 5. Решение Sun основано на повторении, аналогичном таковому для последовательности Сильвестра, но с другим набором начальных значений.

Проблема Znám тесно связана с Египетские фракции. Известно, что для любого фиксированного k. Неизвестно, есть ли какие-либо решения проблемы Знама, использующие только нечетные числа, и остается несколько других открытых вопросов.

Проблема

Задача Знама спрашивает, какие наборы целых чисел обладают тем свойством, что каждое целое число в наборе является собственный делитель произведения других целых чисел в наборе плюс 1. То есть, учитывая k, какие наборы целых чисел

{ displaystyle {n_ {1}, ldots, n_ {k} }}

есть такие, что для каждого я, п_я делит, но не равно

{ displaystyle { Bigl (} prod _ {j neq i} ^ {n} n_ {j} { Bigr)} + ​​1 quad?}

Тесно связанная проблема касается наборов целых чисел, в которых каждое целое число в наборе является делителем, но не обязательно правильным делителем, одного плюс произведение других целых чисел в наборе. Эта проблема, по-видимому, не упоминалась в литературе, и мы будем называть ее проблемой неправильного Znám. Любое решение проблемы Znám - это также решение неправильной проблемы Znám, но не обязательно наоборот.

История

Задача Знама названа в честь словацкого математика. Штефан Знам, который предложил это в 1972 году. Барбо (1971) поставил неправильную проблему Znám для k = 3 и Морделл (1973), независимо от Znám, нашли все решения неправильной задачи для k ≤ 5. Скула (1975) показал, что проблема Знама неразрешима для k <5, и поручил Й. Янаку найти решение {2, 3, 11, 23, 31} для k = 5.

Примеры

Одно решение k = 5 равно {2, 3, 7, 47, 395}. Несколько расчетов покажут, что

3 × 7 × 47 × 395	+ 1 =	389866,	который делится на 2, но не равен 2,
2 × 7 × 47 × 395	+ 1 =	259911,	который делится на 3, но не равен 3,
2 × 3 × 47 × 395	+ 1 =	111391,	который делится на 7, но не равен 7,
2 × 3 × 7 × 395	+ 1 =	16591,	что делится на 47, но не равно 47, и
2 × 3 × 7 × 47	+ 1 =	1975,	который делится на 395, но не равен ему.

Интересный "промах" для k = 4 - это множество {2, 3, 7, 43}, образованное из первых четырех членов последовательности Сильвестра. Он обладает тем свойством, что каждое целое число в наборе делит произведение других целых чисел в наборе плюс 1, но последний член этого набора равен произведению первых трех членов плюс один, а не является правильным делителем. . Таким образом, это решение неправильной проблемы Znám, но не решение проблемы Znám, как ее обычно определяют.

Связь с египетскими фракциями

Любое решение неправильной проблемы Znám эквивалентно (путем деления на произведение Икс_яs) к решению уравнения

{ displaystyle sum { frac {1} {x_ {i}}} + prod { frac {1} {x_ {i}}} = y,}

куда у а также каждый Икс_я должно быть целым числом, и, наоборот, любое такое решение соответствует решению неправильной проблемы Znám. Однако все известные решения имеют у = 1, поэтому они удовлетворяют уравнению

{ displaystyle sum { frac {1} {x_ {i}}} + prod { frac {1} {x_ {i}}} = 1.}

То есть они приводят к Египетская фракция представление числа один в виде суммы единицы измерения. В нескольких цитируемых статьях по проблеме Знама также изучаются решения этого уравнения. Брентон и Хилл (1988) описать приложение уравнения в топология, к классификации особенности на поверхностях и Domaratzki et al. (2005) описать приложение к теории недетерминированные конечные автоматы.

Количество решений

В качестве Янак и Скула (1978) показал, количество решений для любого k конечно, поэтому имеет смысл подсчитать общее количество решений для каждого k.

Брентон и Василиу подсчитали, что количество решений для малых значений k, начиная с k = 5, образует последовательность

2, 5, 18, 96 (последовательность A075441 в OEIS ).

В настоящее время известно несколько решений k = 9 и k = 10, но неясно, сколько решений остается неоткрытым для этих значений kОднако решений бесконечно много, если k не фиксируется:Цао и Цзин (1998) показали, что существует не менее 39 решений для каждого k ≥ 12, улучшая предыдущие результаты, доказывающие существование меньшего числа решений (Цао, Лю и Чжан 1987, Солнце и Цао 1988 ). Сун и Цао (1988) предположить, что количество решений для каждого значения k монотонно растет с k.

Неизвестно, есть ли какие-либо решения проблемы Знама, использующие только нечетные числа. За одним исключением все известные решения начинаются с 2. Если все числа в решении проблемы Znám или неправильной проблемы Znám основной, их продукт первичное псевдоперфектное число (Буске, Яже и Майерник 2000 ); неизвестно, существует ли бесконечно много решений такого типа.