@mrxtraf

Как найти все возможные варианты суммирования и вычитания натуральных чисел с минимальным хранением начальных?

С двумя любыми натуральными числами можно сделать сложение или вычитание. Единственное нельзя суммировать и вычитать с самого себя.
Будем считать их начальными.
К примеру. Два числа
2 и 3 , с этой пары будут известны числа
2+3 = 5
3-2 = 1
Отрицательные числа не учитываются.
Допустим добавляем ещё одну начальную 8, тогда у нас получаются такие дополнительные варианты.
8+2 = 10
8+3 = 11
8-2 = 6
8-3 = 5
То есть на данный момент мы знаем такую последовательность.
1, 2, 3, 5, 6, 8, 10, 11
Где начальные 2, 3, 8
При этом неизвестны 4, 7, 9
Так вот задача заполнить полностью ряд простых чисел, с хранением наименьшего кол-ва начальных. И что бы было наименьшее кол-во пересечений.
Под пересечением имеется ввиду такое.
Добавляем начальное число 12, чтобы найти 4, получаем такие варианты
12+2 = 14
12+3 = 15
12+8 = 20
12-2= 10 (пересечение)
12-3= 9
12-8= 4
4, 9 мы нашли, но 10 получается уже пересечением, двух возможных комбинаций.
Можно конечно это все делать перебором, с хранением матрицы, и это я реализовывал до определенных размеров. Но заполнение нужно для больших чисел от 100 бит и далее. Никакой памяти не хватит держать такую матрицу, даже если усекать найденное начало.
Может есть какой логарифм или алгоритм для нахождения таких чисел?
Я пробовал ряды простых чисел разных алгоритмов, ничего не подходит.
Бьюсь уже давненько над задачей.
  • Вопрос задан
  • 72 просмотра
Пригласить эксперта
Ответы на вопрос 1
@mayton2019
Ent. Software engineer. Oracle. SQL. BigData.
По сути задача звучит так.

Разработать непозиционную систему счисления для представления любого простого числа наименьшим числом символов системы.

Непозиционная в качестве примера - это римская. I/II/III символы. Или система фибоначчи 1,1,2,3,5,8. В твоём случае символ включает в себя еще и знак плюс-минус.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы