Ваша задача - реализовать целочисленную последовательность A130826 :

a _n - наименьшее положительное целое число, такое, что a _n - n - целое число, кратное 3, и двойное число делителей (a _n - n) / 3 дает n- ^й член в первых различиях последовательности, произведенной Flavius Сито Иосифа.

Потерян еще? Ну, это на самом деле довольно легко.

Иосиф Флавий сито определяет целое последовательности следующим образом .

1. Начните с последовательности натуральных чисел и установите k = 2 .

2. Удалите каждое k- ^е целое число последовательности, начиная с k- ^го .

3. Увеличьте k и вернитесь к шагу 2.

f _n - это n- ^е целое число (с 1 индексом), которое никогда не удаляется.

Если - как обычно - σ ₀ (k) обозначает число положительных делителей целого числа k , мы можем определить a _n как наименьшее положительное целое число такое, что 2σ ₀ ((a _n - n) / 3) = f _{n + 1} - ф _н .

Вызов

Написать программу или функцию , которая принимает целое положительное число п в качестве входных данных и выводит или возвращает в _п .

Применяются стандартные правила игры в гольф . Пусть победит самый короткий код!

Отработанные примеры

Если мы удалим каждый второй элемент натуральных чисел, мы останемся с

 1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...

После удаления каждого третьего элемента остатка, мы получаем

 1  3  7  9 13 15 19 21 25 27 31 33 37 39 ...

Теперь, удаляя каждый четвертый, затем пятый, затем шестой элемент, мы получаем

 1  3  7 13 15 19 25 27 31 37 39 ...
 1  3  7 13 19 25 27 31 39 ...
 1  3  7 13 19 27 31 39 ...
 1  3  7 13 19 27 39 ...

В последнем ряду показаны термины от f ₁ до f ₇ .

Различия последовательных элементов этих терминов

 2  4  6  6  8 12

Разделив эти прямые разницы на 2 , мы получим

 1  2  3  3  4  6 

Это целевые значения делителей.

• 4 - первое целое число k такое, что σ ₀ ((k - 1) / 3) = 1 . В самом деле, сг ₀ (1) = 1 .
• 8 - первое целое число k такое, что σ ₀ ((k - 2) / 3) = 2 . В самом деле, сг ₀ (2) = 2 .
• 15 - первое целое число k такое, что σ ₀ ((k - 3) / 3) = 3 . В самом деле, сг ₀ (4) = 3 .
• 16 - первое целое число k такое, что σ ₀ ((k - 4) / 3) = 3 . В самом деле, сг ₀ (4) = 3 .
• 23 - первое целое число k такое, что σ ₀ ((k - 5) / 3) = 4 . В самом деле, сг ₀ (6) = 4 .
• 42 - первое целое число k такое, что σ ₀ ((k - 6) / 3) = 6 . В самом деле, сг ₀ (12) = 6 .

Контрольные примеры

   n     a(n)

   1        4
   2        8
   3       15
   4       16
   5       23
   6       42
   7       55
   8      200
   9       81
  10       46
  11      119
  12      192
  13      205
  14   196622
  15    12303
  16       88
  17      449
  18      558
  19      127
  20     1748
  21   786453
  22       58
  23     2183
  24     3096
  25     1105
  26   786458
  27 12582939
  28      568
  29     2189
  30     2730

Желе, 30 29 27 25 байт

Сохранено 2 байта благодаря уведомлению @Dennis Ædи еще 2 байта для объединения двух цепочек.

RUð÷‘Ċ×µ/
‘Ç_ÇH0Æd=¥1#×3+

Попробуйте онлайн!

Это было, наверное, самое веселое, что я когда-либо имел с Желе Я начал со второй строки, которая вычисляет f _n из n по формуле OEIS, и это довольно красиво.

объяснение

RUð ÷ 'µ × µ / Вспомогательная ссылка для расчета F n . Аргумент: n
R Получить числа [1..n]
 U Обратный
        / Уменьшить на «округление до следующих 2 кратных»:
   ÷ разделить на следующее число
    Инкремент, чтобы пропустить несколько
     Ċ Ceil (округление вверх)
      × Умножить на следующее число

'Ç_ÇH0Æd = ¥ 1 # × 3 + Основная ссылка. Аргумент: n
Инкремент n
 Ç Рассчитать F n + 1 
   Ç Рассчитать F n
  _ Вычесть
    H разделить на 2
     0 1 # Начиная с 0, найдите первого кандидата на (a n -n) / 3
                   это удовлетворяет ...
      Æd σ 0 ((a n -n) / 3)
        = = (F n + 1 -F n ) / 2
            × 3 Умножьте на 3, чтобы превратить (a n -n) / 3 в n -n
              + Добавить n, чтобы превратить n- n в n

Python 2 , 121 119 118 байт

n=input();r=range(1,4**n);d=s,=r*1,
for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,
print d.index(s[n]-s[n-1])*3+n

Время выполнения должно быть примерно O (16 ⁿ ) с использованием O (4 ⁿ ) памяти. Замена 4**nна 5<<n- что я считаю достаточным - значительно улучшила бы это, но я не уверен, что он работает для сколь угодно больших значений n .

Попробуйте онлайн!

Асимптотическое поведение и верхние оценки _n

Определите b _n как (a _n - n) / 3 , т. Е. Наименьшее положительное целое число k такое, что σ ₀ (k) = ½ (f _{n + 1} - f _n ) .

Как отмечено на странице OEIS, f _n ~ ¼πn ² , поэтому f _{n + 1} - f _n ~ ¼π (n + 1) ² - ¼πn ² = ¼π (2n + 1) ~ ½πn .

Таким образом, ½ (f _{n + 1} - f _n ) ~ ¼πn . Если фактическим числом является простое число p , наименьшее положительное целое число с делителями p равно 2 ^p-1 , поэтому b _n можно аппроксимировать как 2 ^{c _n} , где c _n ~ ¼πn .

Поэтому b _n <4 ⁿ будет выполняться для достаточно больших n , и учитывая, что 2 ^¼πn <2 ⁿ << (2 ⁿ ) ² = 4 ⁿ , я уверен, что нет контрпримеров.

Как это работает

n=input();r=range(1,4**n);d=s,=r*1,

Это устанавливает несколько ссылок для нашего итеративного процесса.

• n - пользовательский ввод: положительное целое число.

• r - список [1, ..., 4 ⁿ - 1] .

• s является копией r .

  Повторение списка один раз с r*1созданием мелкой копии, поэтому изменение s не изменит r .

• d инициализируется как кортеж (ы) .

  Это первое значение не важно. Все остальные будут иметь число делителей положительных чисел.

for k in r:del s[k::k+1];d+=sum(k%j<1for j in r)*2,

Для каждого целого числа k от 1 до 4 ⁿ - 1 мы делаем следующее.

• del s[k::k+1]берет каждое (k + 1) ^-ое целое число в s - начиная с (k + 1) ^-ого - и удаляет этот фрагмент из s .

  Это простой способ хранения начального интервала сита Флавиуса Иосифа в с . Он будет вычислять намного больше, чем требуется n + 1 начальных членов, но использование одного forцикла для обновления как s, так и d экономит некоторые байты.

• d+=sum(k%j<1for j in r)*2,подсчитывает, сколько элементов r делит k равномерно и добавляет 2σ ₀ (k) к d .

  Поскольку d был инициализирован как одноэлементный кортеж, 2σ ₀ (k) сохраняется в индексе k .

print d.index(s[n]-s[n-1])*3+n

Это находит первый индекс f _{n + 1} - f _n в d , который является наименьшим k таким, что 2σ ₀ (k) = f _{n + 1} - f _n , затем вычисляет a _n как 3k + 1 и печатает результат.

Java 8, 336 , 305 , 303 , 287 , 283 279 байт

57 байт удалено благодаря Kritixi Lithos

Golfed

class f{static int g(int s,int N){return s<1?N+1:g(s-1,N+N/s);}static int h(int k){int u=0,t=1,i;for(;u!=(g(k,k)-g(k,k-1))/2;t++)for(i=1,u=0;i<=t;)if(t%i++<1)u++;return 3*t-3+k;}public static void main(String[]a){System.out.print(h(new java.util.Scanner(System.in).nextInt()));}}

Ungolfed

class f {
    static int g(int s,int N){return s < 1 ? N + 1 : g(s - 1, N + N / s);}

    static int h(int k) {
        int u = 0, t = 1, i;
        // get the first number with v divisors
        while(u != (g(k, k) - g(k, k - 1))/2){
            u = 0;
            for (i = 1; i <= t; i++)
                if (t % i < 1) u++;
            t++;
        }
        // 3*(t-1)+k = 3*t+k-3
        return 3 * t + k - 3;
    }

    public static void main(String[] a) {
        System.out.print(h(new java.util.Scanner(System.in).nextInt()));
    }
}

Mathematica, 130 116 106 103 байт

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[Tr[2+0Divisors@k]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

или

3Catch@Do[f=#2⌈#/#2+1⌉&~Fold~Reverse@Range@#&;If[2DivisorSum[k,1&]==f[#+1]-f@#,Throw@k],{k,∞}]+#&

Закончилось почти идентично коду Jelly @ Pietu1998 ...

объяснение

Catch@

Catchчто бы то ни было Throw(брошено).

Do[ ... ,{k,∞}]

Бесконечный цикл; kначинается с 1и увеличивает каждую итерацию.

f= ...

Назначить f:

Reverse@Range@#

Найти {1, 2, ... , n}. Переверните это.

#2⌈#/#2+1⌉&

Функция, которая выводит ceil (n1 / n2 + 1) * n2

f= ... ~Fold~ ... &

Назначьте fфункцию, которая рекурсивно применяет вышеуказанную функцию к списку из двух вышеперечисленных шагов, используя каждый выход в качестве первого ввода и каждый элемент списка в качестве второго ввода. Начальный «вывод» (первый ввод) является первым элементом списка.

Tr[2+0Divisors@k]==f[#+1]-f@#

Проверьте, kравно ли число делителей в два раза f (n + 1) - f (n).

If[ ... ,Throw@k]

Если условие является True, Throwзначениеk . Если нет, продолжайте цикл.

3 ... +#&

Умножьте вывод на 3 и добавьте n.

130-байтовая версия

Catch@Do[s=#+1;a=k-#;If[3∣a&&2DivisorSigma[0,a/3]==Differences[Nest[i=1;Drop[#,++i;;;;i]&,Range[s^2],s]][[#]],Throw@k],{k,∞}]&

Perl , 6 , 154 149 136 107 байт

->\n{n+3*first ->\o{([-] ->\m{m??&?BLOCK(m-1).rotor(m+0=>1).flat!!1..*}(n)[n,n-1])/2==grep o%%*,1..o},^Inf}

Ungolfed:

-> \n {                    # Anonymous sub taking argument n
  n + 3 * first -> \o {    # n plus thrice the first integer satisfying:
    (                      #
      [-]                  #
      -> \m {              # Compute nth sieve iteration:
        m                  # If m is nonzero,
          ?? &?BLOCK(m-1).rotor(m+0=>1).flat # then recurse and remove every (m+1)-th element;
          !! 1..*          # the base case is all of the positive integers
      }                    #
      (n)                  # Get the nth sieve
      [n,n-1]              # Get the difference between the nth and (n-1)th elements (via the [-] reduction operator above)
    ) / 2                  # and divide by 2;
    ==                     # We want the number that equals
    grep o %% *, 1..o      # the number of divisors of o.
  }
  ,^Inf
}

05AB1E ,35 34 39 байт

1Qi4ë[N3*¹+NÑg·¹D>‚vyy<LRvy/>îy*}}‚Æ(Q#

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

объяснение

Работает как 2 последовательно называемые программы. Первый вычисляет F _{п + 1} - Р _п , а второй определяет , а _п , основанный на определении его, используя BruteForce подход.

F _{n + 1} - F _n оценивается для каждой итерации, даже если она инвариантна для цикла. Это делает время кода неэффективным, но делает код короче.

Попробуйте онлайн!