Plus petit numéro inutilisé partageant un facteur

11

Il s'agit d'une question assez courante. Je définirai une séquence et vous jouerez du code pour sortir une entrée en fonction d'un index.

  • Le premier élément de la séquence est 2.

  • Le nième élément de la séquence est le plus petit entier positif autre que n et 1 partageant au moins un facteur avec n (autre que 1) qui n'est pas déjà apparu dans la liste.

Cas de test

Voici les 25 premiers éléments de la séquence:

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 apparenté (compensé par un)

code-golf number sequence permutations Ad Hoc Garf Hunter
la source

Réponses:

5

Gelée , 19 octets

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

Essayez-le en ligne!

Dennis
la source
J'étais si heureux que je vous avais hors golfed sur le mot Lyndon factorisation question , mais vous me frapper avec ce ... (dans tout le sérieux bien que ce soit une excellente réponse)
notjagan
3

Python 3 , 118 117 octets

-1 octet merci à 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

Essayez-le en ligne!

Le code est assez inefficace (il force brutalement une valeur qui n'existe pas dans les résultats précédents et calcule à nouveau les résultats précédents sur chaque nouvelle valeur), donc il fonctionne correctement mais je ne recommanderais pas de l'exécuter sur de grands nombres.

notjagan
la source
2
Petite astuce: Vous pouvez enregistrer une nouvelle ligne en rendant def f(n,i=3):et en enlevant la i=3ligne
Cameron Aavik
115 octets .
Jonathan Frech
2

Haskell , 60 59 octets

ÉDITER:

  • -1 octet: @xnor a indiqué qu'il all(/=x)était plus court que x`notElem`.

f prend un entier et retourne un entier.

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

Essayez-le en ligne!

Il s'agit d'un temps très exponentiel, donc TIO expire après 21, tandis que mon GHCi interprété a atteint 22 avant que je ne l'arrête tout à l'heure. La version suivante de 9 octets de plus à mémoriser dans une liste monte facilement par milliers:

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

Essayez-le en ligne!

  • f nutilise une compréhension de liste pour générer des candidats x, en prenant le premier qui passe avec !!0.
  • gcd x n>1vérifie cela xet na des facteurs communs.
  • ||n<2exempte n==1de l'exigence relative aux facteurs.
  • all(/=x)$n:map f[1..n-1]vérifie qui xn'est nni un élément de séquence précédent.
Ørjan Johansen
la source
@WheatWizard Hm, probablement aucune différence dans ce cas. Juste l'habitude de le faire par défaut. C'est l'une des rares fonctions alphanumériques à avoir une fixité définie pour bien s'adapter de cette façon.
Ørjan Johansen
1
all(/=x)$est 1 plus court
xnor
2

Pas intégré pour GCD en C #, donc ...

C # (.NET Core) , 197196194 octets

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

Essayez-le en ligne!

Encore une fois, évitez d'utiliser ce code pour calculer les nombres dans la séquence de n>30...

  • -1 octet en changeant la whileboucle GCD pour une forboucle.
  • -2 octets grâce à Kevin Cruijssen! Joli!
Charlie
la source
1
a>0&b>0peut être joué au a*b>0
golf