Définissons une séquence. Nous dirons que $a(n)$ est le plus petit nombre, $x$ , qui a les propriétés suivantes:

• $x$ et$n$ sont co-premiers (ils ne partagent aucun facteur)

• $x$ n'apparaît pas plus tôt dans la séquence

• $|n - x| > 1$

Contrairement à la plupart des séquences, le domaine et la plage de notre séquence sont des entiers supérieurs à 1.

Calculons les deux premiers termes.

$a(2)$ , doit être au moins4, mais4et2partagent un facteur de2,donc$a(2)$ doit être5.

$a(3)$ , doit être au moins5mais5est pris par$a(2)$ , donc c'est au moins6, mais6partage un facteur avec3donc il doit être au moins7,7remplit les trois conditions donc$a(3)=7$ .

$a(4)$

• 2 partage un facteur
• 3 Trop près
• 4 Trop près
• 5 Trop près
• 6 partage un facteur
• 7 Pris par un (3)
• 8 partage un facteur
• 9 est bon

$a(5)$

• 2 est bon

Tâche

Dans ce défi, vous devez écrire un programme qui prend un nombre supérieur à 1 et renvoie $a(n)$ .

Il s'agit d'une question de code-golf, donc les réponses seront notées en octets, avec moins d'octets étant mieux.

Cas de test

Voici les deux premiers termes de la séquence (ils sont bien sûr indexés 2):

5,7,9,2,11,3,13,4,17,6,19,8,23,22,21,10,25,12,27,16,15,14

Bonus Fun Fact

Comme l'a prouvé Robert Israel sur Math.se ( lien ), cette séquence est son propre inverse, ce qui signifie que $a(a(n)) = n$ pour tout n.

OEIS

Après avoir posé cette question, j'ai soumis cette séquence à l'OEIS et après quelques jours, elle a été ajoutée.

OEIS A290151

Haskell , 61 octets

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0

Essayez-le en ligne!

Je suis assez nouveau à Haskell, donc tous les conseils de golf sont appréciés.

Merci à Wheat Wizard pour 2 octets et nimi pour 4 octets

Explication:

f n=[i|i<-[2..],gcd i n<2,all((/=i).f)[2..n-1],abs(n-i)>1]!!0
f n=                                                          -- define a function f :: Int -> Int
    [i|i<-[2..],                                              -- out of positive integers greater than two
                gcd i n<2,                                    -- gcd of i and n is 1
                          all((/=i).f)[2..n-1],               -- i isn't already in the sequence
                                               abs(n-i)>1]    -- and |n-i| > 1
                                                          !!0 -- take the first element

Alice , 42 octets

/oi
\1@/2-&whq&[]w].q-H.t*n$K.qG?*h$KW.!kq

Essayez-le en ligne!

Explication

/oi
\1@/.........

Il s'agit d'un modèle standard pour les programmes qui prennent un nombre en entrée et en sortent un nombre, modifié pour placer un 1 sur la pile sous le numéro d'entrée.

La partie principale du programme place chaque numéro kdans la fente a(k)sur la bande. La boucle interne calcule a (k) et la boucle externe itère sur k jusqu'à ce que a (n) soit calculé.

1       push 1
i       take input
2-&w    repeat n-1 times (push return address n-2 times)
h       increment current value of k
q&[     return tape to position 0
]       move right to position 1
w       push return address to start inner loop
]       move to next tape position
.q-     subtract tape position from k
H       absolute value
.t*     multiply by this amount minus 1
n$K     if zero (i.e., |k-x| = 0 or 1), return to start of inner loop
.qG     GCD(k, x)
?       current value of tape at position: -1 if x is available, or something positive otherwise
*       multiply
h$K     if not -1, return to start of inner loop
W       pop return address without jumping (end inner loop)
.!      store k at position a(k)
k       end outer loop
q       get tape position, which is a(n)
o       output
@       terminate

VB.NET (.NET 4.5), 222 octets

Function A(n)
Dim s=New List(Of Long)
For i=2To n
Dim c=2
While Math.Abs(i-c)<2Or g(c,i)>1Or s.Contains(c)
c+=1
End While
s.Add(c)
Next
Return s.Last
End Function
Function g(a, b)
Return If(b=0,a,g(b,a Mod b))
End Function

J'ai dû lancer votre propre GCD. Je ne pouvais pas non plus comprendre comment faire en sorte que ce ne soit pas une fonction entière.

GCD est toujours> = 1, il suffit donc d'ignorer 1

Supprimé les courts-circuits dans le golf parce qu'il est plus court

Non golfé

Function Answer(n As Integer) As Integer
    Dim seqeunce As New List(Of Integer)
    For i As Integer = 2 To n
        Dim counter As Integer = 2
        ' took out short-circuiting in the golf because it's shorter
        ' GCD is always >= 1, so only need to ignore 1
        While Math.Abs(i - counter) < 2 OrElse GCD(counter, i) > 1 OrElse seqeunce.Contains(counter)
            counter += 1
        End While
        seqeunce.Add(counter)
    Next
    Return seqeunce.Last
End Function

' roll your own GCD
Function GCD(a, b)
    Return If(b = 0, a, GCD(b, a Mod b))
End Function

Mathematica, 111 octets

(s={};Table[m=2;While[m<3#,If[CoprimeQ[i,m]&&FreeQ[s,m]&&Abs[i-m]>1,s~AppendTo~m;m=3#];m++],{i,2,#}];s[[#-1]])&

Essayez-le en ligne! 2..23 (mode plage)

Essayez-le en ligne! ou 150 (valeurs distinctes)

Japt , 33 octets (non concurrentiel?) ^†

ò2 rÈc_aY >1«XøZ «Yk øZk}a+2}[] o

Essayez-le en ligne!

_{^† J'ai corrigé un bogue dans Japt Interpreter en travaillant sur cette solution. Ce meta post d'il y a un an considère que cette réponse n'est pas concurrente, mais ce nouveau meta post pousse pour plus de liberté dans ce domaine. Quoi qu'il en soit, j'ai passé trop de temps là-dessus pour le supprimer.}

05AB1E , 26 octets

2IŸεDU°2Ÿ¯KʒX¿}ʒXα1›}θDˆ}θ

$n$°T*$10*n$$10^n$

Explication:

2IŸ               # Create a list in the range [2, input]
   ε              # Map each value `y` to:
    DU            #  Store a copy of `y` in variable `X`
    °2Ÿ           #  Create a list in the range [10**`y`,2]
       ¯K         #  Remove all values already in the global_array
       ʒX¿}       #  Only keep values with a greatest common divider of 1 with `X`
       ʒXα1›}     #  Only keep values with an absolute difference larger than 1 with `X`
             θ    #  After these filters: keep the last (the smallest) element
              Dˆ  #  And add a copy of it to the global_array
   }θ             # After the map: only leave the last value
                  # (and output the result implicitly)