Наименьшее неиспользуемое число с общим коэффициентом

11

Это довольно сложный вопрос. Я определю последовательность, и вы получите некоторый код для вывода записи с указанным индексом.

  • Первый элемент в последовательности - 2.

  • N-й элемент в последовательности - это наименьшее положительное целое число, отличное от n и 1, разделяющее по крайней мере один фактор с n (кроме 1), который еще не появился в списке.

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

Вот первые 25 пунктов в последовательности:

1  2
2  4
3  6
4  8
5  10
6  3
7  14
8  12
9  15
10 5
11 22
12 9
13 26
14 7
15 18
16 20
17 34
18 16
19 38
20 24
21 27
22 11
23 46
24 21
25 30

Связанные (смещение на единицу) OEIS

code-golf number sequence permutations Специальный охотник за гарфами
источник

Ответы:

3

Python 3 , 118 117 байт

-1 байт благодаря Кэмерон Аавик !

import math
def f(n,i=3):
 if n<2:return 2
 while 1:
  if math.gcd(n,i)>1>(i in map(f,range(n)))<i!=n:return i
  i+=1

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

Код довольно неэффективен (он перебирает значение, которого нет в предыдущих результатах, и снова вычисляет предыдущие результаты при каждом новом значении), поэтому он работает должным образом, но я бы не рекомендовал запускать его для больших чисел.

notjagan
источник
2
Небольшой совет: вы можете сохранить новую строку, сделав ее def f(n,i=3):и удалив i=3строку
Кэмерон Аавик
115 байтов .
Джонатан Фрех
2

Haskell , 60 59 байт

РЕДАКТИРОВАТЬ:

  • -1 байт: @xnor указал all(/=x)короче чем x`notElem`.

f принимает целое число и возвращает целое число

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:map f[1..n-1]]!!0

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

Это очень экспоненциальное время, поэтому время TIO истекло после 21, в то время как мой интерпретированный GHCi поднялся до 22, прежде чем я остановил его только сейчас. Следующие 9 байт более длинной версии, запоминающиеся в списке, легко вырастают до тысяч:

f n=[x|x<-[2..],gcd x n>1||n<2,all(/=x)$n:take(n-1)l]!!0
l=f<$>[1..]

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

  • f nиспользует составление списка для генерации кандидатов x, взяв первый проходящий с !!0.
  • gcd x n>1проверяет это xи nимеет общие факторы.
  • ||n<2освобождает n==1от требования фактора.
  • all(/=x)$n:map f[1..n-1]проверяет, что не xявляется ни nпредшествующим элементом последовательности.
Орджан Йохансен
источник
@WheatWizard Хм, наверное, нет разницы в этом случае. Просто привык делать это по умолчанию. Это одна из немногих буквенно-числовых функций, которая имеет фиксированность, определенную таким образом.
Орджан Йохансен
1
all(/=x)$там 1 короче
xnor
2

Нет встроенного для GCD в C #, так что ...

C # (.NET Core) , 197 196 194 байта

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

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

Еще раз, воздержитесь от использования этого кода для вычисления чисел в последовательности для n>30...

  • -1 байт, изменяя whileцикл GCD для forцикла.
  • -2 байта благодаря Кевину Круйссену! Хороший!
Чарли
источник
1
a>0&b>0можно сыграть в гольфa*b>0
Кевин Круйссен