Построение ряда чисел по некоторому алгоритму , программа работает под 30 мин - странно это все

[FasterHarder]

Всем хай! Сходу к делу.
Есть такая задача.
Строится некий ряд Bn: b1 = 1, b2 = 2, а, начиная с 3его слагаемого правила такие:
• идет наименьшее положительное число, которое еще не добавлялось в числовой ряд;
• НОД (bn, b(n-1)) > 1
То есть начало ряда будет таким: 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15 и т.д.
Пользователь вводит натуральное число до 3млрд (это количество запросов) и затем каждый запрос состоит из натурального числа b. И надо для всех заданных b найти номер этого числа в этом ряду.
Например: 2 9 4
2 – будет 2 запроса
9 – пользователя интересует, под каким номером стоит число 9 (ответ будет 6)
4 – пользователя интересует, под каким номером стоит число 4 (ответ будет 3)
У пользователя есть право запрашивать числа до 280 000 включительно! Например, он может захотеть узнать, под каким номером число 273 909 было включено в последовательность.

Программу я написал, выдает корректные результаты, но работает для больших чисел чуть ли не по 15-25 минут. Ужас.
Основная структура данных, которую использую (дин.одномерный массив):
0 1 2 4 6 3 9 в качестве значений выступает число, выражающее номер числа в ряду
0 1 2 3 4 5 6 в качестве индекса взято число, добавляемое в ряд

самый первый элемент массива - фиктивный (не юзается).
те элементы, которые не добавлены в ряд, имеют значение = 0. Приходится постоянно отслеживать первый элемент, у которого значение = 0 (кроме 1го элемента, который фиктивный).
Как я понимаю, ведь здесь нет формулы, которая позволяет четко получить номер числа по значению. Например, пользователь хочет знать порядковый номер числа = 15 000 в ряду. 15 000 число было получено после добавления 14 999 числа и т.д. То есть в любом случае надо строить все цепочку чисел до нужного.
Также этот массив разреженный (не сильно правда). Также, например, число 200 000 примерно по счету добавляется в ряд под № 400 000.
Программа работает так: выясняю макс. число среди всех запросов от пользователя. До этого числа (читай, индекса) заполняю порядковыми номерами все элементы массива. После этого вывожу результат массив[число заданное пользователем].
А вопрос у меня такой: это нормально, что программа для «худшего» случая работает под 30минут? Мне, кажется, что, точно нет. Может здесь нужна совсем другая структура данных...
P.S. Ограничение по памяти: где-то около 200 «метров».

[Mikle]

Цитата FasterHarder @ 30.10.21, 06:00

НОД (bn, b(n-1)) > 1

Можно это расшифровать?

[Славян]

Цитата Mikle @ 30.10.21, 09:34

Можно это расшифровать?

Число и предыдущее к нему не должны быть взаимно простыми.

[OpenGL]

Неплохая задачка, немного подумать пришлось. Можно действительно просто все числа сгенерировать до максимально запрошенного пользователем, только делать надо это оптимально.

1. Хранить числа можно именно так, как это делаешь ты - val[i] = 0, если числа ещё не было, или равно порядковому номеру числа, если оно уже было (ты описал сумбурно, но я тебя именно так понял). Массив с номерами чисел (т.е. с ответами на запросы пользователя) проще всего будет получить потом по этому массиву.
2. Также понадобится хранить какой-нибудь ассоциативный массив, в котором ключ - простое число, а значение - минимальное число, которое ещё не добавлялось в ряд и которое кратно этому простому числу.
3. Теперь можно генерировать следующее число по текущему. Условие НОД(текущее, следующее) > 1 означает, что существует простое число, которое делит одновременно и текущее число, и следующее. А значит можно действовать так:
   • Возьмём все простые делители текущего числа
   • Обновим для этих чисел минимумы в ассоциативном массиве из п.2. Для этого просто возьмём текущий минимум, и будем его увеличивать на это самое простое число до тех пор, пока не получим число, которого ещё не было
   • Минимум из этих чисел и будет следующим

Это должно сработать быстро и легко уложиться в ограничения.

[OpenGL]

На oeis есть эта последовательность