Codegolf — Новый Порядок №1: Каково Это?

Введение

Расставлять все положительные числа в обычном порядке (1, 2, 3, ...) немного скучно, не правда ли? Итак, вот серия задач, связанных с перестановками (перестановками) всех положительных чисел.

Первая задача в этой серии — вывести a(n) для заданного n в качестве входных данных, где a(n) — это А064413, также известную как последовательность ЭКГ, поскольку график ее значений напоминает электрокардиограмму (отсюда и "Как это чувствуется" ссылка). Интересные свойства этой последовательности заключаются в том, что все положительные целые числа встречаются ровно один раз. Еще одна примечательная особенность заключается в том, что все простые числа встречаются в порядке возрастания.

Задача

Учитывая целое число на входе n, выведите a(n).

\$a(n)\$ определяется как:

• \$а(1) = 1; а(2) = 2;\$
• для \$n > 2\$ \$a(n)\$ — это наименьшее еще не использованное число, имеющее общий множитель с \$a(n-1)\$

Примечание. Здесь предполагается индексация на основе 1; вы можете использовать индексацию с отсчетом от 0, поэтому \$a(0) = 1; a(1) = 2\$ и т. д. Если вы решите использовать это, укажите это в своем ответе.

Тестовые случаи

 Input | Output
--------------
1     | 1
5     | 3
20    | 11
50    | 49
123   | 132
1234  | 1296
3000  | 3122
9999  | 10374
 

Правила

• Ввод и вывод — целые числа (ваша программа должна как минимум поддерживать ввод и вывод в диапазоне от 1 до 32767).
• Недопустимые входные данные (числа с плавающей запятой, строки, отрицательные значения и т. д.) могут привести к непредсказуемому выводу, ошибкам или (не)определённому поведению.
• По умолчанию Правила ввода-вывода применять.
• Лазейки по умолчанию запрещены.
• Это так, поэтому выигрывают самые короткие ответы в байтах.

Последнее замечание

Видеть этот связанный вопрос PP&CG.

#код-гольф #код-гольф #номер #последовательность

Хаскелл, 66 65 64 байта

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 2┅				| push [1 2]

@				| push n

⟨			 ⟩ₓ	| do n times:

:				| dup

1⟪		      ⟫#	| and find the first 1 integer i where the following results in a truthy value:

Ė₌	     ?		| is i an Ėlement of the list? Also push an extra copy of the arguments
	 0			| if so, give falsy result, so try the next integer
	  ⟪	    ⟫		| else do the following:
	   ;)d			| get divisors of a(n-1)
	      ;d		| get divisors of i
		&1D		| set intersect and remove the first element (which is always 1)
				| this yields an empty set if no divisors are shared (falsy, so try next integer)
				| or a non-empty set (truthy, so returns i = a(n))
			+	| and concatenate to list (end loop).
			   E	| finally, Extract the nth element (n taken implicitly)
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Хаскелл, 60 байт

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

с нулевой индексацией; можно было бы сэкономить четыре байта, если бы серия начиналась с 2 (что-то вроде индекса (-1), но без определения значения -1). Создает бесконечный список, лениво поддерживая список неиспользуемых номеров.

Питон 2, 104 байта

При этом используется индексация, отсчитываемая от 0.

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

05AB1E, 25 байты

0-индексированный

Попробуйте онлайн или Выведите первые \$n\$ элементы.

Объяснение:

Рубин, 86 байт

Однако это работает вечно для входных данных всего 10.

Вот версия с мемоизацией размером 102 байта, которая работает за приемлемое время:

МАШИННЫЙ ЯЗЫК (X86, 32 бита) + библиотека языка C, функции malloc()/free(), байты 325

Над НОД и функцией...

Приведенный ниже ассемблерный код генерирует функции и тестовую программу:

результаты:

50 49 байт

(индекс 0) Благодаря этот ответ

для некоторых трюков.

APL(NARS), символов 119, байт 238

этот тест занимает 1 мин: 49 с здесь:Java (JDK)

, 161 155 152 151 байт a=->(n){n<3?n:1.step{|i|return i if a[n-1].gcd(i)!=1&&(0...n).map(&a).all?{|j|j!=i}}} tracking to leverage the existing 1ˆ2ˆ # Add both 1 and 2 to the global_array F # Loop the (implicit) input amount of times: ∞.Δ # Get the first 1-indexed value resulting in truthy for the following: ¯yå≠ # Where this value is not in the global_array yet * # AND: ¯θ ¿ # Where the greatest common divisor of the last item of the global_array y @2 # and the current value, is larger than or equal to 2 }ˆ # After a new value has been found: add it to the global_array }¯ # After the loop: push the global_array ¨θ # Then remove the last element, and then take the new last element # (which is output implicitly as result) !

Сэкономил байт переключением

, 27 байт

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

Индексация на основе 1. ((1:2#[3..])!!) n#l|x:_<-[y|y<-l,gcd y n>1]=n:x#filter(/=x)l .