Введение
Математика XXI века принципиально отличается от античной. И речь идёт не просто о новых достижениях в геометрии и арифметике — науках, базовые принципы для которых сформированы тысячелетия назад. С появлением вычислительной техники изменился приоритет, и теория чисел из области «упражнений для развития ума» превратилась в науку, от достижений которой зависит мировая экономика.
По задаче о простых близнецах, по ABC-гипотезе, проблеме Гольдбаха-Виноградова и некоторым другим важным математическим проблемам новые научно-популярные публикации выходят ежедневно. С одной стороны, эти задачи выдержали проверку временем, с другой — регулярный пиар поддерживается шестизначными наградами за решение каждой. Но 4 года назад в трудах одного бразильского математика была, косвенно и незаметно для него самого, поднята проблема, которая может стать целью и смыслом жизни для математиков нынешнего столетия. Речь идёт о классификации трансцендентных чисел относительно замыкания конечных множеств алгебраических чисел.
Задача Индер Танежи
Общие сведения
Индер Танежа — бразильский математик-популяризатор, посвятивший большую часть жизни магическим квадратам, треугольным числам и другим занимательным задачам. Он никогда не брался за нерешённые проблемы столетия, не сделал профессионального вклада в изучение свойств натурального ряда, но именно в его любительских исследованиях были подняты вопросы, ответы на которые не способна дать современная математика.
Всё началось с серии публикаций в Реддит, где Танежа рассуждал о возможности представить любое натуральное число меньше некоторой границы при помощи ограниченного числа операндов. Сама идея не нова, и в советских изданиях для олимпиадников периодически возникали такие вопросы:
Представьте число 1958 при помощи семи двоек, расставляя операторы сложения, вычитания, умножения и возведения в степень
Ответом будет:
Подбор необычного представления для текущего года стал традицией для математических факультетов многих вузов и укрепился в литературе. Так же было с задачами о простоте больших чисел: пару веков назад числами Мерсенна и Ферма занимались из спортивного интереса, а теперь первые обеспечивают криптографию надежными закрытыми ключами. И вот 4 года назад появилась публикация, в которой рассматривались возможные пути решения задачи о представлении натурального числа с использованием одной цифры, а также упорядоченные представления со всеми цифрами кроме нуля. Например:
Среди допустимых операций изначально были:
- конкатенация: 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 будет подробнее рассказано ниже.
Точная формулировка и первые обобщения
Вольная формулировка автора задачи породила множество ошибочных решений, опирающихся на неверную трактовку условия. Самые частые ошибки:
- использование «внешней» конкатенации: составление новых операторов из цифр начального вектора допустимо, но конкатенация в общем виде как дописывание одного числа справа от другого — запрещена. Примеры:
— можно,
— нельзя
- округление: решение задачи Танежи в целых числах означает не только использование целочисленного начального вектора, но и получение целого результата на выходе. Примеры:
— можно,
— нельзя
- использование дополнительных операндов: при выполнении операции возведения в степень некоторые авторы рассматривают исходный набор цифр как допустимые основания степени и прибегают к произвольным показателям. Примеры:
— можно,
— нельзя
Опишем процесс проверки и принятия решения задачи Танежи для некоторого числа. Пусть для некоторого вектора комплексных (в общем случае) чисел
- вектор
для
- вектор
для
- вектор
для
- вектор
для
- вектор
для
- вектор
для
- вектор
для
Пусть дан начальный вектор
…
такая, что вектор (8) равен вектору
Для каждого вектора количество операций и возможностей выбора пар значений
- Сколько различных выводов, имеющих целочисленный результат, существует?
- Сколько различных по модулю целых чисел выводимо?
- Сколько различных комплексных значений выводимо?
- Верно ли, что количество различных рациональных значений, выводимых и по модулю не превосходящих некоторое целое число 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 млрд вариантов. По построению, многие варианты вывода будут не просто производить одно и то же значение, но и иметь одно и то же инфиксное представление (получать искомое число, используя те же операторы, над теми же операндами, но в другом порядке). Например, если первая итерация преобразовала элементы
Опишем некоторые классы выводов с повторяющимся результирующим инфиксным представлением:
- пусть оператор сложения выполняется над операндами, один из которых является результатом сложения, тогда можно ограничиться итерациями, в которых правый операнд не является результатом сложения и результат прошлых вычислений является элементом, индекс которого не более
текущей итерации. Так мы с одной стороны исключаем
в пользу
, а с другой для выражения
исключаем вариант вычисления
до вычисления
, исключая таким образом как минимум один повтор
- сложение и вычитание результатов сложения и вычитания: аналогично предыдущему пункту, но с ограничениями для унарных операций перед показателями степеней
- пусть основание степени является результатом возведения в степень, тогда можно не проверять вариант с оператором 7, на основании тождества:
, зная что по построению наличие вектора, аналогичного входному вектору текущей итерации, за исключением значения
вместо
гарантировано
- умножение и деление можно БОО (Без Ограничения Общности) выполнять строго слева направо, т.е. только когда правые операнды не являются результатами умножения или деления. Следует из тождеств:
и
Реализация операторов с учётом этих классов не гарантирует отсутствие повторов среди инфиксных выражений, но БОО позволяет отбросить часть таких повторов.
Значения элементов векторов для некоторых выводов не вычислимы, что связано с ограниченным размером машинного слова. С использованием типа данных 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 с заданными условиями. Для чисел
Исходный код
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, такими как
Число 10958 является полупростым. И если последняя итерация вывода не содержит сложение, вычитание и конкатенацию, то один из операндов на 8-ой итерации будет гарантировано включать 5479 в некоторой степени, за исключением двух случаев:
- когда операнды кратны некоторым комплексно-сопряжённым
- когда один из операндов содержит логарифм, основание или показатель которого кратны 5479
И если первый случай по силам той же Вольфрам Математике, то второй нужно рассматривать отдельно. На сегодня не найдено не одного вывода, в котором элемент выходного вектора на какой-либо итерации являлся логарифмом, удовлетворяющим случаю 2. Более того, существует теорема в общем виде:
Теорема 1: пусть, где
и
— взаимно простые. Тогда
не выводимо над произвольным вектором
конечной длины n, где
— алгебраические целые числа
Напомню, что алгебраическим целым называется любое число, для которого существует многочлен с целыми коэффициентами и единичным старшим коэффициентом, такой что один из корней этого многочлена является данным числом.
При наличии формального доказательства этой теоремы, область поиска решений задачи Танежи можно будет значительно сузить. Один из методов поиска, позволяющий проверять только выводы, наиболее вероятные для получения искомого значения, называется «методом призраков и теней» и предложен мной.
Определение: Пусть на некоторой итерации некоторого вывода над
Определение: Пусть на некоторой итерации некоторого вывода над
Таблица призраков и теней для числа 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
Рассмотрим призрак:
Дискретные представления
Понятие полного дискретного представления
Все мы знаем о проблеме конечности для алгоритмов, о классе NP — задач, которые в теории требуют неограниченных аппаратных ресурсов для вычисления решения за линейно растущее время. Но на факультетах информатики, в научно-исследовательских институтах и на рабочих местах часто игнорируется не менее важная проблема на стыке программирования и информатики — проблема представимости данных.
Так, из математики нам известно, что рациональные числа вида
Можно выполнить несколькими способами. Каждый способ будет опираться на свою структуру данных и обладать определённой эффективностью. Вот некоторые варианты:
- Используем две переменные с плавающей точкой. Такой способ обладает очевидным преимуществом: на написание программы будет потрачено минимальное время. Но при последовательном вычислении вещественного приближения корня из 12, вещественного приближения корня из 3/4, потери точности при умножении двух вещественных и ещё больших потерях при приближенном вычислении мы можем получить вещественное число, близкое к корню из тройки, и оценив абсолютную погрешность вычисления определить вероятность выполнения равенства (1)
- Метод обратной проверки. Для него нам потребуются две переменные с плавающей точкой и две целочисленные переменные. Вычислим приближенное значение первым методом. Заметим, что в исходном выражении все значения под корнем являются рациональными числами, причём либо целыми, либо «конечными десятичными дробями малых порядков». Тогда применим метод обратной проверки. Рассмотрим наш пример пошагово:
- Исходное выражение представляем как
; найдем
в целых как
- Представим правую часть исходного выражения:
как
; Вычислив
в целых, получим:
- Вычисляем в целых
и проверяем делимость результата на 4. Остаток равен 0, поэтому мы можем разделить в целых. Получим
; Сравниваем два целых значения, полученных на этапах 2 и 3 соответственно и получаем точный ответ: выражение (1) верно т.к.
верно
При рассмотрении примера пришлось выполнить больше операций и для создания программы потребуется больше времени, но результат работы алгоритма будет точным, а не вероятностным - Исходное выражение представляем как
- Используем «структуру Х». Опишем структуру данных с тремя целочисленными полями:
, которая будет представлять число:
Главная особенность такого представления: все начальные, промежуточные и конечные значения при работе алгоритма будут представимыми и операции над ними будут выполнены без погрешности. Действительно:
;
Для реализации такого алгоритма придётся описывать сложную систему правил выполнения операций над тройками, но готовая информационная модель позволит быстро и эффективно проверять корректность различных выражений, похожих на (1)
«Структура Х» — это наглядный пример структуры данных, являющейся полным дискретным представлением. Теория дискретных представлений иррациональных и трансцендентных чисел — новая область дискретной математики, которой должно уделяться больше внимания.
Определение: пусть для решения задачи
- алгоритм
, реализующий задачу
на языке L остановится с выдачей корректного результата (соответствующего формату вывода, однозначно интерпретируемого и являющегося решением задачи
над данным вектором входных значений)
- для каждого этапа работы алгоритма Alg, значения всех инициализированных переменных типа
(результаты промежуточных вычислений) могут быть однозначно интерпретированы, их численное значение может быть точно восстановлено и использовано при ручной трассировке алгоритма с сохранением корректного вывода
тогда формальное описание
Минимальное ПДП
Существуют формальные методы построения структур данных, удовлетворяющих критериям ПДП. Один из таких: метод конечного замыкания. Замыканием некоторого множества относительно набора операций считается множество всех чисел, которые можно получить, выполнив конечное количество разрешенных операций над элементами исходного множества. Например: для конечного множества {0, 1} и набора операций: бинарное сложение и унарный минус замыканием будет множество
В методе конечного замыкания нас интересует множество
Для задачи Танежи метод конечного замыкания не применим из-за большого размера булеана для замыкания
Определение: Пусть
тогда будем называть элемент
На самом деле, задача Танежи, в том виде, в котором она изложена в разделе «точная формулировка и первые обобщения» является задачей о полном дискретном представлении, а структура данных NumEx, использованная в алгоритмах перебора выводов Num_2 и Num_3 является примером структуры данных, не являющейся полной даже на одном единственном векторе
Новая трансцендентология
О конечно трансцендентных и в точности трансцендентных числах
Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача. Так было с формальным обоснованием невозможности построения квадратуры круга циркулем и линейкой, с малой проблемой Гольдбаха и рядом других математических проблем. Так происходит и сегодня. Постановка задачи о представлении натуральных чисел при помощи семи операций над некоторым начальным вектором, подарила миру не только красивые частные решения и загадочную константу 10958, но и особый подход к классификации величин, значения которых не всегда могут быть записаны в явном виде. Так, доказано, что радикальные числа имеют ненулевое пересечение с множеством алгебраических чисел, но не входят в последнее полностью.
При написании программ, которые неизбежно по условию задачи должны производить вычисления, содержащие числа
Очевидно, что ПДП минимальное в случае с трансцендентными числами может не являться оптимальным ПДП с точки зрения временной сложности для некоторой реализации алгоритма на императивном декларативном языке.
Определение: пусть
Определение: пусть
Определение: число
Определение: число
С введением понятия конечно трансцендентного числа становится возможным оперировать точными значениями некоторых трансцендентных чисел, не используя при этом их символы. В общем виде утверждается, что для некоторых подмножеств множества конечно-трансцендентных чисел существуют непустые множества задач
Тау-выражения
Итак, в множестве трансцендентных чисел можно выделить на 3 непересекающихся (по построению) подмножества, объединение которых будет совпадать со множеством всех трансцендентных чисел, а именно:
- конечно-трансцендентные числа
- в-точности-трансцендентные числа
- комплексно-трансцендентные числа
И если для конечно-трансцендентных мы можем построить ПДП по методу конечных замыканий и попытаться его минимизировать, то для в-точности-трансцендентных (к которым, помимо очевидных значений
Определение:
Определение:
где
Для
Определение:
Также определим понятия правого и левого мажора и правого дополнения для
Примеры
Определение: главными слагаемыми
и
будем называть элементы вида:
Один из способов записи
Таким образом, множество
Использование порядкового номера
Теорема 2. При ограничении порядка всех тау-выражений некоторым числомдля множества задач
, ПДП для которых представляет все такие выражения, существует реализация
на императивном декларативном языке
для некоторого алгоритма
, такая что для входной строки — описания на любом императивном декларативном языке
ПДП структуры данных некоторой задачи
из A, алгоритм остановится с выводом строки — описания на языке
ПДП минимального для структуры данных алгоритма
— реализации алгоритма
решения задачи
на языке
.
Рассматривая задачу Танежи в восходящем порядке, важно понимать, что ни один из элементов входного вектора итераций (1), (2) и (3) не содержит (доказывается перебором всех таких итераций) трансцендентных элементов. Из определения конечной трансцендентности и на основании вышесказанного следует невыводимость
Общая теорема «О замыканиях конечных множеств трансцендентных чисел»
Определение: будем называть
численно равно одному из значений:
и
и правый мажор
определён и нормален
, левый мажор
определён и нормален, правое дополнение
определено и нормально и алгебраические представления левого мажора
и правого дополнения
не содержат подобных главных слагаемых.
Заметим, что нормальность
Примеры:
Определение:
где
Теорема 3. Всякое счётное подмножество множества-форм конечного порядка включает конечное число
-форм, имеющих хотя бы один корень.
Напомню, что счётным называется множество, которое можно поставить во взаимно-однозначное соответствие с множеством
Теорема 4. Пусть— некоторое множество действительных чисел, удовлетворяющее следующим условиям:
конечно или счётно
содержит не менее одного в точности трансцендентного элемента
- замыкание
множества
относительно набора бинарных операций: сложение и возведение в степень — континуально
тогда всякое счётное подмножество множествавключает конечное число конечно-трансцендентных элементов.
Важным следствием из теоремы 3 является существование ПДП минимального для алгоритмов, производящих вычисления только над алгебраическими и конечно-трансцендентными числами. Теорема 4 даёт общее представление о распределении конечно-трансцендентных чисел среди всех действительных трансцендентных чисел и ценна как теоретический инструмент для классификации групп, колец и замыканий относительно возведения в степень, содержащих трансцендентные элементы.
Итоги
Теория конечно-трансцендентных чисел как следствие из задачи Танежи и часть нового математического аппарата, необходимого для разрешения проблемы числа 10958 — важный инструмент, практическое применение которого в программировании и теоретическая значимость для топологии как науки трудно недооценить. Существуют исчерпывающие классификации рациональных, алгебраических чисел, детально изучены комплексные числа и функции над ними, и только трансцендентные числа остаются для современных математиков загадкой. Поиск корней произвольных
Сама задача Танежи обнажает проблему полного дискретного представления и показывает несостоятельность популярных методов описания структуры данных при решении математических задач на ПК. Так, для полного перебора всех выводов задачи Танежи над вектором
При поверхностном рассмотрении проблемы числа 10958 в статьях математиков-популяризаторов отмечалась лишь проблема «астрономических чисел» — так называют числа (чаще всего целые), десятичная запись которых невозможна. Яркие примеры — число
С одной стороны, научно-популярная математика воспитывает всё новые поколения ферматистов, что негативно сказывается на имидже профессиональной науки. С другой — привлечение внимания многомиллионной аудитории к нерешённым математическим проблемам порождает множество альтернативных взглядов на формулировки и возможные пути решения, и часть таких идей ложится в основу трудов математиков-профессионалов. Так было с задачей Эрдеша, и так сегодня любительская работа Индера Танежи о замечательных представлениях целых чисел способна изменить современную математику и подарить IT-сфере новый подход к описанию структур данных.