Menor número não utilizado compartilhando um fator

11

Esta é uma questão bastante comum. Definirei uma sequência e você cria um código para gerar uma entrada com um índice.

  • O primeiro item da sequência é 2.

  • O enésimo item da sequência é o menor número inteiro positivo que não seja n e 1 que compartilhe pelo menos um fator com n (que não seja 1) que ainda não apareceu na lista.

Casos de teste

Aqui estão os primeiros 25 itens na sequência:

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

Relacionado (compensado por um) OEIS

code-golf number sequence permutations Post Rock Garf Hunter
fonte

Respostas:

5

Geléia , 19 bytes

R»2ɓ²Rg⁸>1Tḟ⁸ḟḢṭµ/Ṫ

Experimente online!

Dennis
fonte
Eu estava tão feliz que eu tinha você out-golfed no Lyndon fatoração palavra pergunta, mas então você me bateu com isso ... (com toda a seriedade que esta é uma grande resposta)
notjagan
3

Python 3 , 118 117 bytes

-1 byte graças 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

Experimente online!

O código é bastante ineficiente (força bruta um valor que não existe nos resultados anteriores e calcula os resultados anteriores novamente em cada novo valor); portanto, funciona corretamente, mas eu não recomendaria executá-lo em grandes números.

notjagan
fonte
2
Pequena dica: Você pode salvar uma nova linha, tornando-a def f(n,i=3):e removendo a i=3linha
Cameron Aavik
115 bytes .
Jonathan Frech 25/09
2

Haskell , 60 59 bytes

EDITAR:

  • -1 byte: @xnor apontou que all(/=x)era menor que x`notElem`.

f pega um número inteiro e retorna um número inteiro.

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

Experimente online!

Este é um tempo muito exponencial, então o TIO expira após 21, enquanto meu GHCi interpretado chegou a 22 antes que eu parasse agora. A seguinte versão mais longa de 9 bytes, memorizando em uma lista, chega facilmente aos milhares:

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

Experimente online!

  • f nusa uma compreensão de lista para gerar candidatos x, levando o primeiro passo com !!0.
  • gcd x n>1verifica isso xe npossui fatores comuns.
  • ||n<2isenta n==1do requisito fatorial.
  • all(/=x)$n:map f[1..n-1]verifica que xnão é nnem um elemento de sequência anterior.
Ørjan Johansen
fonte
@WheatWizard Hm, provavelmente não há diferença nesse caso. Apenas acostumado a fazê-lo por padrão. É uma das poucas funções alfanuméricas que possui uma fixidez definida para se ajustar bem dessa maneira.
Ørjan Johansen
1
all(/=x)$é 1 mais curto lá
xnor
2

Sem built-in para GCD em C #, então ...

C # (.NET Core) , 197196194 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;}}

Experimente online!

Mais uma vez, evite usar esse código para calcular números na sequência de n>30...

  • -1 byte, alterando o whileloop GCD para um forloop.
  • -2 bytes graças a Kevin Cruijssen! Agradável!
Charlie
fonte
1
a>0&b>0pode ser a*b>0
jogado golfe