Задача Танежи: новый этап развития математики? / forpes.ru

Главная
Задача Танежи: новый этап развития математики?

Задача Танежи: новый этап развития математики? +42

17.05.2020 16:17

stefanov94 30 14900 Источник

Введение

Математика XXI века принципиально отличается от античной. И речь идёт не просто о новых достижениях в геометрии и арифметике — науках, базовые принципы для которых сформированы тысячелетия назад. С появлением вычислительной техники изменился приоритет, и теория чисел из области «упражнений для развития ума» превратилась в науку, от достижений которой зависит мировая экономика.

По задаче о простых близнецах, по ABC-гипотезе, проблеме Гольдбаха-Виноградова и некоторым другим важным математическим проблемам новые научно-популярные публикации выходят ежедневно. С одной стороны, эти задачи выдержали проверку временем, с другой — регулярный пиар поддерживается шестизначными наградами за решение каждой. Но 4 года назад в трудах одного бразильского математика была, косвенно и незаметно для него самого, поднята проблема, которая может стать целью и смыслом жизни для математиков нынешнего столетия. Речь идёт о классификации трансцендентных чисел относительно замыкания конечных множеств алгебраических чисел.

Задача Индер Танежи

Общие сведения

Индер Танежа — бразильский математик-популяризатор, посвятивший большую часть жизни магическим квадратам, треугольным числам и другим занимательным задачам. Он никогда не брался за нерешённые проблемы столетия, не сделал профессионального вклада в изучение свойств натурального ряда, но именно в его любительских исследованиях были подняты вопросы, ответы на которые не способна дать современная математика.

Всё началось с серии публикаций в Реддит, где Танежа рассуждал о возможности представить любое натуральное число меньше некоторой границы при помощи ограниченного числа операндов. Сама идея не нова, и в советских изданиях для олимпиадников периодически возникали такие вопросы:

Представьте число 1958 при помощи семи двоек, расставляя операторы сложения, вычитания, умножения и возведения в степень

Ответом будет:

$display$

Подбор необычного представления для текущего года стал традицией для математических факультетов многих вузов и укрепился в литературе. Так же было с задачами о простоте больших чисел: пару веков назад числами Мерсенна и Ферма занимались из спортивного интереса, а теперь первые обеспечивают криптографию надежными закрытыми ключами. И вот 4 года назад появилась публикация, в которой рассматривались возможные пути решения задачи о представлении натурального числа с использованием одной цифры, а также упорядоченные представления со всеми цифрами кроме нуля. Например:

$display$

Среди допустимых операций изначально были:

конкатенация: 2||3=23
сложение: 2+3=5
вычитание: 2-3=-1
умножение: 2*3=6
унарный минус: -(2+3)=-5

Танежа считал деление бесполезным, так как числа до тысячи можно было представить подобно примеру выше без дополнительных операций. Но в дальнейшем всё же добавил в необходимый минимум возведение в степень (включая степени с дробно-рациональными, иррациональными и комплексными показателями, если таковые возникали в промежуточных вычисления и приводили к целому результату в конце расчётов) и деление.

Спустя год вышел объемный труд с таблицей представлений чисел от 1 до 11 111 при помощи цифр в порядке возрастания и убывания. Указанного ранее набора операций оказалось достаточно для представления всех чисел цифрами в убывающем порядке, а также для представления 11 110 чисел из списка в возрастающем порядке.

В поисках одобрения, Индер рассылает на почту профессиональным математикам и блогерам-популяризаторам свой труд с личными комментариями. В числе прочих получателей оказывается Мэт Паркер — лицо Австралийского проекта «Математический стендап» и один из участников Ютуб-проекта «Numberphile». Видеоролик об особенном числе 10958 (единственном пробеле в таблице разложений Танежи) стал достаточно популярен для того, чтобы попытки решения и научно-популярные статьи о Танеже стали иногда появляться по всему миру.

В Россию задачу «завезли» Mad Astronomer и неизвестный автор с Яндекс.Дзен. Последний добавил новость о премии в 5000$ за нахождение решения для числа 10958. Однако ни Танежа, ни Паркер, ни сотрудники MIT о публичной награде ничего не знают. За три года вышло всего две любительские работы, предпринимающие хоть какие-то попытки найти решения. Первая опубликована экс-участником проекта TedX и касается вопроса оценки общего количества вычислимых выражений, построенных по правилам Танежи, и времени работы переборного алгоритма. Вторая направлена на «слабое расширение» задачи, а именно:

Представить все числа от 1 до 11 111 111 при помощи цифр в порядке возрастания (одну цифру можно использовать один раз и каждая цифра должна быть использована), расставляя операторы: а) бинарные: сложение, вычитание, умножение, деление, возведение в степень; б) унарные: унарный минус, факториал, квадратный корень

Такого ослабления, со слов автора исследования, оказалось достаточно для представления 11 111 105 чисел. Оригинальный видеоотчёт:

Попытки точного аналитического доказательства непредставимости числа 10958 в необходимом нам виде не предпринимались, во всяком случае информации о них нет ни на одном из доступных мне иностранных языков. О невозможности переборного решения и особенностях числа 10958 будет подробнее рассказано ниже.

Точная формулировка и первые обобщения

Вольная формулировка автора задачи породила множество ошибочных решений, опирающихся на неверную трактовку условия. Самые частые ошибки:

использование «внешней» конкатенации: составление новых операторов из цифр начального вектора допустимо, но конкатенация в общем виде как дописывание одного числа справа от другого — запрещена. Примеры: $inline$ — можно, $inline$ — нельзя
округление: решение задачи Танежи в целых числах означает не только использование целочисленного начального вектора, но и получение целого результата на выходе. Примеры: $inline$ — можно, $7 \approx (1+2/3)*4=20/3$ — нельзя
использование дополнительных операндов: при выполнении операции возведения в степень некоторые авторы рассматривают исходный набор цифр как допустимые основания степени и прибегают к произвольным показателям. Примеры: $inline$ — можно, $inline$ — нельзя

Опишем процесс проверки и принятия решения задачи Танежи для некоторого числа. Пусть для некоторого вектора комплексных (в общем случае) чисел

$inline$ предложена тройка

$inline$ , где

$inline$ и

$inline$ — последовательные натуральные числа,

$inline$ ;

$inline$ — код оператора — натуральное число от 1 до 7, тогда итерацией

$inline$ над вектором

$inline$ будем называть процесс, результатом которого является вектор длины

$inline$ , а именно:

вектор $(c_1, c_2, ... , с_{ind-1}, c_{ind}||c_{ind+1}, c_{ind+2}, ... , c_k)$ для $inline$
вектор $(c_1, c_2, ... , с_{ind-1}, c_{ind}+c_{ind+1}, c_{ind+2}, ... , c_k)$ для $inline$
вектор $(c_1, c_2, ... , с_{ind-1}, |c_{ind}-c_{ind+1}|, c_{ind+2}, ... , c_k)$ для $inline$
вектор $(c_1, c_2, ... , с_{ind-1}, c_{ind}*c_{ind+1}, c_{ind+2}, ... , c_k)$ для $inline$
вектор $(c_1, c_2, ... , с_{ind-1}, c_{ind}/c_{ind+1}, c_{ind+2}, ... , c_k)$ для $inline$
вектор $(c_1, c_2, ... , с_{ind-1}, c_{ind}^{c_{ind+1}}, c_{ind+2}, ... , c_k)$ для $inline$
вектор $(c_1, c_2, ... , с_{ind-1}, c_{ind}^{-(c_{ind+1})}, c_{ind+2}, ... , c_k)$ для $inline$

Пусть дан начальный вектор

$inline$ из девяти элементов, равных своим порядковым номерам. Тогда говорят что для некоторого целого числа

$inline$ существует решение задачи Танежи в восходящем порядке, если существует последовательность (которую мы будем называть выводом для числа а):

$(op_1, ind_1,{ind_1}+1)$ — итерация над начальным вектором, результат которой — вектор (1)

$(op_2, ind_2,{ind_2}+1)$ — итерация над вектором (1), результат которой — вектор (2)
…

$(op_8, ind_8,{ind_8}+1)$ — итерация над вектором (7), результат которой — вектор (8),

такая, что вектор (8) равен вектору

$inline$ либо вектору

$inline$ и для каждой итерации со значением оператора равным единицы верно, что элементы с номерами

$ind_m и {ind_m}+1$ не являются преобразованными. При выполнении некоторой итерации будем называть элемент некоторого нового вектора (x) атомарным, если значение этого элемента было взято из исходного вектора или получено конкатенацией атомарных значений. Будем называть элемент некоторого нового вектора (y) преобразованным, если он является результатом выполнения одной из шести бинарных арифметических операций с номерами от 2 до 7, на одной из итераций, предшествующей данной.

Для каждого вектора количество операций и возможностей выбора пар значений

$inline$ ограничен, количество итераций, предшествующих получению результата — числа а — тоже ограничено. Следовательно, существует конечное количество целых чисел, для которых задача Танежи в восходящем порядке имеет решение. Также можно на примерах показать, что разные последовательности итераций не всегда приводят к разным результатам, а также — что не все такие последовательности имеют целый или хотя бы действительный результат. Кроме того, статистические данные, в частности — результаты работы Билла Амса, показывают, что число различных выводимых рациональных значений может не превышать удвоенного числа различных целых значений. Поэтому первым важным обобщением задачи Танежи является следующий набор вопросов:

Сколько различных выводов, имеющих целочисленный результат, существует?
Сколько различных по модулю целых чисел выводимо?
Сколько различных комплексных значений выводимо?
Верно ли, что количество различных рациональных значений, выводимых и по модулю не превосходящих некоторое целое число k, не превосходит удвоенного количества различных выводимых целых, по модулю не превосходящих k? Для каких k? Верно ли в общем виде?

Верно также, что при выводе целого значения, таком что на некоторых промежуточных итерациях вектор содержит иррациональные и комплексные значения, вероятность получить различные итоговые значения уменьшается, так как ряд операций (сложение иррационального с рациональным, возведение рационального в иррациональную степень) не возвращают рациональный результат, а потому количество вариантов уменьшается. Поэтому возникает ещё одно обобщение:

Доказать или опровергнуть, что для всякого целого числа а справедливо: если задача Танежи в восходящем порядке для числа а не имеет такого решения, в котором все итерации вывода выполняются над векторами, не имеющими иррациональных элементов, то она не имеет решения вовсе.

Ход решения

Для начала реализуем функцию подсчёта количества всех выводов, которые могут считаться решениями для некоторого а — не обязательно целого (т.е. всех выводов, для которых операция с кодом 1 выполняется только над атомарными операндами). Язык реализации — C#.

Получим:

static long Num_0(bool[] A)
        {
            if (A.Length == 1)
            {
                return 1;
            }
            else
            {
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                {
                    bool[] B = new bool[A.Length - 1];
                    for (int j = 0; j < i; j++)
                        B[j] = A[j];
                    for (int j = i + 1; j < A.Length-1; j++)
                        B[j] = A[j+1];
                    if (A[i] && A[i + 1])
                    {
                        B[i] = true; //B[i] result for A[i]||A[i+1]
                        res += Num_0(B);
                    }
                    B[i] = false; //B[i] result for A[i] op A[i+1], op!=||
                    res += 6 * Num_0(B);
                }
                return res;
            }
        }

        static void Test_0(int range = 9, bool wait = true)
        {
            Console.WriteLine("Test 0 for [1.." + Convert.ToString(range) + "]");
            bool[] A = new bool[range];
            for (int i = 0; i < range; i++)
                A[i] = true; //each basic element is concatenable 
            string s = "Eq count: " + Convert.ToString(Num_0(A));
            Console.WriteLine(s);
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
        }

Результат работы программы:

Test 0 for [1..9]
Eq count: 112274877312

Мы получили около 112 млрд вариантов. По построению, многие варианты вывода будут не просто производить одно и то же значение, но и иметь одно и то же инфиксное представление (получать искомое число, используя те же операторы, над теми же операндами, но в другом порядке). Например, если первая итерация преобразовала элементы

$inline$ и

$inline$ в

$inline$ , а вторая элементы

$inline$ и

$inline$ в

$inline$ и если первая итерация преобразовала элементы

$inline$ и

$inline$ в

$inline$ , а вторая элементы

$inline$ и

$inline$ в

$inline$ , то в обоих случаях мы получим инфиксное выражение:

$display$

Опишем некоторые классы выводов с повторяющимся результирующим инфиксным представлением:

пусть оператор сложения выполняется над операндами, один из которых является результатом сложения, тогда можно ограничиться итерациями, в которых правый операнд не является результатом сложения и результат прошлых вычислений является элементом, индекс которого не более $inline$ текущей итерации. Так мы с одной стороны исключаем $inline$ в пользу $inline$ , а с другой для выражения $inline$ исключаем вариант вычисления $inline$ до вычисления $inline$ , исключая таким образом как минимум один повтор
сложение и вычитание результатов сложения и вычитания: аналогично предыдущему пункту, но с ограничениями для унарных операций перед показателями степеней
пусть основание степени является результатом возведения в степень, тогда можно не проверять вариант с оператором 7, на основании тождества: ${({a^b})}^c={{(a^{-b}})}^{-с}$ , зная что по построению наличие вектора, аналогичного входному вектору текущей итерации, за исключением значения $a^{-b}$ вместо $inline$ гарантировано
умножение и деление можно БОО (Без Ограничения Общности) выполнять строго слева направо, т.е. только когда правые операнды не являются результатами умножения или деления. Следует из тождеств: $inline$ и $inline$

Реализация операторов с учётом этих классов не гарантирует отсутствие повторов среди инфиксных выражений, но БОО позволяет отбросить часть таких повторов.

Значения элементов векторов для некоторых выводов не вычислимы, что связано с ограниченным размером машинного слова. С использованием типа данных BigInteger можно будет вычислить часть таких значений. Объявим структуру данных для элемента вектора. В ней буду два длинных целых, представляющих числитель и знаменатель некоторого рационального числа. Для каждого оператора напишем ряд дополнительных условий, гарантирующих получение рационального результата без переполнения. Добавив в эту же структуру коды операций и ограничения по классам повторяющихся инфиксных значений, получим функцию Num_1, которая БОО подсчитывает количество выводов, имеющих различное инфиксное представление. Очевидно, что ни одно решение не будет потеряно, в том смысле, что если для некоторого числа а существовал минимум 1 вывод в Num_0, то для него будет существовать хотя бы один вывод в Num_1.

Получим

        public struct NumEx
        {
            public NumEx(BigInteger x, BigInteger y, int opcode)
            {
                X = x;
                Y = y;
                OpCode = opcode;
                Eq = X.ToString();
            }

            public BigInteger X { get; set; }
            public BigInteger Y { get; set; }
            public int OpCode { get; set; }

            public string Eq { get; set; }

            public override string ToString() => $"({X}/{Y}) [{Eq}]";
        }

        static long Num_1(NumEx[] A, int pos = -1)
        {
            if (A.Length == 1)
                return 1;
            else
            {
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                    if ((A[i + 1].OpCode != 0) || (pos == -1) || (pos >= i))
                    {
                        NumEx[] B = new NumEx[A.Length - 1];
                        for (int j = 0; j < i; j++)
                            B[j] = A[j];
                        for (int j = i + 1; j < A.Length - 1; j++)
                            B[j] = A[j + 1];
                        if ((A[i].OpCode < 2) && (A[i + 1].OpCode == 0))
                        {
                            // concat
                            B[i].OpCode = 1;
                            res += Num_1(B, i);
                        }
                        if (A[i + 1].OpCode != 2)
                        {
                            //+ -
                            B[i].OpCode = 2;
                            res += 2 * Num_1(B, i);
                        }
                        if (A[i + 1].OpCode != 3)
                        {
                            //* /
                            B[i].OpCode = 3;
                            res += 2 * Num_1(B, i);
                        }
                        {
                            //^ ^-
                            B[i].OpCode = 4;
                            if (A[i].OpCode == 4)
                                res += Num_1(B, i);
                            else
                                res += 2 * Num_1(B, i);
                        }
                    }
                return res;
            }
        }

        static void Test_1(int range = 9, bool wait = true)
        {
            Console.WriteLine("Test 1 for [1.." + Convert.ToString(range) + "]");
            NumEx[] A = new NumEx[range];
            for (int i = 0; i < range; i++)
                A[i] = new NumEx(i + 1, 1, 0);
            string s = "Eq count: " + Convert.ToString(Num_1(A));
            Console.WriteLine(s);
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
        }

Результат работы нового теста:

Test 1 for [1..9]
Eq count: 4762796551

Получили около 4762 млн выражений.

В структуре данных для элемента вектора также создадим строковое поле, в котором будет накапливаться инфиксное представление вывода. В конце цепочки итераций (при рекурсивном вызове функции Num_2 с массивом длины 1) будем проверять сократимость дроби, представляющей элемент этого вектора и сравнивать результат деления числителя на знаменатель с некоторым числом. Введя переменную счётчик, получим процедуру, результатом работы которой будет количество выводов числа val с заданными условиями. Для чисел

$inline$ и

$inline$ (где

$inline$ — простое) получим:

Исходный код

        public struct NumEx
        {
            public NumEx(BigInteger x, BigInteger y, int opcode)
            {
                X = x;
                Y = y;
                OpCode = opcode;
                Eq = X.ToString();
            }

            public BigInteger X { get; set; }
            public BigInteger Y { get; set; }
            public int OpCode { get; set; }

            public string Eq { get; set; }

            public override string ToString() => $"({X}/{Y}) [{Eq}]";
        }
        static long PowLimit = 27;
        static long SolLimit = 400;
        static long SolCount = 0;
        static long Num_2(NumEx[] A, long val, int pos = -1)
        {
            if (A.Length == 1)
            {
                if ((A[0].X % A[0].Y) == 0)
                {
                    BigInteger B = BigInteger.Divide(A[0].X, A[0].Y);
                    if (B == new BigInteger(val))
                    {
                        SolCount++;
                        if (SolCount <= SolLimit)
                        {
                            Console.WriteLine(Convert.ToString(val) + " = " + A[0].Eq);
                        }
                    }
                }
                return 1;
            }
            else
            {
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                    if ((A[i + 1].OpCode != 0) || (pos == -1) || (pos >= i))
                    {
                        NumEx[] B = new NumEx[A.Length - 1];
                        for (int j = 0; j < i; j++)
                            B[j] = A[j];
                        for (int j = i + 1; j < A.Length - 1; j++)
                            B[j] = A[j + 1];

                        if ((A[i].OpCode < 2) && (A[i + 1].OpCode == 0))
                        {
                            // concat
                            int p = A[i + 1].X.ToString().Length;
                            B[i].X = BigInteger.Add(A[i + 1].X, BigInteger.Multiply(A[i].X,
                                BigInteger.Pow(new BigInteger(10), p)));
                            B[i].Y = 1;
                            B[i].OpCode = 1;
                            B[i].Eq = A[i].Eq + A[i + 1].Eq;
                            res += Num_2(B, val, i);
                        }

                        if ((A[i + 1].X % A[i + 1].Y) == 0)
                        {
                            //pow
                            BigInteger pow = BigInteger.Divide(A[i + 1].X, A[i + 1].Y);
                            if (pow <= PowLimit)
                            {
                                if (pow.IsZero)
                                {
                                    B[i].X = 1;
                                    B[i].Y = 1;
                                    B[i].OpCode = 4;
                                    string s1 = A[i].Eq;
                                    string s2 = A[i + 1].Eq;
                                    if (A[i].OpCode > 1)
                                        s1 = "(" + s1 + ")";
                                    if (A[i+1].OpCode > 1)
                                        s2 = "(" + s2 + ")";
                                    B[i].Eq = s1 + "^" + s2;
                                    res += Num_2(B, val, i);
                                }
                                else
                                {
                                    //^
                                    int p = (int)pow;
                                    BigInteger val1 = BigInteger.Pow(A[i].X, p);
                                    BigInteger val2 = BigInteger.Pow(A[i].Y, p);
                                    B[i].X = val1;
                                    B[i].Y = val2;
                                    B[i].OpCode = 4;
                                    string s1 = A[i].Eq;
                                    string s2 = A[i + 1].Eq;
                                    if (A[i].OpCode > 1)
                                        s1 = "(" + s1 + ")";
                                    if (A[i + 1].OpCode > 1)
                                        s2 = "(" + s2 + ")";
                                    B[i].Eq = s1 + "^" + s2;
                                    res += Num_2(B, val, i);
                                    //^-
                                    if ((!val1.IsZero) && (A[i].OpCode != 4))
                                    {
                                        B[i].X = val2;
                                        B[i].Y = val1;
                                        B[i].OpCode = 4;
                                        s1 = A[i].Eq;
                                        s2 = A[i + 1].Eq;
                                        if (A[i].OpCode > 1)
                                            s1 = "(" + s1 + ")";
                                        if (A[i + 1].OpCode > 1)
                                            s2 = "(" + s2 + ")";
                                        B[i].Eq = s1 + "^-" + s2;
                                        res += Num_2(B, val, i);
                                    }
                                }
                            }
                        }
                        if ((A[i + 1].X != 0) && (A[i + 1].OpCode != 3))
                        {
                            //div
                            B[i].X = BigInteger.Multiply(A[i].X, A[i + 1].Y);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].X);
                            B[i].OpCode = 3;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1)||(s2.ToArray()[0]=='-'))
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1+ "/" + s2;
                            res += Num_2(B, val, i);
                        }
                        if (A[i + 1].OpCode != 3)
                        {
                            //mul
                            B[i].X = BigInteger.Multiply(A[i].X, A[i + 1].X);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 3;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "*" + s2;
                            res += Num_2(B, val, i);
                        }
                        if (A[i + 1].OpCode != 2)
                        {
                            //add
                            B[i].X = BigInteger.Add(BigInteger.Multiply(A[i].X, A[i + 1].Y),
                                BigInteger.Multiply(A[i].Y, A[i + 1].X));
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 2;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (s2.ToArray()[0] == '-')
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "+" + s2;
                            res += Num_2(B, val, i);
                            //sub -abs
                            B[i].X = 
                                BigInteger.Subtract(BigInteger.Multiply(A[i].X, A[i + 1].Y),
                                BigInteger.Multiply(A[i].Y, A[i + 1].X));
                            bool neg = B[i].X < BigInteger.Zero;
                            if (neg) B[i].X = BigInteger.Abs(B[i].X);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 2;
                            s1 = A[i].Eq;
                            s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            if (neg)
                                B[i].Eq = "(-" + s1 + ")+" + s2; //?
                            else
                                B[i].Eq = s1 + "-" + s2;
                            res += Num_2(B, val, i);
                        }
                    }

                return res;
            }
        }

        static void Test_2(long val, int range = 9, bool wait = true, long out_lim = 400, long pow_lim = 27)
        {
            Console.WriteLine("Test 2 for [1.." + Convert.ToString(range) + "]");
            NumEx[] A = new NumEx[range];
            for (int i = 0; i < range; i++)
                A[i] = new NumEx(i + 1, 1, 0);
            SolCount = 0;
            SolLimit = out_lim;
            PowLimit = pow_lim;
            Console.WriteLine("Max power: " + Convert.ToString(PowLimit) + ", output limit: " 
                + Convert.ToString(SolLimit));
            string s = "Eq count: " + Convert.ToString(Num_2(A, val));
            Console.WriteLine(s);
            Console.WriteLine("Total solutions count for " + Convert.ToString(val) + ": " 
                + Convert.ToString(SolCount));
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
        }

Вывод будет содержать количество выводов, результат которых удалось точно вычислить, а также инфиксные выражения для всех выводов их числа вычисленных, которые закончились с получением значения val.

Результат

Test 2 for [1..9]
Max power: 27, output limit: 400
Eq count: 957441620
Total solutions count for 10958: 0

Test 2 for [1..9]
Max power: 27, output limit: 400
5479 = ((1+2*(345-6)+7)*8)-9
5479 = ((((-((-1)+23))+((4*5)*6))*7)*8)-9
5479 = 1+(2*3)*((((4*5)*6)-7)*8+9)
5479 = (((((-1)+(2^3))*((4*5)-6))*7)*8)-9
5479 = ((((1+2*3)*((4*5)-6))*7)*8)-9
5479 = ((((((-1)+(2^3))/4)*56)*7)*8)-9
5479 = (((((1+2*3)/4)*56)*7)*8)-9
5479 = ((((1^2+3/4)*56)*7)*8)-9
5479 = ((((1^-2+3/4)*56)*7)*8)-9
5479 = (((((-1)+2+3/4)*56)*7)*8)-9
5479 = ((((1*2)*((-(3+4))+56))*7)*8)-9
5479 = ((((1*2)*((-(3+4))+56))*7)*8)-9
5479 = 1*((((2*((-(3+4))+56))*7)*8)-9)
5479 = ((123-4+567)*8)-9
5479 = (-(1*2))+((34+567+8)*9)
5479 = (-(1*2))+((34+567+8)*9)
5479 = 1*((-2)+((34+567+8)*9))
5479 = ((((1/2+3)*4)*(56-7))*8)-9
5479 = (((1*2+3*4)*(56-7))*8)-9
5479 = (((1*(2+3*4))*(56-7))*8)-9
5479 = 1*((((2+3*4)*(56-7))*8)-9)
5479 = ((((1*2)*(3+4))*(56-7))*8)-9
5479 = 1*((((2*(3+4))*(56-7))*8)-9)
5479 = 1+(2+3^4)*(56-7+8+9)
5479 = ((((1*2)*34+5*6)*7)*8)-9
5479 = (((1*(2*34+5*6))*7)*8)-9
5479 = 1*((((2*34+5*6)*7)*8)-9)
5479 = (((((1/2)^-(3+4))-(5*6))*7)*8)-9
5479 = (((((1*2)^(3+4))-(5*6))*7)*8)-9
5479 = ((((1*(2^(3+4)))-(5*6))*7)*8)-9
5479 = (((1*((2^(3+4))-(5*6)))*7)*8)-9
5479 = 1*(((((2^(3+4))-(5*6))*7)*8)-9)
5479 = ((((1/(2^-(3+4)))-(5*6))*7)*8)-9
5479 = ((((-1)+((2+3+4)*(5+6)))*7)*8)-9
5479 = (-(1*2))+(((-(3+4))+(((5+6)*7)*8))*9)
5479 = (-(1*2))+(((-(3+4))+(((5+6)*7)*8))*9)
5479 = 1*((-2)+(((-(3+4))+(((5+6)*7)*8))*9))
5479 = (((12/3)*4)*(5*67+8))-9
5479 = (((12/3)*4)*(5*67+8))-9
5479 = (((12/3)*4)*(5*67+8))-9
5479 = (((1^2+3)*4)*(5*67+8))-9
5479 = (((1^2+3)*4)*(5*67+8))-9
5479 = ((((-(1^2))+3)^4)*(5*67+8))-9
5479 = ((((-(1^2))+3)^4)*(5*67+8))-9
5479 = (((1^2+3)*4)*(5*67+8))-9
5479 = ((((-(1^2))+3)^4)*(5*67+8))-9
5479 = (((1^-2+3)*4)*(5*67+8))-9
5479 = (((1^-2+3)*4)*(5*67+8))-9
5479 = ((((-(1^-2))+3)^4)*(5*67+8))-9
5479 = ((((-(1^-2))+3)^4)*(5*67+8))-9
5479 = (((1^-2+3)*4)*(5*67+8))-9
5479 = ((((-(1^-2))+3)^4)*(5*67+8))-9
5479 = ((((-1)+2+3)*4)*(5*67+8))-9
5479 = ((((-1)+2+3)*4)*(5*67+8))-9
5479 = ((((-((-1)+2))+3)^4)*(5*67+8))-9
5479 = ((((-((-1)+2))+3)^4)*(5*67+8))-9
5479 = ((((-1)+2+3)*4)*(5*67+8))-9
5479 = ((((-((-1)+2))+3)^4)*(5*67+8))-9
5479 = ((((-1)+((2+3)^4))-5+67)*8)-9
5479 = (-1)+(2^3)+((4+5+67)*8)*9
5479 = (-1)+(2^3)+((4+5+67)*8)*9
5479 = 1+(2/3+(4+5+67)*8)*9
5479 = 1+2*3+((4+5+67)*8)*9
5479 = 1+2*3+((4+5+67)*8)*9
5479 = 1+(2/3+(4+5+67)*8)*9
5479 = (-1)+(2^3)+((4+5+67)*8)*9
5479 = 1+2*3+((4+5+67)*8)*9
5479 = (((12/3)*4)*(5*67+8))-9
5479 = (((1^2+3)*4)*(5*67+8))-9
5479 = ((((-(1^2))+3)^4)*(5*67+8))-9
5479 = (((1^-2+3)*4)*(5*67+8))-9
5479 = ((((-(1^-2))+3)^4)*(5*67+8))-9
5479 = ((((-1)+2+3)*4)*(5*67+8))-9
5479 = ((((-((-1)+2))+3)^4)*(5*67+8))-9
5479 = (1*2)*(3+4*(5+678))+9
5479 = (1*2)*(3+4*(5+678))+9
5479 = (1*2)*(3+4*(5+678))+9
5479 = (1*2)*(3+4*(5+678))+9
5479 = 1*(2*(3+4*(5+678))+9)
5479 = 1+(2+3^4)*((5*(6+7))-8+9)
5479 = 1+(2+3^4)*((5*(6+7))-8+9)
5479 = 1+(2+3^4)*((5*(6+7))-8+9)
5479 = (-(1*2))+(((34-5)*(6+7+8))*9)
5479 = (-(1*2))+(((34-5)*(6+7+8))*9)
5479 = 1*((-2)+(((34-5)*(6+7+8))*9))
5479 = (-1)+((2+3)*(4^5+(((-6)+7)*8)*9))
5479 = (-1)+((2+3)*(4^5+(((-6)+7)*8)*9))
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = 1+2*((34-5+6)*78+9)
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = 1*((-2)+(((3^4)-5)*((-6)+78)))+9
5479 = 1*((-2)+(((3^4)-5)*((-6)+78))+9)
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = 1*((-2)+(((3^4)-5)*((-6)+78)))+9
5479 = 1*((-2)+(((3^4)-5)*((-6)+78))+9)
5479 = 1+(((2/3)*(4^5+6))-78)*9
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = (-(1*2))+(((3^4)-5)*((-6)+78))+9
5479 = 1*((-2)+(((3^4)-5)*((-6)+78)))+9
5479 = 1*((-2)+(((3^4)-5)*((-6)+78))+9)
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = 1*((-2)+(((3*4)-5)*((-6)+789)))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = 1*((-2)+(((3*4)-5)*((-6)+789)))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = (-(1*2))+(((3*4)-5)*((-6)+789))
5479 = 1*((-2)+(((3*4)-5)*((-6)+789)))
5479 = (1+(2*3+4^5)*6)-(78*9)
5479 = (1+(2*3)*(4^5+6))-(78*9)
5479 = (-(1*2))+((3+4+56)*(78+9))
5479 = (-(1*2))+((3+4+56)*(78+9))
5479 = (-(1*2))+((3+4+56)*(78+9))
5479 = 1*((-2)+((3+4+56)*(78+9)))
5479 = 1+(2+3^4)*((-5)+6+7*8+9)
5479 = 1+(2+3^4)*((-5)+6+7*8+9)
5479 = 1+(2+3^4)*((-5)+6+7*8+9)
5479 = 1+2*(3+456*((7+8)-9))
5479 = 1+((2+3^4)*(5+6))*((7+8)-9)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = (-((1/2)^-(3+4)))+((56+7)*89)
5479 = (-((1*2)^(3+4)))+((56+7)*89)
5479 = (-((1/2)^-(3+4)))+((56+7)*89)
5479 = (-((1/2)^-(3+4)))+((56+7)*89)
5479 = (-((1*2)^(3+4)))+((56+7)*89)
5479 = (-((1*2)^(3+4)))+((56+7)*89)
5479 = (-(1*(2^(3+4))))+((56+7)*89)
5479 = (-(1*(2^(3+4))))+((56+7)*89)
5479 = 1*((-(2^(3+4)))+((56+7)*89))
5479 = (-(1/(2^-(3+4))))+((56+7)*89)
5479 = (-(1/(2^-(3+4))))+((56+7)*89)
5479 = (-((1/2)^-(3+4)))+((56+7)*89)
5479 = (-((1*2)^(3+4)))+((56+7)*89)
5479 = (-(1*(2^(3+4))))+((56+7)*89)
5479 = 1*((-(2^(3+4)))+((56+7)*89))
5479 = (-(1/(2^-(3+4))))+((56+7)*89)
5479 = (-((1/2)^-(3+4)))+((56+7)*89)
5479 = (-((1*2)^(3+4)))+((56+7)*89)
5479 = (-(1*(2^(3+4))))+((56+7)*89)
5479 = 1*((-(2^(3+4)))+((56+7)*89))
5479 = (-(1/(2^-(3+4))))+((56+7)*89)
5479 = 1+(2+3^4)*((-((5*6)-7))+89)
5479 = 1+(2+3^4)*((-((5*6)-7))+89)
5479 = 1+(2+3^4)*((-((5*6)-7))+89)
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4+(5+6*7)*89)
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4+(5+6*7)*89)
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4+(5+6*7)*89)
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4+(5+6*7)*89)
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4+(5+6*7)*89)
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = ((1/2)/3)^-4+(5+6*7)*89
5479 = ((1*2)*3)^4+(5+6*7)*89
5479 = (1+2+3)^4+(5+6*7)*89
5479 = 1*((2*3)^4)+(5+6*7)*89
5479 = 1*((2*3)^4+(5+6*7)*89)
5479 = 1/((2*3)^-4)+(5+6*7)*89
5479 = (((-((-1)+(2^3)))+(4^5))*6)-(7*89)
5479 = (((-(1+2*3))+(4^5))*6)-(7*89)
5479 = 1+2*((((3^(4+5))-6)/7)-(8*9))
5479 = 1+(2+3^4)*((-((-((-5)+6))+7))+(8*9))
5479 = 1+(2+3^4)*((-((-((-5)+6))+7))+(8*9))
5479 = 1+(2+3^4)*((-((-((-5)+6))+7))+(8*9))
5479 = ((((12^3)/4)-5)*(6+7))-(8*9)
5479 = (-1)+((2+3)*(4^(5^((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5/((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5*((-6)+7))+8*9))
5479 = (-1)+((2+3)*((4^5)^((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)/((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)*((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)^((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)^((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)/((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)/((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)*((-6)+7)+8*9))
5479 = (-1)+((2+3)*((4^5)*((-6)+7)+8*9))
5479 = (-1)+((2+3)*(4^(5^((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5^((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5^((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5/((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5/((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5/((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5*((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5*((-6)+7))+8*9))
5479 = (-1)+((2+3)*(4^(5*((-6)+7))+8*9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (-12)+(((-(3*4))+(5*67))*(8+9))
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = ((12*((3^4)-5))*6+7)^((-8)+9)
5479 = ((12*((3^4)-5))*6+7)/((-8)+9)
5479 = ((12*((3^4)-5))*6+7)*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)^((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)/((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)^((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)/((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)^((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)/((-8)+9)
5479 = ((12^3)*(4-(5/6))+7)*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12*((3^4)-5))*6+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12^3)*(4-(5/6))+7^((-8)+9)
5479 = (12*((3^4)-5))*6+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12^3)*(4-(5/6))+7/((-8)+9)
5479 = (12*((3^4)-5))*6+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
5479 = (12^3)*(4-(5/6))+7*((-8)+9)
Eq count: 957441620
Total solutions count for 5479: 356

Итак, для ограничения по целым степеням не более 27 по модулю, вычислимыми оказались результаты ~957 млн выводов и среди них 356 являются выводами числа 5479 и ни один вывод (а соответственно ни один вывод с операциями сложения, вычитания, конкатенации, умножения и деления, а также некоторые выводы с этими же операциями и некоторыми целыми степенями) не является выводом числа 10958. В чем его особенность?

Призраки и тени

Для задачи, аналогичной задаче Танежи в восходящем порядке, но с начальными векторами длины 8, такими как

$inline$ и

$inline$ количество вариантов меньше, а с иррациональными, комплексными и длинными целыми значениями элементов векторов (1) — (7) справляются оптимизированные алгоритмы Вольфрам Математики. Так, достоверно известно, что ни один вывод в

$inline$ , имеющий на 8-ой итерации оператор конкатенации, сложения или вычитания не может привести к значению 10958. Какие возможности для дальнейшего решения это даёт?

Число 10958 является полупростым. И если последняя итерация вывода не содержит сложение, вычитание и конкатенацию, то один из операндов на 8-ой итерации будет гарантировано включать 5479 в некоторой степени, за исключением двух случаев:

когда операнды кратны некоторым комплексно-сопряжённым
когда один из операндов содержит логарифм, основание или показатель которого кратны 5479

И если первый случай по силам той же Вольфрам Математике, то второй нужно рассматривать отдельно. На сегодня не найдено не одного вывода, в котором элемент выходного вектора на какой-либо итерации являлся логарифмом, удовлетворяющим случаю 2. Более того, существует теорема в общем виде:

Теорема 1: пусть $\alpha = log_ab$ , где $inline$ и $inline$ — взаимно простые. Тогда $\alpha$ не выводимо над произвольным вектором $inline$ конечной длины n, где $inline$ — алгебраические целые числа

Напомню, что алгебраическим целым называется любое число, для которого существует многочлен с целыми коэффициентами и единичным старшим коэффициентом, такой что один из корней этого многочлена является данным числом.
При наличии формального доказательства этой теоремы, область поиска решений задачи Танежи можно будет значительно сузить. Один из методов поиска, позволяющий проверять только выводы, наиболее вероятные для получения искомого значения, называется «методом призраков и теней» и предложен мной.

Определение: Пусть на некоторой итерации некоторого вывода над

$inline$ один из элементов результирующего вектора итерации равняется простому числу p, тогда инфиксное представление этого элемента будем называть призраком числа p в данном выводе над

$inline$ .

Определение: Пусть на некоторой итерации некоторого вывода над

$inline$ один из элементов результирующего вектора является рациональным числом, числитель или знаменатель которого делятся на простое число p, и этот элемент не является призраком, тогда инфиксное представление этого элемента будем называть тенью числа p в данном выводе над

$inline$ .

Таблица призраков и теней для числа 5479 будет в сотни тысяч раз меньше общего количества выводов по Num_1. Кроме того, вручную комбинируя признаки с остальными элементами выходного вектора итерации, на которой были найдены призраки или тени, можно получить выводы с иррациональными и комплексными степенями, а также с большими целыми и рациональными степенями, которые отсекались в Num_2. Опишем функцию Num_3 для поиска призраков и теней и добавим нашему проекту файловый вывод.

Исходный код

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Numerics;

namespace ConsoleApp1
{
    class Program
    {
        static long Num_0(bool[] A)
        {
            if (A.Length == 1)
            {
                return 1;
            }
            else
            {
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                {
                    bool[] B = new bool[A.Length - 1];
                    for (int j = 0; j < i; j++)
                        B[j] = A[j];
                    for (int j = i + 1; j < A.Length-1; j++)
                        B[j] = A[j+1];
                    if (A[i] && A[i + 1])
                    {
                        B[i] = true; //B[i] result for A[i]||A[i+1]
                        res += Num_0(B);
                    }
                    B[i] = false; //B[i] result for A[i] op A[i+1], op!=||
                    res += 6 * Num_0(B);
                }
                return res;
            }
        }

        static void Test_0(int range = 9, bool wait = true)
        {
            Console.WriteLine("Test 0 for [1.." + Convert.ToString(range) + "]");
            F.WriteLine("Test 0 for [1.." + Convert.ToString(range) + "]");
            bool[] A = new bool[range];
            for (int i = 0; i < range; i++)
                A[i] = true; //each basic element is concatenable 
            string s = "Eq count: " + Convert.ToString(Num_0(A));
            Console.WriteLine(s);
            F.WriteLine(s);
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
            F.WriteLine();
        }

        public struct NumEx
        {
            public NumEx(BigInteger x, BigInteger y, int opcode)
            {
                X = x;
                Y = y;
                OpCode = opcode;
                Eq = X.ToString();
            }

            public BigInteger X { get; set; }
            public BigInteger Y { get; set; }
            public int OpCode { get; set; }

            public string Eq { get; set; }

            public override string ToString() => $"({X}/{Y}) [{Eq}]";
        }

        static long Num_1(NumEx[] A, int pos = -1)
        {
            if (A.Length == 1)
                return 1;
            else
            {
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                    if ((A[i + 1].OpCode != 0) || (pos == -1) || (pos >= i))
                    {
                        NumEx[] B = new NumEx[A.Length - 1];
                        for (int j = 0; j < i; j++)
                            B[j] = A[j];
                        for (int j = i + 1; j < A.Length - 1; j++)
                            B[j] = A[j + 1];
                        if ((A[i].OpCode < 2) && (A[i + 1].OpCode == 0))
                        {
                            // concat
                            B[i].OpCode = 1;
                            res += Num_1(B, i);
                        }
                        if (A[i + 1].OpCode != 2)
                        {
                            //+ -
                            B[i].OpCode = 2;
                            res += 2 * Num_1(B, i);
                        }
                        if (A[i + 1].OpCode != 3)
                        {
                            //* /
                            B[i].OpCode = 3;
                            res += 2 * Num_1(B, i);
                        }
                        {
                            //^ ^-
                            B[i].OpCode = 4;
                            if (A[i].OpCode == 4)
                                res += Num_1(B, i);
                            else
                                res += 2 * Num_1(B, i);
                        }
                    }
                return res;
            }
        }

        static void Test_1(int range = 9, bool wait = true)
        {
            Console.WriteLine("Test 1 for [1.." + Convert.ToString(range) + "]");
            F.WriteLine("Test 1 for [1.." + Convert.ToString(range) + "]");
            NumEx[] A = new NumEx[range];
            for (int i = 0; i < range; i++)
                A[i] = new NumEx(i + 1, 1, 0);
            string s = "Eq count: " + Convert.ToString(Num_1(A));
            Console.WriteLine(s);
            F.WriteLine(s);
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
            F.WriteLine();
        }

        static long PowLimit = 27;
        static long SolLimit = 400;
        static long SolCount = 0;
        static long Num_2(NumEx[] A, long val, int pos = -1)
        {
            if (A.Length == 1)
            {
                if ((A[0].X % A[0].Y) == 0)
                {
                    BigInteger B = BigInteger.Divide(A[0].X, A[0].Y);
                    if (B == new BigInteger(val))
                    {
                        SolCount++;
                        if (SolCount <= SolLimit)
                        {
                            Console.WriteLine(Convert.ToString(val) + " = " + A[0].Eq);
                            F.WriteLine(Convert.ToString(val) + " = " + A[0].Eq);
                        }
                    }
                }
                return 1;
            }
            else
            {
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                    if ((A[i + 1].OpCode != 0) || (pos == -1) || (pos >= i))
                    {
                        NumEx[] B = new NumEx[A.Length - 1];
                        for (int j = 0; j < i; j++)
                            B[j] = A[j];
                        for (int j = i + 1; j < A.Length - 1; j++)
                            B[j] = A[j + 1];

                        if ((A[i].OpCode < 2) && (A[i + 1].OpCode == 0))
                        {
                            // concat
                            int p = A[i + 1].X.ToString().Length;
                            B[i].X = BigInteger.Add(A[i + 1].X, BigInteger.Multiply(A[i].X,
                                BigInteger.Pow(new BigInteger(10), p)));
                            B[i].Y = 1;
                            B[i].OpCode = 1;
                            B[i].Eq = A[i].Eq + A[i + 1].Eq;
                            res += Num_2(B, val, i);
                        }

                        if ((A[i + 1].X % A[i + 1].Y) == 0)
                        {
                            //pow
                            BigInteger pow = BigInteger.Divide(A[i + 1].X, A[i + 1].Y);
                            if (pow <= PowLimit)
                            {
                                if (pow.IsZero)
                                {
                                    B[i].X = 1;
                                    B[i].Y = 1;
                                    B[i].OpCode = 4;
                                    string s1 = A[i].Eq;
                                    string s2 = A[i + 1].Eq;
                                    if (A[i].OpCode > 1)
                                        s1 = "(" + s1 + ")";
                                    if (A[i+1].OpCode > 1)
                                        s2 = "(" + s2 + ")";
                                    B[i].Eq = s1 + "^" + s2;
                                    res += Num_2(B, val, i);
                                }
                                else
                                {
                                    //^
                                    int p = (int)pow;
                                    BigInteger val1 = BigInteger.Pow(A[i].X, p);
                                    BigInteger val2 = BigInteger.Pow(A[i].Y, p);
                                    B[i].X = val1;
                                    B[i].Y = val2;
                                    B[i].OpCode = 4;
                                    string s1 = A[i].Eq;
                                    string s2 = A[i + 1].Eq;
                                    if (A[i].OpCode > 1)
                                        s1 = "(" + s1 + ")";
                                    if (A[i + 1].OpCode > 1)
                                        s2 = "(" + s2 + ")";
                                    B[i].Eq = s1 + "^" + s2;
                                    res += Num_2(B, val, i);
                                    //^-
                                    if ((!val1.IsZero) && (A[i].OpCode != 4))
                                    {
                                        B[i].X = val2;
                                        B[i].Y = val1;
                                        B[i].OpCode = 4;
                                        s1 = A[i].Eq;
                                        s2 = A[i + 1].Eq;
                                        if (A[i].OpCode > 1)
                                            s1 = "(" + s1 + ")";
                                        if (A[i + 1].OpCode > 1)
                                            s2 = "(" + s2 + ")";
                                        B[i].Eq = s1 + "^-" + s2;
                                        res += Num_2(B, val, i);
                                    }
                                }
                            }
                        }
                        if ((A[i + 1].X != 0) && (A[i + 1].OpCode != 3))
                        {
                            //div
                            B[i].X = BigInteger.Multiply(A[i].X, A[i + 1].Y);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].X);
                            B[i].OpCode = 3;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1)||(s2.ToArray()[0]=='-'))
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1+ "/" + s2;
                            res += Num_2(B, val, i);
                        }
                        if (A[i + 1].OpCode != 3)
                        {
                            //mul
                            B[i].X = BigInteger.Multiply(A[i].X, A[i + 1].X);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 3;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "*" + s2;
                            res += Num_2(B, val, i);
                        }
                        if (A[i + 1].OpCode != 2)
                        {
                            //add
                            B[i].X = BigInteger.Add(BigInteger.Multiply(A[i].X, A[i + 1].Y),
                                BigInteger.Multiply(A[i].Y, A[i + 1].X));
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 2;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (s2.ToArray()[0] == '-')
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "+" + s2;
                            res += Num_2(B, val, i);
                            //sub -abs
                            B[i].X = 
                                BigInteger.Subtract(BigInteger.Multiply(A[i].X, A[i + 1].Y),
                                BigInteger.Multiply(A[i].Y, A[i + 1].X));
                            bool neg = B[i].X < BigInteger.Zero;
                            if (neg) B[i].X = BigInteger.Abs(B[i].X);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 2;
                            s1 = A[i].Eq;
                            s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            if (neg)
                                B[i].Eq = "(-" + s1 + ")+" + s2; //?
                            else
                                B[i].Eq = s1 + "-" + s2;
                            res += Num_2(B, val, i);
                        }
                    }

                return res;
            }
        }

        static void Test_2(long val, int range = 9, bool wait = true, long out_lim = 400, long pow_lim = 27)
        {
            Console.WriteLine("Test 2 for [1.." + Convert.ToString(range) + "]");
            F.WriteLine("Test 2 for [1.." + Convert.ToString(range) + "]");
            NumEx[] A = new NumEx[range];
            for (int i = 0; i < range; i++)
                A[i] = new NumEx(i + 1, 1, 0);
            SolCount = 0;
            SolLimit = out_lim;
            PowLimit = pow_lim;
            Console.WriteLine("Max power: " + Convert.ToString(PowLimit) + ", output limit: " 
                + Convert.ToString(SolLimit));
            F.WriteLine("Max power: " + Convert.ToString(PowLimit) + ", output limit: "
                + Convert.ToString(SolLimit));
            string s = "Eq count: " + Convert.ToString(Num_2(A, val));
            Console.WriteLine(s);
            F.WriteLine(s);
            Console.WriteLine("Total solutions count for " + Convert.ToString(val) + ": " 
                + Convert.ToString(SolCount));
            F.WriteLine("Total solutions count for " + Convert.ToString(val) + ": "
                + Convert.ToString(SolCount));
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
            F.WriteLine();
        }

        static long GhostCount = 0;
        static long GhostLimit = (int)Math.Pow(10, 6);
        static long ShadowCount = 0;
        static long ShadowLimit = (int)Math.Pow(10, 6);
        static long Num_3(NumEx[] A, long val, int pos = -1)
        {
            if (A.Length == 1)
            {
                return 1;
            }
            else
            {
                //Ghosts & Shadows
                for (int i = 0; i < A.Length; i++)
                    if (A[i].X != BigInteger.Zero) 
                    {
                        if ((A[i].X % A[i].Y == 0) && (A[i].X / A[i].Y == new BigInteger(val)))
                    {
                        GhostCount++;
                        if (GhostCount <= GhostLimit)
                        {
                            string s = "";
                            for (int j = 0; j < A.Length; j++)
                            {
                                s += "[" + A[j].Eq + "]";
                                if (j == i)
                                    s += "<-[Ghost]";
                                s += ";";
                            }
                            Console.WriteLine(Convert.ToString(val) + "[Ghost]: " + s);
                                F.WriteLine(Convert.ToString(val) + "[Ghost]: " + s);
                        }
                    }
                    else
                    {
                        bool b1 = A[i].X % new BigInteger(val) == 0;
                        bool b2 = A[i].Y % new BigInteger(val) == 0;
                        if (!(!b1 && !b2))
                        {
                            ShadowCount++;
                            if (ShadowCount <= ShadowLimit)
                            {
                                string s = "";
                                for (int j = 0; j < A.Length; j++)
                                {
                                    s += "[" + A[j].Eq + "]";
                                    if (j == i)
                                        s += "<-[Shadow]";
                                    s += ";";
                                }
                                Console.WriteLine(Convert.ToString(val) + "[Shadow]: " + s);
                                    F.WriteLine(Convert.ToString(val) + "[Shadow]: " + s);
                            }
                        }
                    }
                }
                //Main search
                long res = 0;
                for (int i = 0; i < A.Length - 1; i++)
                    if ((A[i + 1].OpCode != 0) || (pos == -1) || (pos >= i))
                    {
                        NumEx[] B = new NumEx[A.Length - 1];
                        for (int j = 0; j < i; j++)
                            B[j] = A[j];
                        for (int j = i + 1; j < A.Length - 1; j++)
                            B[j] = A[j + 1];

                        if ((A[i].OpCode < 2) && (A[i + 1].OpCode == 0))
                        {
                            // concat
                            int p = A[i + 1].X.ToString().Length;
                            B[i].X = BigInteger.Add(A[i + 1].X, BigInteger.Multiply(A[i].X,
                                BigInteger.Pow(new BigInteger(10), p)));
                            B[i].Y = 1;
                            B[i].OpCode = 1;
                            B[i].Eq = A[i].Eq + A[i + 1].Eq;
                            res += Num_3(B, val, i);
                        }

                        if ((A[i + 1].X % A[i + 1].Y) == 0)
                        {
                            //pow
                            BigInteger pow = BigInteger.Divide(A[i + 1].X, A[i + 1].Y);
                            if (pow <= PowLimit)
                            {
                                if (pow.IsZero)
                                {
                                    B[i].X = 1;
                                    B[i].Y = 1;
                                    B[i].OpCode = 4;
                                    string s1 = A[i].Eq;
                                    string s2 = A[i + 1].Eq;
                                    if (A[i].OpCode > 1)
                                        s1 = "(" + s1 + ")";
                                    if (A[i + 1].OpCode > 1)
                                        s2 = "(" + s2 + ")";
                                    B[i].Eq = s1 + "^" + s2;
                                    res += Num_3(B, val, i);
                                }
                                else
                                {
                                    //^
                                    int p = (int)pow;
                                    BigInteger val1 = BigInteger.Pow(A[i].X, p);
                                    BigInteger val2 = BigInteger.Pow(A[i].Y, p);
                                    B[i].X = val1;
                                    B[i].Y = val2;
                                    B[i].OpCode = 4;
                                    string s1 = A[i].Eq;
                                    string s2 = A[i + 1].Eq;
                                    if (A[i].OpCode > 1)
                                        s1 = "(" + s1 + ")";
                                    if (A[i + 1].OpCode > 1)
                                        s2 = "(" + s2 + ")";
                                    B[i].Eq = s1 + "^" + s2;
                                    res += Num_3(B, val, i);
                                    //^-
                                    if ((!val1.IsZero) && (A[i].OpCode != 4))
                                    {
                                        B[i].X = val2;
                                        B[i].Y = val1;
                                        B[i].OpCode = 4;
                                        s1 = A[i].Eq;
                                        s2 = A[i + 1].Eq;
                                        if (A[i].OpCode > 1)
                                            s1 = "(" + s1 + ")";
                                        if (A[i + 1].OpCode > 1)
                                            s2 = "(" + s2 + ")";
                                        B[i].Eq = s1 + "^-" + s2;
                                        res += Num_3(B, val, i);
                                    }
                                }
                            }
                        }
                        if ((A[i + 1].X != 0) && (A[i + 1].OpCode != 3))
                        {
                            //div
                            B[i].X = BigInteger.Multiply(A[i].X, A[i + 1].Y);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].X);
                            B[i].OpCode = 3;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "/" + s2;
                            res += Num_3(B, val, i);
                        }
                        if (A[i + 1].OpCode != 3)
                        {
                            //mul
                            B[i].X = BigInteger.Multiply(A[i].X, A[i + 1].X);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 3;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "*" + s2;
                            res += Num_3(B, val, i);
                        }
                        if (A[i + 1].OpCode != 2)
                        {
                            //add
                            B[i].X = BigInteger.Add(BigInteger.Multiply(A[i].X, A[i + 1].Y),
                                BigInteger.Multiply(A[i].Y, A[i + 1].X));
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 2;
                            string s1 = A[i].Eq;
                            string s2 = A[i + 1].Eq;
                            if (s2.ToArray()[0] == '-')
                                s2 = "(" + s2 + ")";
                            B[i].Eq = s1 + "+" + s2;
                            res += Num_3(B, val, i);
                            //sub -abs
                            B[i].X =
                                BigInteger.Subtract(BigInteger.Multiply(A[i].X, A[i + 1].Y),
                                BigInteger.Multiply(A[i].Y, A[i + 1].X));
                            bool neg = B[i].X < BigInteger.Zero;
                            if (neg) B[i].X = BigInteger.Abs(B[i].X);
                            B[i].Y = BigInteger.Multiply(A[i].Y, A[i + 1].Y);
                            B[i].OpCode = 2;
                            s1 = A[i].Eq;
                            s2 = A[i + 1].Eq;
                            if (A[i].OpCode > 1)
                                s1 = "(" + s1 + ")";
                            if ((A[i + 1].OpCode > 1) || (s2.ToArray()[0] == '-'))
                                s2 = "(" + s2 + ")";
                            if (neg)
                                B[i].Eq = "(-" + s1 + ")+" + s2; //?
                            else
                                B[i].Eq = s1 + "-" + s2;
                            res += Num_3(B, val, i);
                        }
                    }

                return res;
            }
        }

        static void Test_3(long val, int range = 9, bool wait = true, long out_lim = 1000000, long pow_lim = 27)
        {
            Console.WriteLine("Test 3 for [1.." + Convert.ToString(range) + "]");
            F.WriteLine("Test 3 for [1.." + Convert.ToString(range) + "]");
            NumEx[] A = new NumEx[range];
            for (int i = 0; i < range; i++)
                A[i] = new NumEx(i + 1, 1, 0);
            GhostLimit = out_lim;
            ShadowLimit = out_lim;
            PowLimit = pow_lim;
            Console.WriteLine("Max power: " + Convert.ToString(PowLimit) + ", output limit: "
                + Convert.ToString(SolLimit));
            F.WriteLine("Max power: " + Convert.ToString(PowLimit) + ", output limit: "
                + Convert.ToString(SolLimit));
            string s = "Eq count: " + Convert.ToString(Num_3(A, val));
            Console.WriteLine(s);
            F.WriteLine(s);
            Console.WriteLine("Total ghost count for " + Convert.ToString(val) + ": "
                + Convert.ToString(GhostCount));
            F.WriteLine("Total ghost count for " + Convert.ToString(val) + ": "
                + Convert.ToString(GhostCount));
            Console.WriteLine("Total shadow count for " + Convert.ToString(val) + ": "
                + Convert.ToString(ShadowCount));
            F.WriteLine("Total shadow count for " + Convert.ToString(val) + ": "
                + Convert.ToString(ShadowCount));
            if (wait) Console.ReadLine();
            else
                Console.WriteLine();
            F.WriteLine();
        }

        static StreamWriter F;
        static void Init(string sFilename)
        {
            F = new StreamWriter(sFilename);
        }

        static void Close()
        {
            F.Close();
        }
        static void Main(string[] args)
        {
            Init("Tests_0_-_3.txt");
            for (int i = 2; i <= 9; i++)
            {
                Test_0(i, false);
                Test_1(i, false);
                Test_2(10958, i, false);
                Test_2(10958 / 2, i, false);
                Test_3(10958 / 2, i, false);
            }
            Close();
            while (true)
                Console.ReadLine();
        }
    }
}

Вывод получился объёмным, я покажу несколько его участков:

Test 3 for [1..9]
Max power: 27, output limit: 1000000
5479[Shadow]: [(-((((12^3+4)-5)^-6)^7))+8]<-[Shadow];[9];
5479[Shadow]: [(((12^-3)/4+5)^6+7)-8]<-[Shadow];[9];
5479[Shadow]: [(-(((12^-3)/4+5)^-6+7))+8]<-[Shadow];[9];
5479[Shadow]: [(-(((((12*3)-4)-5)^-6)^7))+8]<-[Shadow];[9];
5479[Shadow]: [(-((((((1^2)/3)^-4)*5)-6)^-7))+8]<-[Shadow];[9];
5479[Shadow]: [(-((((((1^2)*3)^4)*5)-6)^-7))+8]<-[Shadow];[9];
5479[Shadow]: [((-(((-(1^2))+3+4)^-5))+6)^7+8]<-[Shadow];[9];
5479[Shadow]: [(-((((((1^-2)/3)^-4)*5)-6)^-7))+8]<-[Shadow];[9];
5479[Shadow]: [(-((((((1^-2)*3)^4)*5)-6)^-7))+8]<-[Shadow];[9];
5479[Shadow]: [((-(((-(1^-2))+3+4)^-5))+6)^7+8]<-[Shadow];[9];
5479[Shadow]: [(-((((((1/2)^-3)*4)-5)^-6)^7))+8]<-[Shadow];[9];
5479[Shadow]: [((-((((1/2)*3)*4)^-5))+6)^7+8]<-[Shadow];[9];
5479[Shadow]: [(((1/2+3+4)*5)^6+7)-8]<-[Shadow];[9];
5479[Shadow]: [(-(((1/2+3+4)*5)^-6+7))+8]<-[Shadow];[9];
5479[Shadow]: [((((-(1/2))+3)^4+5+6)*7)-8]<-[Shadow];[9];
5479[Shadow]: [(-((((((1*2)^3)*4)-5)^-6)^7))+8]<-[Shadow];[9];
5479[Shadow]: [((-((((1*2)/3)/4)^5))+6)^7+8]<-[Shadow];[9];
5479[Shadow]: [((1*2+3)/4)^5+6+7]<-[Shadow];[8];[9];
5479[Shadow]: [(((1*2+3)/4)^5+6+7)^8]<-[Shadow];[9];
5479[Shadow]: [(((1*2+3)/4)^5+6+7)^-8]<-[Shadow];[9];
5479[Shadow]: [(((1*2+3)/4)^5+6+7)/8]<-[Shadow];[9];
5479[Shadow]: [(((1*2+3)/4)^5+6+7)*8]<-[Shadow];[9];

...

5479[Shadow]: [(-(1/(2*(345-6)+7)))+8]<-[Shadow];[9];
5479[Ghost]: [(-1)+((2*(345-6)+7)*8)]<-[Ghost];[9];
5479[Shadow]: [1/(2-((34^-5)^6)+7)+8]<-[Shadow];[9];

...

Eq count: 957441620
Total ghost count for 5479: 66
Total shadow count for 5479: 10802

Рассмотрим призрак:

$inline$ . Из всех элементов начального вектора осталась не задействована девятка, но над вектором

$inline$ невыводимо 10958. Аналогично нужно разобрать 65 призраков и 10802 тени. В интернете существует несколько крупных математических сообществ, занимающихся «дорешиванием» переборных задач, как это было с задачей о замощении плоскости. Однако пока теорема о выводимости логарифмов со взаимно простыми основанием и аргументом не доказана, о дорешивании речи не идет. В следующем разделе мы подробнее изучим вопрос машинного перебора всех выводов для произвольных векторов конечной длины с целыми алгебраическими элементами.

Дискретные представления

Понятие полного дискретного представления

Все мы знаем о проблеме конечности для алгоритмов, о классе NP — задач, которые в теории требуют неограниченных аппаратных ресурсов для вычисления решения за линейно растущее время. Но на факультетах информатики, в научно-исследовательских институтах и на рабочих местах часто игнорируется не менее важная проблема на стыке программирования и информатики — проблема представимости данных.

Так, из математики нам известно, что рациональные числа вида

$inline$ , где

$inline$ и

$inline$ — взаимно простые натуральные, представимо в виде конечной десятичной дроби, если в каноническом представлении числа

$inline$ все простые числа, отличные от 2 и 5 имеют нулевую степень, в противном случае

$inline$ можно представить в виде бесконечной дроби, которая будет периодической, поскольку

$inline$ не иррационально. Тогда машинную проверку равенства:

${\sqrt 3} = {\sqrt {{\sqrt 12}*{\sqrt {3/4}}}}$ (1)

Можно выполнить несколькими способами. Каждый способ будет опираться на свою структуру данных и обладать определённой эффективностью. Вот некоторые варианты:

Используем две переменные с плавающей точкой. Такой способ обладает очевидным преимуществом: на написание программы будет потрачено минимальное время. Но при последовательном вычислении вещественного приближения корня из 12, вещественного приближения корня из 3/4, потери точности при умножении двух вещественных и ещё больших потерях при приближенном вычислении мы можем получить вещественное число, близкое к корню из тройки, и оценив абсолютную погрешность вычисления определить вероятность выполнения равенства (1)
Метод обратной проверки. Для него нам потребуются две переменные с плавающей точкой и две целочисленные переменные. Вычислим приближенное значение первым методом. Заметим, что в исходном выражении все значения под корнем являются рациональными числами, причём либо целыми, либо «конечными десятичными дробями малых порядков». Тогда применим метод обратной проверки. Рассмотрим наш пример пошагово:
1. Исходное выражение представляем как $3 = {\sqrt {\alpha}}$ ; найдем $3 = {\alpha}$ в целых как ${\alpha}={\sqrt 3}^2=3$
2. Представим правую часть исходного выражения: ${\sqrt {{\sqrt 12}*{\sqrt {3/4}}}}$ как ${\alpha}={{\sqrt 12}*{\sqrt {3/4}}}={\sqrt {\beta}}$ ; Вычислив $\beta$ в целых, получим: ${\beta}={{\alpha}^2}=9$
3. Вычисляем в целых $inline$ и проверяем делимость результата на 4. Остаток равен 0, поэтому мы можем разделить в целых. Получим $inline$ ; Сравниваем два целых значения, полученных на этапах 2 и 3 соответственно и получаем точный ответ: выражение (1) верно т.к. $inline$ верно
При рассмотрении примера пришлось выполнить больше операций и для создания программы потребуется больше времени, но результат работы алгоритма будет точным, а не вероятностным
Используем «структуру Х». Опишем структуру данных с тремя целочисленными полями: $inline$ , которая будет представлять число: ${(a/b)}^{1/c}$ Главная особенность такого представления: все начальные, промежуточные и конечные значения при работе алгоритма будут представимыми и операции над ними будут выполнены без погрешности. Действительно:

$(3,1,2)={\sqrt {{\sqrt {(12,1,1)}}*{\sqrt {(3,4,1)}}}}={\sqrt {(12,1,2)*(3,4,2)}}=$ $={\sqrt {(36,4,2)}}={\sqrt {(9,1,2)}}={\sqrt (3,1,1)}={(3,1,2)}$ ;

Для реализации такого алгоритма придётся описывать сложную систему правил выполнения операций над тройками $inline$ , но готовая информационная модель позволит быстро и эффективно проверять корректность различных выражений, похожих на (1)

«Структура Х» — это наглядный пример структуры данных, являющейся полным дискретным представлением. Теория дискретных представлений иррациональных и трансцендентных чисел — новая область дискретной математики, которой должно уделяться больше внимания.

Определение: пусть для решения задачи

$inline$ для каждого вектора входных значений из конечного множества

$inline$ таких векторов, и для некоторой структуры данных

$Struct_{n_k}$ , описывающей каждый элемент вектора как набор из

$inline$ натуральных чисел, по модулю не превосходящих

$2^{len-1}$ , где

$inline$ — размер машинного слова исполнителя в битах, справедливо:

алгоритм $inline$ , реализующий задачу $inline$ на языке L остановится с выдачей корректного результата (соответствующего формату вывода, однозначно интерпретируемого и являющегося решением задачи $inline$ над данным вектором входных значений)
для каждого этапа работы алгоритма Alg, значения всех инициализированных переменных типа $Struct_{n_k}$ (результаты промежуточных вычислений) могут быть однозначно интерпретированы, их численное значение может быть точно восстановлено и использовано при ручной трассировке алгоритма с сохранением корректного вывода

тогда формальное описание

$Struct_{n_k}$ на некотором императивном декларативном языке программирования L будем называть полным дискретным представлением (ПДП) по L для решения задачи A над множеством векторов входных значений M и обозначать:

$L(A,M, Struct_{n_k})=true$

Минимальное ПДП

Существуют формальные методы построения структур данных, удовлетворяющих критериям ПДП. Один из таких: метод конечного замыкания. Замыканием некоторого множества относительно набора операций считается множество всех чисел, которые можно получить, выполнив конечное количество разрешенных операций над элементами исходного множества. Например: для конечного множества {0, 1} и набора операций: бинарное сложение и унарный минус замыканием будет множество

$inline$ всех целых чисел. Действительно: чтобы получить некоторое натуральное число

$inline$ , достаточно сложить

$inline$ единиц, для получения

$inline$ из

$inline$ можно использовать унарный минус, а нецелые значения будут невыводимы.

В методе конечного замыкания нас интересует множество

$inline$ всех элементов замыкания

$inline$ множества

$inline$ относительно набора операций

$inline$ , такое что для вывода любого значения из

$inline$ требуется произвести не более чем

$inline$ операций из

$inline$ над операндами из

$inline$ . Пусть при решении некоторой задачи, множество всевозможных наборов входных значений из

$inline$ , при которых алгоритм решения задачи остановится с выдачей корректного результата таково, что при выполнении данного алгоритма на любом из таких наборов все промежуточные значения (значения инициализированных на некотором этапе работы алгоритма переменные) будут лежать в

$inline$ . Тогда доказано, что существует ПДП, состоящее из не более чем

$inline$ целых чисел для машинного слова длины 2, где

$inline$ — мощность булеана множества

$inline$

Для задачи Танежи метод конечного замыкания не применим из-за большого размера булеана для замыкания

$inline$ относительно семи операций над начальным множеством цифр от 1 до 9. Поэтому ставится вопрос о минимизации числа n — количества целочисленных переменных, описывающих элемент вектора промежуточных значений в алгоритме, реализующем решение задачи Танежи в восходящем порядке.

Определение: Пусть

$inline$ — множество полных дискретных представлений

$\{ L(A,M, Struct_{n_k})\}$ и для некоторого элемента

$L_{i}(A,M, Struct_{n_{i,k}})$ (i — порядковый номер элемента множества) справедливо:

$\forall j\neq i: L_{j}(A,M, Struct_{n_{j,k}})=true \Rightarrow n_{i,k}\leqslant n_{j,k}$

тогда будем называть элемент

$\{ L_{i}(A,M, Struct_{n_{i,k}})\}$ минимальным полным дискретным представлением (ПДП минимальное) по L для решения задачи A над множеством векторов входных значений M и обозначать:

$L^{(min)}{(A,M, Struct_{n_k})=true}$

На самом деле, задача Танежи, в том виде, в котором она изложена в разделе «точная формулировка и первые обобщения» является задачей о полном дискретном представлении, а структура данных NumEx, использованная в алгоритмах перебора выводов Num_2 и Num_3 является примером структуры данных, не являющейся полной даже на одном единственном векторе

$inline$ . Построение ПДП минимального для задачи Танежи в восходящем порядке — важный этап доказательства отсутствия вывода для числа 10958.

Новая трансцендентология

О конечно трансцендентных и в точности трансцендентных числах

Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача. Так было с формальным обоснованием невозможности построения квадратуры круга циркулем и линейкой, с малой проблемой Гольдбаха и рядом других математических проблем. Так происходит и сегодня. Постановка задачи о представлении натуральных чисел при помощи семи операций над некоторым начальным вектором, подарила миру не только красивые частные решения и загадочную константу 10958, но и особый подход к классификации величин, значения которых не всегда могут быть записаны в явном виде. Так, доказано, что радикальные числа имеют ненулевое пересечение с множеством алгебраических чисел, но не входят в последнее полностью.

При написании программ, которые неизбежно по условию задачи должны производить вычисления, содержащие числа

$\pi$ и

$inline$ в качество операндов, обычно либо ограничиваются приближенным их представлением, либо пытаются запрограммировать аналитическое вычисление предела для рядов, которые сходятся к

$\pi$ и

$inline$ соответственно. Если же формат вывода конечного результата работы программы и специфика вычислений позволяют использовать такие числа как символы, то наличие трансцендентной составляющей неизбежно попадает в ПДП минимальное как переменная признака. Сравните две структуры данных и числа которые они представляют и оцените оптимальность решения некой абстрактной задачи над каждой такой структурой:

$inline$
$(a, b, b_p, c, c_p, d) = {(a+b*{\pi}^{b_p}+c*e^{c_p})}/d$

Очевидно, что ПДП минимальное в случае с трансцендентными числами может не являться оптимальным ПДП с точки зрения временной сложности для некоторой реализации алгоритма на императивном декларативном языке.

Определение: пусть

$inline$ — некоторые действительные алгебраические числа (не обязательно различные) и для некоторого трансцендентного действительного числа

$\tau$ существует инфиксное представление:

$\tau = a_1 op a_2$ , где

$inline$ — бинарный оператор из набора: сложение, вычитание, умножение, деление, возведение в степень. Тогда число

$\tau$ будем называть 1-трансцендентным и обозначать

$qtrans({\tau})=1$

Определение: пусть

$inline$ — некоторое действительное алгебраическое число,

${\tau}_{k}$ — k-трансцендентное число, тогда будем называть некоторое число

$\tau$ (k+1)-трансцендентным и обозначать

$qtrans({\tau})=k+1$ , если оно не является 1-трансцендентным, 2-трансцендентным… k-трансцендентным и существует инфиксное представление

${\tau}={\tau}_k op a$ , где

$inline$ — бинарный оператор из набора: сложение, вычитание, умножение, деление, возведение в степень.

Определение: число

$\tau$ будем называть конечно-трансцендентным и обозначать

$qtrans({\tau})\neq inf$ если для некоторого натурального числа

$inline$ справедливо:

$qtrans({\tau})=n$

Определение: число

$\tau$ будем называть в-точности-трансцендентным и обозначать

$qtrans({\tau})= inf$ , если оно действительно, трансцендентно и не является конечно-трансцендентным.

С введением понятия конечно трансцендентного числа становится возможным оперировать точными значениями некоторых трансцендентных чисел, не используя при этом их символы. В общем виде утверждается, что для некоторых подмножеств множества конечно-трансцендентных чисел существуют непустые множества задач

$inline$ над векторами входных значений, состоящими из алгебраических чисел, такие что для всякой задачи из

$inline$ ни одно из промежуточных или выходных значений элемента ПДП при работе алгоритма, реализующего решение данной задачи из

$inline$ не является в-точности-трансцендентным и среди всех реализаций данного алгоритма на некотором императивном декларативном языке

$inline$ наименьшую временную сложность будет иметь реализация с ПДП минимальным. Мощность множества A таких задач напрямую зависит от порядка

$inline$ .

Тау-выражения

Итак, в множестве трансцендентных чисел можно выделить на 3 непересекающихся (по построению) подмножества, объединение которых будет совпадать со множеством всех трансцендентных чисел, а именно:

конечно-трансцендентные числа
в-точности-трансцендентные числа
комплексно-трансцендентные числа

И если для конечно-трансцендентных мы можем построить ПДП по методу конечных замыканий и попытаться его минимизировать, то для в-точности-трансцендентных (к которым, помимо очевидных значений

${\pi}$ и

$inline$ , по Гельфонду будут относиться и десятичные логарифмы рациональных чисел, не являющихся точными целыми степенями 10 и некоторые другие важные с практической точки зрения значения). В текущем разделе предлагается рассмотреть множество чисел, включающее как конечно-трансцендентные, так и в-точности-трансцендентные числа и обладающее некоторыми важными для теории полных дискретных представлений свойствами. Речь пойдет о бесконечном множестве

${\tau}$ -выражений (читается: тау-выражений), а также о некоторых его счётных подмножествах.

Определение:

$\tau$ -формой (читается: тау-формой) первого порядка будем называть функцию

${\tau}_1 ({\alpha})$ , определённую для всякого аргумента

$\alpha \in \{0, 1\}$ и заданную таблицей значений:

${\tau}_1 (0) = e; {\tau}_1 (1) = \pi$ . Обозначение:

$qtrang({\tau}_1 ({\alpha})) = 1$

Определение:

$\tau$ -формой порядка

$inline$ будем называть функцию

${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ , определённую для всякого вектора

$({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ , где

${\alpha}_i \in \{0, 1\}, i=\overline{\rm 1, n}$ , заданную одним из равенств:

${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n) = {\tau}_L ({\alpha}_1, {\alpha}_2, ... , {\alpha}_{k}) + {\tau}_{RA} ({\alpha}_{k+1}, {\alpha}_{k+2}, ... ,{\alpha}_n)$
${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n) = {{\tau}_1 ({\alpha}_1)} ^ {{\tau}_R ({\alpha}_2, {\alpha}_3, ... , {\alpha}_{n})}$

где

${\tau}_1 ({\alpha})$ —

$\tau$ -форма первого порядка,

${\tau}_L ({\alpha}_1, {\alpha}_2, ... , {\alpha}_{k})$ —

$\tau$ -форма порядка

$inline$ , называемая левым мажором

$\tau$ -формы

${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ ,

${\tau}_R ({\alpha}_2, {\alpha}_3, ... , {\alpha}_n)$ —

$\tau$ -форма порядка

$inline$ , называемая правым мажором

$\tau$ -формы

${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ ,

${\tau}_{RA} ({\alpha}_{k+1}, {\alpha}_{k+2}, ... , {\alpha}_n)$ —

$\tau$ -форма порядка

$inline$ , называемая правым дополнением

$\tau$ -формы

${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ . Обозначения:

$qtrang({\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n))=n, Lmaj({\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n))={\tau}_L ({\alpha}_1, {\alpha}_2, ... , {\alpha}_{k}),$

$Rmaj({\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n))={\tau}_R ({\alpha}_2, {\alpha}_3, ... , {\alpha}_n)$ ,

$Radd({\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n))={\tau}_{RA} ({\alpha}_{k+1}, {\alpha}_{k+2}, ... , {\alpha}_n)$ .

Для

$\tau$ -формы

${\tau}_n ({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ заданной

$\tau$ -формой первого порядка и правым мажором или левым мажором и правым дополнением будем считать соответственно левый мажор и правое дополнение или правый мажор неопределёнными.

Определение:

$\tau$ -выражением порядка

$inline$ будем называть значение

$\tau$ -формы

${\tau}_n({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ порядка n на некотором векторе

$({a}_1, {a}_2, ... , {a}_n)$ , называемом задающим вектором

$\tau$ -формы, где

${a}_i \in \{0, 1\}, i=\overline{\rm 1, n}$ .

Также определим понятия правого и левого мажора и правого дополнения для

$\tau$ -выражения, как значение соответственно правого и левого мажора и правого дополнения

$\tau$ -формы

${\tau}_n({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ , задающей это выражение на соответствующем подвекторе задающего вектора.

Примеры

$\tau$ -выражений:

$\pi + e^e$ ;

$e^{e^{\pi}+e}+e^e+e$ ;

${\pi}^{{\pi}^{e+e}}$ ;

Определение: главными слагаемыми

$\tau$ -выражения

${\tau}_n$ порядка

$inline$ вида:

${\tau}_n={{\tau}_{1,1}}^{{\tau}_{k_1,1}}+{{\tau}_{1,2}}^{{\tau}_{k_2,2}}+$

$... + {{\tau}_{1,m}}^{{\tau}_{k_m,m}}+{{\tau}_{1,m+1}}+{{\tau}_{1,m+2}}+$

$... + {\tau}_{1,m+p}$ , где:

${\tau}_{1, i}$ — некоторые

$\tau$ -выражения первого порядка,

$i=\overline{\rm 1,m+p}$ ,

${\tau}_{k_j,j}$ — некоторые

$\tau$ -выражения порядка

$inline$ ,

$j=\overline{\rm 1,m}$
и

$inline$
будем называть элементы вида:

${\tau}_{1,q}$ и

${{\tau}_{1,r}}^{{\tau}_{k_r,r}}$ , где

$q=\overline{\rm m+1,m+p}$ ,

$r=\overline{\rm 1,m}$

Один из способов записи

$\tau$ -форм:

${\tau}({\alpha}_1, {\alpha}_2, {\alpha}_3, {\alpha}_4, {\alpha}_5) = {\tau}_1({\alpha}_1)^{{\tau}_1({\alpha}_2)}+{\tau}_1({\alpha}_3) +{\tau}_1({\alpha}_4) + {\tau}_1({\alpha}_5)$ , где

$qtrang({\tau}_1 ({\alpha})) = 1$

Таким образом, множество

$\tau$ -выражений конечного порядка является частным случаем замыкания множества

${\pi, e}$ относительно операций сложения и умножения. Подмножество

$\tau$ -выражений одного порядка всегда можно упорядочить.

Использование порядкового номера

$\tau$ -выражения в качестве ПДП позволяет сравнивать

$\tau$ -выражения и выполнять некоторые операции над ними без какой-либо погрешности, более того:

Теорема 2. При ограничении порядка всех тау-выражений некоторым числом $inline$ для множества задач $inline$ , ПДП для которых представляет все такие выражения, существует реализация $inline$ на императивном декларативном языке $inline$ для некоторого алгоритма $inline$ , такая что для входной строки — описания на любом императивном декларативном языке $inline$ ПДП структуры данных некоторой задачи $inline$ из A, алгоритм остановится с выводом строки — описания на языке $inline$ ПДП минимального для структуры данных алгоритма $inline$ — реализации алгоритма $inline$ решения задачи $inline$ на языке $inline$ .

Рассматривая задачу Танежи в восходящем порядке, важно понимать, что ни один из элементов входного вектора итераций (1), (2) и (3) не содержит (доказывается перебором всех таких итераций) трансцендентных элементов. Из определения конечной трансцендентности и на основании вышесказанного следует невыводимость

$inline$ -трансцендентных значений для задачи Танежи в восходящем порядке при

$inline$ . Значит, при доказательстве отсутствия вывода для числа

$inline$ достаточно проверить выводимость всех

$inline$ -трансцендентных чисел

${\tau}_m$ и алгебраических чисел

$\alpha$ над всеми подвекторами вектора

$inline$ , таких что:

$10958 = {\tau}_m op \alpha, m<6$ , где

$inline$ — некоторая операция из множества допустимых для итерации (8), заданной тройкой

$inline$ . Данное условие является достаточным: т.е. невыводимость всех таких пар, представляющих число

$inline$ , доказывает невыводимость самого числа

$inline$ , но обратное не верно — из вывода в

$inline$ -трансцендентных ещё не следует решение исходной задачи.

Общая теорема «О замыканиях конечных множеств трансцендентных чисел»

Определение: будем называть

$\tau$ -выражение

${\tau}_n$ порядка

$inline$ нормальным, если выполняется одно из условий:

${\tau}_n$ численно равно одному из значений: $\pi , e, \pi +e$ и $n \in {1, 2}$
$inline$ и правый мажор ${\tau}_n$ определён и нормален
$inline$ , левый мажор ${\tau}_n$ определён и нормален, правое дополнение ${\tau}_n$ определено и нормально и алгебраические представления левого мажора ${\tau}_n$ и правого дополнения ${\tau}_n$ не содержат подобных главных слагаемых.

Заметим, что нормальность

$\tau$ -выражения, в простом понимании, означает отсутствие подобных слагаемых в алгебраической записи этого

$\tau$ -выражения.

Примеры:

${\pi}^e+e^{\pi}$ — нормально

$e^{e+{\pi}}+{\pi}+e^{{\pi}+e}$ — не нормально, так как:

$e^{e+{\pi}}+{\pi}+e^{{\pi}+e} = e^{e+{\pi}}+e^{e+{\pi}}+{\pi} = 2*e^{e+{\pi}}+{\pi}$

Определение:

$\tau$ -выражение

${\tau}_0={\tau}_n(a_1, a_2, ... , a_n)$ будем называть корнем некоторой

$\tau$ -формы

${\tau}_n({\alpha}_1, {\alpha}_2, ... , {\alpha}_n)$ порядка

$inline$ , если это выражение нормально и выполняется неравенство:

$qtrans({{\tau}_n(a_1, a_2, ... , a_n)}) \leqslant n$ ,
где

$a_i \in \{0, 1\}, i=\overline{\rm 1, n}$

Теорема 3. Всякое счётное подмножество множества $\tau$ -форм конечного порядка включает конечное число $\tau$ -форм, имеющих хотя бы один корень.

Напомню, что счётным называется множество, которое можно поставить во взаимно-однозначное соответствие с множеством

$inline$ целых чисел.

Теорема 4. Пусть $inline$ — некоторое множество действительных чисел, удовлетворяющее следующим условиям:

$inline$ конечно или счётно

$inline$ содержит не менее одного в точности трансцендентного элемента

замыкание $\overline{\rm M}$ множества $inline$ относительно набора бинарных операций: сложение и возведение в степень — континуально

тогда всякое счётное подмножество множества $\overline{\rm M}$ включает конечное число конечно-трансцендентных элементов.

Важным следствием из теоремы 3 является существование ПДП минимального для алгоритмов, производящих вычисления только над алгебраическими и конечно-трансцендентными числами. Теорема 4 даёт общее представление о распределении конечно-трансцендентных чисел среди всех действительных трансцендентных чисел и ценна как теоретический инструмент для классификации групп, колец и замыканий относительно возведения в степень, содержащих трансцендентные элементы.

Итоги

Теория конечно-трансцендентных чисел как следствие из задачи Танежи и часть нового математического аппарата, необходимого для разрешения проблемы числа 10958 — важный инструмент, практическое применение которого в программировании и теоретическая значимость для топологии как науки трудно недооценить. Существуют исчерпывающие классификации рациональных, алгебраических чисел, детально изучены комплексные числа и функции над ними, и только трансцендентные числа остаются для современных математиков загадкой. Поиск корней произвольных

$\tau$ -форм как упражнение со временем поможет выработать новый подход к решению задач классификации действительных чисел.

Сама задача Танежи обнажает проблему полного дискретного представления и показывает несостоятельность популярных методов описания структуры данных при решении математических задач на ПК. Так, для полного перебора всех выводов задачи Танежи над вектором

$inline$ абсолютная погрешность вычислений при использовании типа Complex с двумя компонентами — числами с плавающей точкой — не позволит разрешить вопрос о выводимости не только конкретного целого числа, но и вопрос о выводимости хотя бы одного целого/рационального числа из короткого отрезка.

При поверхностном рассмотрении проблемы числа 10958 в статьях математиков-популяризаторов отмечалась лишь проблема «астрономических чисел» — так называют числа (чаще всего целые), десятичная запись которых невозможна. Яркие примеры — число

$6^{7^{8^9}}$ , которое легло вывести над вектором

$inline$ или оценка

$N\approx 10^{10^{10^{34}}}$ появления отрицательной погрешности в законе Чебышева о распределении простых чисел. В действительности, промежуточные значения при вычисления вывода могут быть не только астрономическими числами, но также комплексными и трансцендентными числами, выполнение арифметических операций с которыми и расчет погрешности вычислений затруднительны.

С одной стороны, научно-популярная математика воспитывает всё новые поколения ферматистов, что негативно сказывается на имидже профессиональной науки. С другой — привлечение внимания многомиллионной аудитории к нерешённым математическим проблемам порождает множество альтернативных взглядов на формулировки и возможные пути решения, и часть таких идей ложится в основу трудов математиков-профессионалов. Так было с задачей Эрдеша, и так сегодня любительская работа Индера Танежи о замечательных представлениях целых чисел способна изменить современную математику и подарить IT-сфере новый подход к описанию структур данных.

Ссылки

Комментарии (30)

speakingfish
18.05.2020 11:00
#21629164
+1
Не понял, каким образом задача Танежи вдруг стала фундаментальной, если она использует «конкатенацию» цифр, которые зависят от системы счисления?
1. stefanov94 Автор
  18.05.2020 12:00
  #21629370
  Она и не стала. Перечитайте статью. Речь идёт о новом математическом аппарате и связанном с ним подходе к решению переборных задач на ПК — подходе, без которого вывод для числа 10958 нереально построить. Фундаментальность самой задачи Танежи нигде не утверждается. Цитата из заключения:
  Сама задача Танежи обнажает проблему полного дискретного представления и показывает несостоятельность популярных методов описания структуры данных при решении математических задач на ПК
  1. Vitter
    18.05.2020 16:36
    #21630234
    там абзац этому посвятили:
    
    Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача. Так было с формальным обоснованием невозможности построения квадратуры круга циркулем и линейкой, с малой проблемой Гольдбаха и рядом других математических проблем. Так происходит и сегодня. Постановка задачи о представлении натуральных чисел при помощи семи операций над некоторым начальным вектором, подарила миру не только красивые частные решения и загадочную константу 10958, но и особый подход к классификации величин, значения которых не всегда могут быть записаны в явном виде. Так, доказано, что радикальные числа имеют ненулевое пересечение с множеством алгебраических чисел, но не входят в последнее полностью.
    
    stefanov94 Автор
    19.05.2020 06:31
    #21631780
    Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача.
    
    При аналитическом подходе к решению задачи Танежи в восходящем порядке естественным образом возникает понятие конечно-трансцендентного числа. И за это мы благодарны Индеру Танеже. Но сам он никакой классификацией трансцендентных действительных величин не занимался. Об этом идёт речь. Мы ценим не саму возможность представления целых при помощи замыкания над множеством чисел от 1 до 9, а ту математическую теорию, которая благодаря изучению этой возможности возникает.

ComodoHacker
18.05.2020 11:12
#21629214
+2
Пожалуйста, уберите длинные простыни кода и вывода под кат. Мотивация дочитать до конца и понять сильно повысится.
1. Boomburum
  18.05.2020 11:53
  #21629336
  +1
  Поправил :)
  1. stefanov94 Автор
    18.05.2020 12:04
    #21629382
    Спасибо!

rsync
18.05.2020 13:55
#21629720
+1
по моему актуальные задачи у математиков кончились и они теперь из цифр 12345… составляют 1956

очень полезное занятие, наверное

но неужели у физиков например нет задач которые требуют решения?
1. ComodoHacker
  18.05.2020 14:24
  #21629812
  Кончились задачи, которые можно решить в одиночку, не будучи супергением.
  FTFY.
1. AAngstrom
  18.05.2020 18:38
  #21630598
  Нерешённых (вопрос, считать ли их все актуальными?) проблем в математике — море: https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics.
  
  У физиков (и не только) тоже дофига задач, где математики могли бы помочь. К сожалению, часто это задачи вычислительного характера, которые математикам неинтересны (простой пример: выразить решение дифференциального уравнения Х либо через известные спецфункции, либо в виде интеграла и т.п.). Поэтому, в основном, такими задачами занимаются не собственно математики, а математические физики.
1. stefanov94 Автор
  19.05.2020 05:38
  #21631744
  +1
  Проблема в том, что некоторые люди не осознают как сильно решение «практически полезных» задач той же физики зависит от математического аппарата. Без производных не были бы запущены на орбиту спутники, которые обеспечивают беспроводной интернет вам и позволяют написать этот комментарий. Поверьте, сотни компаний — производственников сегодня ждут решения открытых математических проблем. И если для вас связь между «составлением из цифр» и выходом нового поколения электроники не очевидна — это говорит лишь о недостатке образования. Пишу искренне, не желая никого обидеть. Спасибо!
  1. rsync
    19.05.2020 10:09
    #21632112
    +1
    и тензоры зачем нужны — понимаю
    и конечно производные
    и вычеты
    и т.п.
    
    у всех этих вещей есть физическое применение, смысл
    
    а в чем смысл разложения числа 1958 на числа 123456789, это именно синтетическая задача
    
    PS: тоже искрене пишу, никого не хочу обидеть
    
    AAngstrom
    19.05.2020 11:29
    #21632366
    +1
    В чём физический смысл теоремы Ферма или диофантовых уравнений? Наверное, ни в чём, но при решении связанных с ними задач была придумано масса методов, были найдены неожиданные связи между геометрией и алгеброй и т.д… Попытки оценить плотность простых чисел внесли вклад в развитие комплексного анализа, были получены многочисленные тождества для всяких спецфункций, которые через пару сотен лет неожиданным образом оказались нужны для физики.
    
    В общем, синтетические задачи — это не обязательно плохо. Часто они являются драйвером развития общих математических методов.
    
    stefanov94 Автор
    19.05.2020 11:37
    #21632398
    *10958
    Есть такое замечательное понятие: Гильбертова интуиция. Оно поможет вам понять, что происходит.
    Давид Гильберт — немецкий математик XIX-XX веков. На втором международном математическом конгрессе 1900 года он предложил 23 «фундаментальные» задачи современной (ему) математики и обосновал их значимость весьма оригинальным образом.
    Рассмотрим поведение профессионального математика при решении некоторой задачи. На первом этапе решения математик пытается получить наиболее простую (так называемую «рабочую версию») формулировку задачи. Речь не всегда идёт о простоте в научно-популярном смысле, как это происходит сейчас с проблемой Гольдбаха-Виноградова и проблемой Эрдеша. Математик ищет простую для себя формулировку. Так не секрет, что без ограничения общности некоторой геометрической задаче можно поставить в соответствие алгебраическую модель. А задачу из теории чисел, наоборот решать в топологиях. И если наш герой более компетентен в геометрии, он будет искать наиболее понятную геометрическую трактовку для большинства задач, вне зависимости от раздела-источника задачи.
    На втором этапе происходит процесс «эвристического поиска уязвимостей». Решая однотипные задачи математик не развивается — такие упражнения полезны при подготовке к ЕГЭ, выступлении на олимпиадах — не более. Но рассматривая задачи с принципиально разным подходом к решению, относящиеся к некоторой узко специальной области, ученый формирует ряд ложных корреляций, которые составляют математическую интуицию. Так, имея на начальном этапе несколько путей анализа задачи, математик с опытом может «наугад» выбрать тот путь, который с большей вероятностью приведёт к стройному решению.
    Наряду с интуицией отдельного математика, Гильберт рассматривает коллективное «ощущение важности» некоторых задач для всего математического сообщества. Так, диофантово уравнение ${a^n}+{b^n}={c^n}$ уже на тот момент не являлось единственным нерешаемым неопределённым уравнением в целых числах, однако «математическое чутьё» подсказывало, что при решении именно этого уравнения возникнет необычайно ценный математический аппарат, который будет применяться в различных областях науки.
    Гильбертова интуиция — это способность отобрать из числа бесполезных задач как таковых (ибо нахождение корней для уравнения ${a^n}+{b^n}={c^n}$ не несёт ничего полезного) — те, с решением которых престиж математики, возможности теоретического аппарата и уровень влияния на другие науки возрастут.
    Задача Танежи как таковая не несёт пользы, но для её решения (как оказалось при детальном рассмотрении, результаты которого частично приведены в этой статье) потребуется развить трансцендентологию и расширить современную дискретную математику теорией ПДП. То, как сильно современные астрофизика, нейробиология и ряд других прикладных дисциплин зависят от дискретки думаю пояснять не требуется.

michael_vostrikov
18.05.2020 14:32
#21629832
По поводу связи с представлением в целых числах можно еще вспомнить степени i.
i это поворот вектора на ?/2 через комплексное направление, поэтому i² это поворот на ?, что эквивалентно умножению на -1.
i^1/2 это поворот на ?/4, а его проекции на координатные оси равны v2/2 = (1/2)^1/2.
1. stefanov94 Автор
  19.05.2020 06:44
  #21631794
  Для задач, при решении которых приходится выполнять операции с комплексными алгебраическими числами и некоторыми трансцендентными, являющимися линейной комбинацией алгебраических чисел и числа $\pi$ , тип данных Complex как структуру можно считать ПДП минимальным для некоторых из таких задач.
  
  $i^{1/2}$ это поворот на ${\pi}/4$ , а его проекции на координатные оси равны ${\sqrt {2}}/2 = {(1/2)}^{1/2}$ .
  
  Интересная идея! Действительно, некоторые комплексные величины, целая и мнимая часть которых являются целыми числами, либо для которых существует тригонометрическая форма записи с рациональными углами (в градусном их измерении), в точности представляют такие иррациональные значения, как ${\sqrt {2}}/2$ и позволяют выполнять некоторые операции над этими значениями без погрешности.
  1. AAngstrom
    19.05.2020 11:37
    #21632396
    +1
    Гауссовы целые (и рациональные) числа?
    
    stefanov94 Автор
    19.05.2020 11:44
    #21632432
    Точно!

Tzimie
18.05.2020 15:51
#21630096
Интересно, это как нибудь связано с мерой рациональности числа?
Также, мне кажется тема «нормальных» чисел более фундаментальна
1. stefanov94 Автор
  19.05.2020 06:20
  #21631766
  Интересно, это как нибудь связано с мерой рациональности числа?
  
  Если вы имеете в виду «меру иррациональности», то она является оценкой возможности приближения некоторого действительного числа конечным набором целых значений. ПДП же предполагает точное представление иррациональных и трансцендентных чисел на компьютере и выполнение операций над ними без погрешности. Поэтому прямая связь отсутствует. Если же будет доказана связь между мерой иррациональности и qtrans, то тогда можно будет подискутировать.
  
  Также, мне кажется тема «нормальных» чисел более фундаментальна
  
  Для математики — да. Для прикладной информатики — тема «конечно-трансцендентных» сегодня важнее. К тому же, в работах математиков 2010-2020 годов слишком часто стали появляться высказывания о «беспомощности» современной алгебры при работе с трансцендентными величинами. Пока даже доказательство факта трансцендентности является нерешаемой задачей для большинства классов действительных величин. Например: трансцендентность десятичных логарифмов целых, отличных от степени десятки, чисел была доказана, однако вопрос о трансцендентности логарифма числа, взаимно простого с основанием этого логарифма является открытой математической проблемой, не уступающей по «безнадёжности» ABC-гипотезе.
  1. Tzimie
    19.05.2020 19:37
    #21634380
    +1
    Кстати, Вы не задумывались о том, что получение произвольного числа из вектора 123456789 и ограниченного набора операций близко к проблеме Collatz в ее инверсной форме: от 1 и двигаясь "назад" получить любое целое?
    
    stefanov94 Автор
    20.05.2020 04:34
    #21635540
    Спасибо! Проблема Коллатца:

Shiny2
18.05.2020 16:04
#21630158
есть по-русски
youtu.be/T9TqbJNkcP0
1. stefanov94 Автор
  19.05.2020 05:40
  #21631746
  О Mad Astronomer говорится в статье, но само видео от них не прикреплял. Спасибо!

Andrey_Rogovsky
18.05.2020 16:17
#21630184
В теории — прикольно
На практике — хранение неупакованных данных в памяти дешевле, чем затраты процессора на перепаковку
МБ для каких-то супер-пупер компьютеров это не так, там проц дешевле оперативы и тогда это будет иметь смысл. Но что-то я сомневаюсь в таких суперкомпьютерах
1. stefanov94 Автор
  19.05.2020 06:02
  #21631760
  Речь не всегда идёт о перепаковке данных с целью уменьшения сложности по памяти. Для некоторых задач реализация алгоритма решения с типом double будет некоректна из-за громадных погрешностей. И когда вам нужно проверить равенство значения функции в точке некоторой константе, а на выходе получаете: $f({x_0}) = 2 \pm 1000$ , тогда приходится описывать сложную структуру данных, чтобы минимизировать погрешность или вовсе организовать работу с точными численными значениями величин, непредставимых конечной или бесконечной периодической десятичной дробью. В таких ситуациях ПДП (полное дискретное представление) — важный ориентир для программиста.

OlegPatron92
19.05.2020 05:41
#21631748
Почему бы не написать алгоритм, который переберёт все возможные решения. Вариантов ведь не так и много…
1. stefanov94 Автор
  19.05.2020 06:21
  #21631768
  Потому что в int, double, Complex и даже BigInteger он не переберёт…
  В статье дан ответ на этот вопрос. Если коротко и на примерах, то с такими числами как $2^{({3^4}^5)}$ и $6^{7^{89}}$ работать на компьютере проблематично, а в теории то что ${2^{({3^4}^5)}} /{6^{7^{89}}} \neq 10958$ — неочевидно и требует строгой проверки. И такие варианты, с которыми нельзя справится даже на суперкомпьютерах — составляют порядка 15% от общего числа выводов. Помимо этого, работа с иррациональными числами на компьютере как правило ограничена работой с их вещественным приближением. И для некоторого выражения: $\sqrt {{\alpha}+{\beta}^{\sqrt {\gamma}}}$ на компьютере можно получить лишь приближение: $\sqrt {{\alpha}+{\beta}^{\sqrt {\gamma}}} = 10958 \pm {10}^{20}$ . Отсюда вытекает проблема полного дискретного представления для иррациональных и трансцендентных величин.

OlegTheMath
20.05.2020 20:45
#21638626
+1
Поправьте пожалуйста в примерах:
(1+2^3)*4-5=(1+8)*4-5=9*4-5=36-5=31,
а не 35, как у Вас написано.

PS: по-моему, никто еще не отметил эту ошибку
см. Точная формулировка и первые обобщения
1. stefanov94 Автор
  20.05.2020 20:46
  #21638628
  Спасибо, исправил!

Задача Танежи: новый этап развития математики? +42

Введение

Задача Индер Танежи

Общие сведения

Точная формулировка и первые обобщения

Ход решения

Призраки и тени

Дискретные представления

Понятие полного дискретного представления

Минимальное ПДП

Новая трансцендентология

О конечно трансцендентных и в точности трансцендентных числах

Тау-выражения

Общая теорема «О замыканиях конечных множеств трансцендентных чисел»

Итоги

Ссылки

Комментарии (30)

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор

stefanov94 Автор