Kleinste positive ganze Zahl, die den letzten beiden Vorgängern entspricht und noch nicht erschienen ist; a (1) = 1, a (2) = 2

10

Definition

  • Zwei ganze Zahlen sind Koprime, wenn sie keine anderen positiven gemeinsamen Teiler als haben 1.
  • a(1) = 1
  • a(2) = 2
  • a(n)positive ganze Zahl ist die kleinste , die coprime zu der ist a(n-1)und a(n-2)und hat für integer noch nicht erschienen, n >= 3.

Aufgabe

  • Bei positiver Ganzzahl nAusgabe / Druck a(n).

Beispiel

  • a(11) = 6weil 6ist Koprime mit den letzten beiden Vorgängern (nämlich 11und 13) und 6ist noch nicht erschienen.

Anmerkungen

  • Beachten Sie, dass die Sequenz nicht aufsteigend ist, was bedeutet, dass ein Element kleiner als sein Vorgänger sein kann.

Technische Daten

  • Sie müssen 1-indiziert verwenden.

Testfälle

n      a(n)
1      1
2      2
3      3
4      5
5      4
6      7
7      9
8      8
9      11
10     13
11     6
12     17
13     19
14     10
15     21
16     23
17     16
18     15
19     29
20     14
100    139
1000   1355
10000  13387
100000 133361

Wertung

  • Da Coprime bedeutet, dass die beiden Zahlen nur einen Divisor ( 1) gemeinsam haben und 1eine kleine Zahl sind, sollte Ihr Code in Bezug auf die Anzahl der Bytes so klein wie möglich sein.

Verweise

Undichte Nonne
quelle
4
Diese "Gründe" für den Funktionscode ...
Luis Mendo
1
Ich frage mich, warum dies abgelehnt wurde. Sicher nicht wegen der schrecklichen Gründe?
Conor O'Brien
@ Conor Nicht ich. Eigentlich habe ich gestimmt. Ich hoffe, die Leute werden sowohl die Begründung als auch meinen Kommentar als Witze sehen
Luis Mendo
3
Das Problem mit diesen "lustigen" Begründungen für Code-Golf ist, dass ich einen schlechten Witz lesen muss, der sich über vier Zeilen erstreckt, um herauszufinden, dass dies Standard-Code-Golf ist. Es verschleiert einfach die Regeln der Herausforderung ohne guten Grund.
Martin Ender
1
@ ConorO'Brien Nicht alle Browser zeigen immer den Titel an (und dann gibt es die mobile App), und wir beschreiben im Allgemeinen die Bewertung im Beitrag zusätzlich zur Verwendung des Tags, da das Tag allein für neue Leute nichts bedeutet zum Ort. Obwohl ich mit unseren Tags für Herausforderungstypen vertraut bin , habe ich sie nie gelesen, um herauszufinden, wie eine Herausforderung bewertet wird, aber ich versuche, dies im Herausforderungskörper zu finden. Das Tag dient zur Kategorisierung, Durchsuchbarkeit und zu spezifischen Herausforderungen im Tag-Wiki.
Martin Ender

Antworten:

5

Python 3.5, 160 141 126 124 121 109 Bytes

Dies ist eine einfache Implementierung der Sequenzdefinition. Golfvorschläge willkommen.

Bearbeiten: -17 Bytes dank Leaky Nun. -9 Bytes dank Peter Taylor. -6 Bytes dank Sp3000 und Umstellung auf Python 3.5.

import math;f=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+math.gcd(c,r[0]*r[1])<2and f(n-1,[c]+r)or f(n,r,c+1)

Ungolfing:

import math
def f(n, r=[2,1], c=3):
    if n<2:
        return r[1]
    elif (c in r) + math.gcd(c,r[0]*r[1]) < 2:
        return f(n-1, [c]+r)
    else:
        return f(n, r, c+1)
Sherlock9
quelle
Für Python 3.5 oder höher, import mathdann g=math.gcdsollte kürzer sein als die eigenen definieren g. Für vor 3.5 können Sie from fractions import*für tun gcd.
Sp3000
Wenn Sie c=3innerhalb der Schleife initialisieren , müssen Sie dies nur einmal tun. Nach meiner Zählung sparen Sie 3 Zeichen.
Peter Taylor
Es gibt auch eine 2-char Einsparung von dem Aufbau der Anordnung umgekehrt: Sie haben zu verwenden , r=[c]+ranstatt +=, aber drei negative Indizes werden positiv. Und dann gibt es noch eine weitere 2-Zeichen-Ersparnis beim Umschreiben als Lambda, obwohl dies eine ziemlich drastische Änderung ist: from fractions import*;F=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+gcd(r[0]*r[1],c)<2and F(n-1,[c]+r)or F(n,r,c+1)und keine Notwendigkeit für ein, printweil es kein vollständiges Programm mehr ist.
Peter Taylor
2

MATL , 28 27 Bytes

2:i:"`@ym1MTF_)Zdqa+}@h]]G)

Der Code ist langsam, liefert aber das richtige Ergebnis.

Probieren Sie es online aus! Oder überprüfen Sie die ersten zehn Fälle .

Eine kleine Änderung des Codes erzeugt eine Darstellung der Sequenz:

2:i:"`@ym1MTF_)Zdqa+}@h]]G:)XG

Sehen Sie es als ASCII- Grafik oder mit grafischer Ausgabe im Offline-Compiler:

Geben Sie hier die Bildbeschreibung ein

Geben Sie hier die Bildbeschreibung ein

Erläuterung

2:         % Push [1 2] to initiallize the sequence
i:         % Input n. Push [1 2 ... n]
"          % For loop: repeat n times
  `        %   Do while loop
    @      %     Push iteration index, starting at 1. This is the candidate number
           %     to extend the sequence
    y      %     Duplicate vector containing the sequence so far
    m      %     Is member? Gives true if the candidate is in the sequence
    1M     %     Push candidate and vector again
    TF_)   %     Get last two elements of the vector
    Zd     %     GCD between the candidate and those two elements. Produces a
           %     two-element vector
    qa     %     True if any of the two results exceeds 1, meaning
           %     the candidate is not coprime with the latest two sequence values
    +      %     Add. This corresponds to logical "or" of the two conditions, namely
           %     whether the candidate is member of the sequence so far, and
           %     whether it is not coprime with the latest two. In either case
           %     the do...while must continue with a next iteration, to try a new
           %     candidate. Else the loop is exited, and the current candidate
           %     is the new value of the sequence
  }        %   Finally (execute when the loop is exited)
    @h     %     Push current candidate and concatenate to the sequence vector
  ]        %   End do...while
]          % End for
G)         % Get n-th value of the sequence. Implicitly display
Luis Mendo
quelle
1

C 185 Bytes

G(a,b){return a%b?G(b,a%b):b;}
i,j,k;f(n){int a[n+2];for(i=0;i++<n;){a[i]=i<3?i:0;for(j=2;!a[i];++j){for(k=i;--k;){if(a[k]==j)++j,k=i;}a[G(a[i-1],j)*G(a[i-2],j)<2?i:0]=j;}}return a[n];}
orlp
quelle
1

Eigentlich , 38 37 35 33 31 30 Bytes

Dies ist eine einfache Implementierung der Funktionsdefinition. Golfvorschläge willkommen. Probieren Sie es online aus!

Bearbeiten: -3 Bytes dank Leaky Nun.

2R#╗,;`1";2±╜tπg@╜í+Y"£╓╖`nD╜E

Ungolfing:

2R#╗    Push [1,2] and store it in register 0
,;      Take input and duplicate
`1      Start function, push 1
  "       Start string
  ;       Duplicate i
  2±╜t    Push (list in register 0)[-2:]
  πg      gcd(i, product of list[-2:])
  @╜í     Rotate the gcd and bring up i, check for i in list (0-based, -1 if not found)
  +Y      Add the gcd and the index, negate (1 if coprime and not found in list, else 0)
  "£      End string, turn into a function
╓       Push first (1) values where f(x) is truthy, starting with f(0)
╖`      Append result to the list in register 0, end function
n       Run function (input) times
D╜E     Return (final list)[n-1]
Sherlock9
quelle
1
Stapelmanipulation viel
Leaky Nun
0

Haskell, 81 73 Bytes

c l@(m:n:_)=m:c([x|x<-[1..],gcd(m*n)x<2,all(/=x)l]!!0:l)
((0:1:c[2,1])!!)

Anwendungsbeispiel: ((0:1:c[2,1])!!) 12-> 17.

Erstellen Sie die Liste aller a(n), beginnend mit 0dem Fixieren des 1-basierten Index 1und gefolgt von c[2,1]. cnimmt den Kopf der Argumentliste, lgefolgt von einem rekursiven Aufruf mit der nächsten passenden Nummer (Co-Prime, vorher nicht gesehen), die vor hinzugefügt wird l. Wählen Sie das ndritte Element dieser Liste aus.

Nimi
quelle
0

R 141 Bytes

 f=Vectorize(function(n)ifelse(n>3,{c=3;a=f(n-1);b=f(n-2);d=f(4:n-3);while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)c=c+1;c},n))

ungolfed

f=Vectorize( function(n)     #build a recursive function. Vectorize allows
    if(n>3) {                #the function to be called on vectors.
        c=3                  #Tests size. Builds some frequent variables.
        a=f(n-1)
        b=f(n-2)
        d=f(4:n-3)           #Should really golf this out, but its horribly slow.
        while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)
              c=c+1          #If we are coprime and not already seen. add.
        c
     } else n)               #First three are 1,2,3.
user5957401
quelle
0

Mathematica, 97 90 Bytes

a@1=1;a@2=2;a@n_:=SelectFirst[Range[2n],GCD[a[n-1]a[n-2],#]<2&&!MemberQ[a/@Range[n-1],#]&]

Basierend auf meiner Vermutung, dass a(n) < 2n für alle n.

Fügen Sie a@n=nach dem Original hinzu :=, um eine schnellere Ausführung zu erzielen, damit die Funktion keine vorherigen Werte neu berechnen muss .

7 Bytes dank Sherlock9 gespeichert (wenn gcd(a,b)=1dann gcd(ab,m) = gcd(a,m)*gcd(b,m))

für Monica
quelle
Es ist keine Vermutung, da auf der OEIS-Seite geschrieben steht, dass " ABS(a(n)-n) < n"
Leaky Nun
@LeakyNun Danke. Die OEIS-Seite war bis vor wenigen Augenblicken ausgefallen, und ich war besorgt über ein mögliches Gegenbeispiel für große n.
für Monica
0

Pyth, 23 Bytes

eu+Gf&-TGq1iT*F>2G1tQ]1

Testsuite

Eine ziemlich einfache Implementierung, aber mit einigen schönen Golf-Tricks.

eu+Gf&-TGq1iT*F>2G1tQ]1
 u                 tQ]1    Apply the following function input - 1 times,
                           where G is the current state (List of values so far)
  +G                       Add to G
    f             1        The first number, counting up from 1
      -TG                  That has not been seen so far
     &                     And where
               >2G         The most recent two numbers
             *F            Multiplied together
           iT              Gcd with the current number being checked
         q1                Equals 1
e                          Output the final element of the list.
isaacg
quelle