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 ista(n-1)
unda(n-2)
und hat für integer noch nicht erschienen,n >= 3
.
Aufgabe
- Bei positiver Ganzzahl
n
Ausgabe / Drucka(n)
.
Beispiel
a(11) = 6
weil6
ist Koprime mit den letzten beiden Vorgängern (nämlich11
und13
) und6
ist 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 und1
eine kleine Zahl sind, sollte Ihr Code in Bezug auf die Anzahl der Bytes so klein wie möglich sein.
Verweise
- OEIS A084937
code-golf
sequence
number-theory
Undichte Nonne
quelle
quelle
Antworten:
Python 3.5,
160141126124121109 BytesDies 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.
Ungolfing:
quelle
import math
danng=math.gcd
sollte kürzer sein als die eigenen definiereng
. Für vor 3.5 können Siefrom fractions import*
für tungcd
.c=3
innerhalb der Schleife initialisieren , müssen Sie dies nur einmal tun. Nach meiner Zählung sparen Sie 3 Zeichen.r=[c]+r
anstatt+=
, 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,print
weil es kein vollständiges Programm mehr ist.MATL ,
2827 BytesDer 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:
Sehen Sie es als ASCII- Grafik oder mit grafischer Ausgabe im Offline-Compiler:
Erläuterung
quelle
C 185 Bytes
quelle
Eigentlich ,
383735333130 BytesDies ist eine einfache Implementierung der Funktionsdefinition. Golfvorschläge willkommen. Probieren Sie es online aus!
Bearbeiten: -3 Bytes dank Leaky Nun.
Ungolfing:
quelle
Haskell,
8173 BytesAnwendungsbeispiel:
((0:1:c[2,1])!!) 12
->17
.Erstellen Sie die Liste aller
a(n)
, beginnend mit0
dem Fixieren des 1-basierten Index1
und gefolgt vonc[2,1]
.c
nimmt den Kopf der Argumentliste,l
gefolgt von einem rekursiven Aufruf mit der nächsten passenden Nummer (Co-Prime, vorher nicht gesehen), die vor hinzugefügt wirdl
. Wählen Sie dasn
dritte Element dieser Liste aus.quelle
R 141 Bytes
ungolfed
quelle
Mathematica,
9790 BytesBasierend auf
meiner Vermutung, dassa(n) < 2n
für allen
.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)=1
danngcd(ab,m) = gcd(a,m)*gcd(b,m)
)quelle
ABS(a(n)-n) < n
"n
.Pyth, 23 Bytes
Testsuite
Eine ziemlich einfache Implementierung, aber mit einigen schönen Golf-Tricks.
quelle