El número no utilizado más pequeño que comparte un factor

11

Esta es una pregunta bastante común. Definiré una secuencia y usted jugará un código para generar una entrada dado un índice.

  • El primer elemento de la secuencia es 2.

  • El enésimo elemento de la secuencia es el entero positivo más pequeño que no sea n y 1 que comparte al menos un factor con n (que no sea 1) que aún no ha aparecido en la lista.

Casos de prueba

Aquí están los primeros 25 elementos de la secuencia:

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 relacionados (compensados ​​por uno)

code-golf number sequence permutations Ad Hoc Garf Hunter
fuente

Respuestas:

3

Python 3 , 118117 bytes

-1 byte gracias a Cameron Aavik !

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

Pruébalo en línea!

El código es bastante ineficiente (fuerza bruta un valor que no existe en los resultados anteriores y calcula los resultados anteriores nuevamente en cada valor nuevo), por lo que funciona correctamente, pero no recomendaría ejecutarlo en grandes cantidades.

notjagan
fuente
2
Pequeño consejo: puede guardar una nueva línea haciéndola def f(n,i=3):y quitando la i=3línea
Cameron Aavik
115 bytes .
Jonathan Frech
2

Haskell , 60 59 bytes

EDITAR:

  • -1 byte: @xnor señaló que all(/=x)era más corto que x`notElem`.

f toma un entero y devuelve un entero.

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

Pruébalo en línea!

Este es un tiempo muy exponencial, por lo que TIO agota el tiempo de espera después de 21, mientras que mi GHCi interpretado llegó a 22 antes de detenerlo en este momento. La siguiente versión de 9 bytes más larga que se memoriza en una lista sube fácilmente a miles:

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

Pruébalo en línea!

  • f nutiliza una lista de comprensión para generar candidatos x, tomando el primer paso con !!0.
  • gcd x n>1comprueba eso xy ntiene factores comunes.
  • ||n<2exento n==1del requisito de factor.
  • all(/=x)$n:map f[1..n-1]comprueba que xno es nni un elemento de secuencia precedente.
Ørjan Johansen
fuente
@WheatWizard Hm, probablemente no haya diferencia en ese caso. Solo estoy acostumbrado a hacerlo por defecto. Es una de las pocas funciones alfanuméricas que tiene una fijación definida para ajustarse bien de esa manera.
Ørjan Johansen
1
all(/=x)$es 1 más corto allí
xnor
2

No incorporado para GCD en C #, así que ...

C # (.NET Core) , 197 196 194 bytes

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;}}

Pruébalo en línea!

Una vez más, abstenerse de usar este código para calcular los números en la secuencia para n>30...

  • -1 byte cambiando el whilebucle GCD por un forbucle.
  • -2 bytes gracias a Kevin Cruijssen! ¡Buena esa!
Charlie
fuente
1
a>0&b>0se puede jugar al golfa*b>0
Kevin Cruijssen