Определите 1-индексированную последовательность следующим образом:

• A083569(1) = 1
• A083569(n)где nцелое число больше, чем 1наименьшее целое число m, не встречающееся ранее, например m+nпростое число.

Ваша задача взять nи вернуться A083569(n).

 n  A083569(n)
 1  1
 2  3
 3  2
 4  7
 5  6
 6  5
 7  4
 8  9
 9  8
10 13
11 12
12 11
13 10
14 15
15 14
16 21
17 20
18 19
19 18
20 17

Больше тестов можно найти здесь . Оригинальную последовательность на OEIS можно найти здесь .

Это код-гольф . Кратчайший ответ в байтах побеждает. Применяются стандартные лазейки .

Haskell , 87 86 83 80 74 69 байт

Спасибо xnor за предложенные изменения, которые сохранили 3 байта!

f n=[m|m<-[1..],all((>0).mod(n+m))[2..n+m-1],all((/=m).f)[1..n-1]]!!0

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

Я новичок в Haskell, и Haskell в гольф, обратная связь приветствуется!

объяснение

Мы определяем функцию f n. Мы определяем, f nчтобы быть первым элементом !!0списка:

[m|m<-[1..],all((>0).mod(n+m))[2..n+m-1],all((/=m).f)[1..n-1]]

Сломано это:

[m|          # Numbers m
m<-[1..],    # From the integers greater than 0
all          # Forall x
(>0).mod(n+m)# n+m mod x is not zero
[2..n+m-1]   # from the integers from 2 to n+m-1
all          # Forall
((/=m).f)    # when f is applied the result is not m
[1..n-1]     # from the integers from 1 to n-1

Желе , 16 15 байт

Rɓ²R+⁸ÆPTḟḢṭµ/Ṫ

Предполагается, что A083569 (n) ≤ n² (последовательность, по-видимому, растет линейно).

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

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

Rɓ²R+⁸ÆPTḟḢṭµ/Ṫ  Main link. Argument: n

R                Range; yield [1, ..., n].
 ɓ               Begin a dyadic chain with swapped arguments.
            µ/   Reduce the range by that chain.
                 If we call the chain f, this computes f(2,1), then f(3,f(2,1)),
                 then f(4,f(3,f(2,1)), etc.
                 The left argument is an integer k, the right one an array A.
  ²                Square; yield k².
   R               Range; yield [1, ..., k²].
    +⁸             Add k, yielding [1+k, ..., k²+k].
      ÆP           Test each sum for primality.
        T          Truth; get all indices of 1‘s. This finds all m in [1, ..., k²]
                   such that m+k is prime.
         ḟ         Filterfalse; remove all resulting elements that appear in A.
          Ḣ        Head; extract the first remaining result.
           ṭ       Tack; append the extracted integer to A.
                 This computes the first n elements of the sequence.
              Ṫ  Tail; extract the last, n-th element.

Pyth - 18 17 15 байт

Спасибо @isaacg за то, что сэкономили мне два байта!

Вернувшись на этот сайт, немного поработав, будем надеяться, что игра в гольф будет продолжена.

esmaYf&-TYP_+Th

Попробуйте это онлайн здесь .

C # (.NET Core) , 169 байт

n=>{if(n<2)return 1;var p=new int[n-1];int i=0,j,s;for(;i<n-1;)p[i]=f(++i);for(i=1;;i++){for(j=2,s=i+n;j<s&&s%j++>0;);if(j==s&!System.Array.Exists(p,e=>e==i))return i;}}

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

До сих пор наиболее неэффективный способ расчета результатов, поэтому , пожалуйста , воздержитесь от расчета f(n)для n>=30этого кода. Первым шагом является рекурсивное вычисление значений от f(1)до, f(n-1)а затем переход к вычислению f(n)путем поиска первого, iтакого n+iкак простое число, iкоторого нет в предыдущем списке значений.

Сборка x86-64, 57 55 байт

Я новичок в гольф, поэтому комментарии / отзывы приветствуются.

Примечание: это оптимизировано для длины машинного кода, а не для длины исходного кода.

0: 89 f8 ff cf 74 32 97 89 fe 89 f1 ff c6 89 f0 99
1: f7 f1 85 d2 e0 f7 85 c9 75 ed 89 f9 ff c9 56 29
2: fe 56 57 51 89 fc e8 d3 ff ff ff 59 5f 5e 39 c6
3: e0 ef 96 5e 74 d1 c3

Определяет функцию, используя стандартное соглашение (то есть возвращаемое значение в eax, первый аргумент в edi, все регистры, сохраненные вызывающим абонентом, кроме ebx), которое принимает 32-разрядное целое число без знака и возвращает наименьшее m и т. Д.

Источник:

    .globl a083569
    // edi = original, probably don't touch
    // esi = candidate prime, if it's not a repeat we return edi-this
a083569:
    mov %edi, %eax
    dec %edi
    jz end
    xchg %eax, %edi
    mov %edi, %esi
primecheck:
    mov %esi, %ecx
    inc %esi
primeloop:
    mov %esi, %eax
    cdq
    div %ecx
    test %edx, %edx
    loopnz primeloop
/* end */
    // if esi isn't prime, then ecx is now one or greater.
    test %ecx, %ecx
    jnz primecheck
    // esi is now our target prime: check if it's not already one
    mov %edi, %ecx
    dec %ecx
    push %rsi   /* we need a flag-safe way to restore this later */
    sub %edi, %esi
chkdup:
    push %rsi
    push %rdi
    push %rcx
    mov %ecx, %edi
    call a083569
    pop %rcx
    pop %rdi
    pop %rsi
    cmp %eax, %esi
    loopne chkdup
/* end loop - chkdup */
    xchg %esi, %eax
    pop %rsi
    je primecheck
/* end outer loop - primecheck */
end:
    ret

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

Clojure, 158 155 байтов

#(loop[r[0 1]i 1](if(= i %)(last r)(recur(conj r(nth(for[j(range):when(=((set r)j)(seq(for[k(range 2(+ 1 i j)):when(=(mod(+ 1 i j)k)0)]j)))]j)0))(inc i))))

Это может все еще иметь немного жира, я не совсем доволен, (+ 1 i j)но это был самый простой способ справиться с базовым случаем n = 1и остальным. ((set r)j)возвращает nilif, если jего нет в наборе, а (seq ())в пустом списке также возвращает nil. Вычисляет n = 1000за 48 секунд.

Обновление: снято nilс =проверки, так как код работает правильно и без него.

Рубин , 62 + 8 = 70 байт

Использует -rprimeфлаг.

f=->n,o=[]{o<<f[n-1,o]if n>1;Prime.find{|i|i>n&&o|[i-n]!=o}-n}

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

Python, 194 170 110 байт

84 байта, сохраненные Leaky Nun

2 байта сохранены матеманданом

def s(n):
 a=[s(j)for j in range(1,n)];i=1
 while(i in a)|any((i+n)%j<1for j in range(2,i+n)):i+=1
 return i

Определяет функцию s (n), которая принимает число в качестве входных данных и возвращает A083569 (n).

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