Удалить каждый (k+1)-й оставшийся элемент в k-м проходе натуральных чисел

В серии натуральных чисел мы должны удалить каждый 2-й элемент в 1-м проходе. Затем в оставшихся элементах удалите каждый третий элемент во втором проходе. Затем на K-м проходе удалите каждый (k+1)-й элемент из оставшихся элементов.

Сериал будет таким

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, ...

После 1-го прохода (после удаления каждого 2-го элемента),

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, ...

После 2-го прохода (после удаления каждого 3-го элемента)

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ...

После 3-го прохода (после удаления каждого 4-го элемента)

1, 3, 13, 15, 19, 25, 27, ...

Итак, после прохождения бесконечности он станет

1, 3, 7, 13, 19, 27, 39, 49, 63, 79, ...

Этот ряд также называют ситом Флавия-Иосифа.

Решение для этого, чтобы найти 6-й элемент в ряду:

  • do 6^2 = 36
  • перейти к кратному 5, что дает 35
  • затем до кратного 4 = 32
  • затем до кратного 3 = 30
  • затем до кратного 2 = 28
  • затем до кратного 1 = 27
  • и так 6-е счастливое число 27.

Хотя это работает, я не понимаю, как работает решение?

Программа C для этого,

int calc(int n)
{
   if (n == 1) return 1;
   return calc_rec(n*n, n-1);
}

int calc_rec(int nu, int level)
{
   int tmp;
   if (level == 1) return (nu-1);
   tmp = nu % level;
   return calc_rec(nu - (tmp ? tmp : level), level-1);
}

Ссылка, объясняющая это http://oeis.org/A000960


algorithm math sieve number-sequence
person viji    schedule 11.05.2012    source источник
comment
Возможно, вам будет полезно задать этот вопрос на math.stackexchange.com.   -  person Shahbaz    schedule 11.05.2012
comment
Я сделал это. math.stackexchange.com/questions/143876/   -  person viji    schedule 11.05.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

Назовем начальную серию, содержащую все целые числа, S[0], затем S[1] — серию после первого прохода, S[2] — серию после второго прохода и так далее.

В серии S[0] N-е целое число (начиная с нуля) равно N + 1.

1 2 3 4 5 6 7 8 9 10 ...

В серии S[1] N-е целое число получается путем доступа к (2N)-му элементу из S[0]. Примечание 2N = N+(N деление 1). «div» — целочисленное деление, т. е. деление, при котором остаток отбрасывается.

1 3 5 7 9 11 13 15 17 ...

В серии S[2] N-е целое число получается путем доступа к N+(N div 2)-му элементу из S[1].

1 3 7 9 13 15 19 21 ...

В серии S[3] N-е целое число получается путем доступа к N+(N делению 3)-го элемента из S[2] и так далее.

1 3 7 13 15 19 ...

Таким образом, вы получаете следующую рекурсивную процедуру:

get_number(int series, int N):
   if (series == 0):
      return N + 1
   else:
      return get_number(series - 1, N + floor(N / series))

Но обратите внимание, что когда серия> N, пол (N / серия) тождественно равен нулю, поэтому вы всегда можете вызывать это как get_number (N, N).

Например,

get_number(5, 5) = get_number(4, 6) = get_number(3, 7) =
  get_number(2, 9) = get_number(1, 13) = get_number(0, 26) = 27.

Это показывает, как вы можете получить «27» как 6-й (5, но индексация с отсчетом от нуля) из потока.

person Antti Huima    schedule 11.05.2012