Последовательность слишком мета

25

Начнем с пустой последовательности с 1 индексом:

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

На n- м шаге мы заполняем все пробелы a (n) целыми числами больше 1, начиная с первого оставшегося пробела, где a (n) - это n- ая запись в последовательности.

После первого шага:

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

Обратите внимание, что a (1) должно быть 2, потому что первое целое число больше 1 равно 2.

На втором шаге мы заполняем каждые a (2) пробелы. Будет очевидно, что a (2) должно быть 2.

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

На третьем шаге мы заполняем каждые a (3) пробелы. Из последовательности а (3) = 3.

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

На четвертом шаге мы заполняем каждые a (4) пробелы. Из последовательности а (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 членов последовательности можно найти здесь .

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

code-golf sequence Дрянная Монахиня
источник
@ LuisMendo Спасибо, я добавил это.
Утренняя монахиня
Просто любопытно, что плохого сделал г-н. Чтобы быть исключенным из последовательности?
Мертвый опоссум
@DeadPossum хорошо, если вы заполняете каждый пробел, то все готово за один шаг.
Дрянная монахиня
2
@DeadPossum Если a (n) равно 1, то n-й шаг заполнит каждый оставшийся пробел, завершив генерацию.
Утренняя монахиня
1
@QBrute Я предоставил список первых 10 000 000, связанных в вопросе; просто заговор их.
Дрянная монахиня

Ответы:

20

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 - идеальный язык для определения бесконечного списка с точки зрения самого себя.

Андерс Касеорг
источник
1
Учитывая, что ссылка TIO работает должным образом, я полагаю, что мой вопрос должен быть следующим: не могли бы вы объяснить, как это работает?
Джулиан Вольф
2
@JulianWolf Похоже, вы не знакомы с letохранниками. pattern1 | let pattern2 = expr2 = expr1означает то же самое, что и pattern1 = let pattern2 = expr2 in expr1(по той же причине, что [expr1 | let pattern2 = expr2]означает то же самое, что и [let pattern2 = expr2 in expr1]).
Андерс Касеорг
1
Я должен помнить letпаттерны (особенно, что они могут выполнять функции)! Кроме того, m=2:2:2`drop`g mявляется байтом короче.
Орджан Йохансен
1
(!!)$0:mна два байта короче.
Орджан Йохансен
1
На самом деле, вы можете отбросить 2:2:материал целиком с немного большей ленью: g ~(a:b)|...и m=g m.
Орджан Йохансен
10

C, 123 байта

f(n){int*p=calloc(n,4),i=0,j,k;for(*p=p[1]=2;i<n;++i)for(j=0,k=i/2?0:2-i;j<n;++j)p[j]||k++%p[i]||(p[j]=k/p[i]+2);n=p[n-1];}

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

Прохождение

f(n){int*p=calloc(n,4),

Выделите массив из n целых чисел для хранения первых n элементов последовательности. Это жесткие коды sizeof(int)как 4, что является безопасным допущением в большинстве случаев и, безусловно, я хочу сделать в контексте кода гольф. :)

i=0,j,k;

Все это счетчики: iдля индекса шага, на котором мы находимся, jдля циклического прохождения последовательности в поисках пустых мест и kдля подсчета количества пустых мест.

for(*p=p[1]=2;i<n;++i)

Прежде чем мы начнем наш основной цикл, мы пробираемся в инициализации первых двух элементов последовательности к 2. ( p[0]= *(p + 0)= *p.) Это сбрасывает счёт k, хотя, но ...

for(j=0,k=i/2?0:2-i;j<n;++j)

... мы также делаем скрытую инициализацию k, которая проверяет, iменьше ли она, 2и корректирует начальное значение, kесли так. Здесь также начинается внутренний цикл, который повторяется на протяжении всей последовательности на каждом этапе.

p[j]||k++%p[i]||(p[j]=k/p[i]+2);

Эта строка может действительно использовать некоторые объяснения. Мы можем расширить это до:

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

коротким замыканием, а затем законами де Моргана и тем фактом, что 0в C ложно:

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

По сути, это гласит: «если это пространство пустое, увеличивайте его k. И если kранее было кратно размеру шага, выполните следующую инструкцию». Следовательно, мы запускаем оператор для каждого элемента размера шага , что в точности соответствует последовательности. Само утверждение просто; все это будет генерировать 2, 3, 4, ....

n=p[n-1];}

Используя метод tricky-return-without-a-return, с которым gccмы работаем, мы «возвращаем» последний элемент первых n членов в последовательности, который оказывается n- м членом.

Дверная ручка
источник
3

Pyth, 29 байт

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())))
Андерс Касеорг
источник
3

Haskell , 67 байт

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

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

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

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

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

В идеале мы будем использовать, divModпотому что оба divи modиспользуются, но (d,m)<-divMod ...это длинное выражение. Вместо этого мы по счастливой случайности проверим, что мод ненулевой, посмотрев, не divпревышает ли значение делителя кратное исходному значению.

0%j=2Случае не будет необходимость , если Haskell короткого замыкания div 0, что это не так. В .predПреобразует 1-индексированный вход нуля индексированные, или иначе было бы -1поправки везде.

XNOR
источник
Если вы включите %1-индексированный, то вам нужно исправить пять байтов - что просто связывает. Тем не менее , вы можете встраивать fв %бесплатно, а затем fстановится анонимным, поэтому вы экономите два байта в целом.
Орджан Йохансен
@ ØrjanJohansen Что вы подразумеваете здесь под встроенным? Я не вижу, как изменить ссылки fбез потери байтов.
xnor
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)
Орджан Йохансен
Как видите, встраивание предполагает 1-переиндексацию, которая удаляет .pred.
Орджан Йохансен
2

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 байт

Предложил Шегги за -1 байт

Этот должен быть вызван с 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))

демонстрация

Показать фрагмент кода

Arnauld
источник
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)().
Лохматый
@ Shaggy Спасибо! Добавлено как альтернативная версия.
Arnauld
1

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).

Xanderhall
источник