Послідовність занадто мета

Leaky Nun 09/11/2017. 6 answers, 2.053 views
code-golf sequence

Почнемо з порожньої 1-індексованої послідовності:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,... 

На n- м кроці ми заповнюємо всі а (n) заголовки з цілими числами більше, ніж 1, починаючи з першого залишкового порожнього, де a (n) - n- й запис у послідовності.

Після першого кроку:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,... 

Зверніть увагу, що a (1) має бути 2, тому що перше ціле число більше 1 становить 2.

На другому кроці ми заповнюємо всі (2) заголовки. Буде очевидним, що (2) має бути 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,... 

На третьому кроці ми заповнюємо всі (3) заголовки. З послідовності, a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,... 

На четвертому кроці ми заповнюємо всі (4) заголовки. З послідовності, a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,... 

Врешті-решт:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,... 

Завдання

Дано n, повертаємо n- й елемент послідовності.

Перші 10 000 000 умов цієї послідовності можна знайти тут .

Це . Найкоротша відповідь у байтах перемагає. Стандартні лазівки застосовуються.

5 Comments
Leaky Nun 06/20/2017
@LuisMendo Дякую, я додав його.
Dead Possum 06/20/2017
Просто цікаво, що неправильно виключив г-н Оне з послідовності?
Leaky Nun 06/20/2017
@DeadPossum добре, якщо ви заповните кожен порожнім, то ви зробите в одному кроці.
2 Leaky Nun 06/20/2017
@DeadPossum Якщо a (n) дорівнює 1, то n-й крок заповнить кожен залишок порожнім, припиняючи генерацію.
1 Leaky Nun 06/20/2017
@QBrute Я представив список перших 10 000 000, зв'язаних у питанні; просто сюжет їх.

6 Answers


Anders Kaseorg 06/20/2017.

Haskell , 80 67 байт

 g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m 

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

Haskell є ідеальною мовою для визначення нескінченного списку з точки зору себе.

5 comments
1 Julian Wolf 06/20/2017
Враховуючи, що зв'язок TIO працює як і очікувалося, я думаю, що моє запитання має бути: Чи можете ви додати пояснення того, як це працює?
2 Anders Kaseorg 06/20/2017
@JulianWolf Схоже, ви незнайомі з охороною картин. pattern1 | let pattern2 = expr2 = expr1 pattern1 | let pattern2 = expr2 = expr1 означає те ж саме, що і pattern1 = let pattern2 = expr2 in expr1 (з тієї ж причини, що [expr1 | let pattern2 = expr2] означає те ж саме, що [let pattern2 = expr2 in expr1] ).
1 Ørjan Johansen 06/20/2017
Я повинен пам'ятати, let захисники шаблону (особливо, що вони можуть виконувати функції)! Крім того, m=2:2:2`drop`g m - це байт коротший.
1 Ørjan Johansen 06/20/2017
(!!)$0:m менше двох байтів.
1 Ørjan Johansen 06/20/2017
Насправді, ви можете скинути 2:2: матеріал цілком з трохи більше ляпів: g ~(a:b)|... і m=g m .

Doorknob 06/20/2017.

C 123 байт

 f(n)NO 

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

Проходження

 f(n)NO 

через коротке замикання, а потім через закони Де Моргана та той факт, що 0 - фальсифікація в C:

 if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
} 

Це по суті говорить: "Якщо цей пробіл порожній, збільште k . А якщо k раніше був кратний розміру кроку, запустіть таке твердження". Отже, ми запускаємо твердження на кожному елементі step size , який точно описує послідовність. Сама заява проста. все це генерувати 2 , 3 , 4 , ....

 n=p[n-1];} 

Використовуючи складний метод-return-without-return, який працює з gcc , ми "повертаємо" останній елемент перших n термінів у послідовності, який, як виявляється, є n м терміном.


Anders Kaseorg 06/20/2017.

Pyth, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1 

Спробуйте його в Інтернеті

Як це працює

Замість того, щоб обдурювати списки, це використовує звичайну рекурсивну формулу.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input()))) 

xnor 06/20/2017.

Haskell , 67 байт

 0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j 

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

Рекурсивне арифметичне рішення, яке вийшло в основному тим же способом, як і відповідь Піт на запитання Андера Казерога .

Цей код покритий бородавками - потворними частинами, які виглядають так, як їх можна було б відірватися від гольфу, але я не бачив, як це зробити.

Функція i%j дійсно хоче використати охорону, щоб перевірити, чи mod i(f j)>0 і оцінити один з відповідних двох виразів. Але обидва вирази використовують div i(f j) . Зв'язування того, що в охоронці не буде застосовуватися з обох сторін. Наскільки я знаю, охоронець не може бути "розподілений" над іншими охоронцями. let і where занадто довгі Таким чином, last код використовується для вибору одного з двох виразів, тоді як охоронець прив'язує змінну. Ух

В ідеалі ми будемо використовувати divMod оскільки використовуються як div і mod , але (d,m)<-divMod ... є довгим висловом. Замість того, щоб перевірити, чи мода, коли значення дільника перевищує початкове значення, ми перевіряємо, що мод не відрізняється від нуля.

0%j=2 справа не потрібна, якщо Haskell короткозамкнутий div 0 , який він не має. Файл .pred перетворює 1-індексований вхід на нульовий індекс, або в будь-якому місці буде -1 корекція.

4 comments
Ørjan Johansen 06/21/2017
Якщо ви ввімкнете індексування % 1, то вам потрібно 5 байт корекції - це просто зв'язок. However , ви можете вставити f в % безкоштовно, а потім f стає анонімним, тому ви в цілому зберігаєте два байти.
xnor 06/21/2017
@ ØrjanJohansen Що ви маєте на увазі тут за інлайн? Я не бачу, як змінити посилання на f без втрати байтів.
Ørjan Johansen 06/21/2017
divMod здається, один байт дешевше, тому що це дозволяє розгалужувати з !!(0^m) . Поки що у мене є: 1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);‌​(%1)
Ørjan Johansen 06/21/2017
Як ви бачите, inlining передбачає 1-reindexing, що видаляє .pred .

Arnauld 06/20/2017.

JavaScript (ES6), 98 93 91 байт

Рекурсивна функція, яка зупиняється, як тільки результат є доступним.

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

Альтернативна версія, 90 байт

Suggested by Shaggy for -1 byte

Це потрібно назвати за допомогою f(n)() . Хоча відповідний пост в meta на даний момент дає позитивну оцінку, цей синтаксис, очевидно, оскаржується.

 n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

Демонстрація

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

for(n = 1; n <= 50; n++) {
  console.log('a[' + n + '] = ' + f(n));
} 

2 comments
Shaggy 06/20/2017
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k‌​?c:++v:(i=1,v=2),i=0‌​,k=a[p]||2)) повинна працювати на 92 байти. Зателефонуйте йому за допомогою f(n)() .
Arnauld 06/20/2017
@Шаггі Спасибо! Додано як альтернативну версію.

Xanderhall 06/20/2017.

Java 8, 124 байти

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];} 

Лямбда-вираз.

Створює цілий масив і постійно заповнює його, доки n-й значення не буде заповнено.

Попередньо оголошуючи змінні вгорі, щоб зменшити стільки декларацій, скільки можливо, оскільки кожна int витрачає 4 байти простору, а не додавання ,n що дорівнює 2.

У j -й ітерації обчислення кількість "заготовок", яку треба пропустити, дорівнює a[j] (або 2, якщо порожній). Звідси випливає, що якщо перший пробіл, який ми повинні заповнити, знаходиться в положенні k , k * a[j] дає нам "крок" ( s ).

Related questions

Hot questions

Language

Popular Tags