Einführung
A229037 hat eine ziemlich interessante Handlung (zumindest für die ersten Begriffe):
Es gibt die Vermutung, dass es tatsächlich eine Art fraktale Eigenschaft haben könnte.
Wie ist diese Sequenz aufgebaut?
Definieren a(1) = 1, a(2) = 1
dann für jedes n>2
eine minimale positive ganze Zahl finden , a(n)
so dass für jede arithmetische 3 Begriff Sequenz n,n+k,n+2k
von Indizes, die entsprechenden Werte der Sequenz a(n),a(n+k),a(n+2k)
ist nicht eine arithmetische Sequenz.
Herausforderung
Geben Sie bei einer positiven Ganzzahl n
als Eingabe die ersten n
Terme a(1), ... , a(n)
dieser Sequenz aus. (Bei angemessener Formatierung. Mögliche führende / trainierende Zeichen / Zeichenfolgen sind irrelevant.)
Es gibt Schnipsel zum Erzeugen dieser Sequenz, aber ich denke, dass andere Ansätze für bestimmte Sprachen besser geeignet sind.
Bitte teilen Sie uns mit, wie Ihr Programm funktioniert. Wenn Sie auf einen besonders effizienten Algorithmus stoßen, sollten Sie dies ebenfalls erwähnen, da dadurch mehr Terme der Sequenz in kürzerer Zeit aufgezeichnet werden können.
Erste Testfälle:
1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13
Weitere Testfälle:
a(100) = 4
a(500) = 5
a(1000) = 55
a(5000) = 15
a(10000) = 585
Alle Bedingungen bis n=100000
sind hier verfügbar: https://oeis.org/A229037/b229037.txt
Danke @ MartinBüttner für die Hilfe und Ermutigung.
Antworten:
Python 2, 95 Bytes
Der Haupttrick besteht darin, die Zahlen zu generieren, die der neue Wert vermeiden muss. Behalten
l
wir die bisherige umgekehrte Reihenfolge bei und schauen wir uns an, welche Elemente mit dem Wert, den wir hinzufügen möchten, eine arithmetische Dreierfolge bilden könnten.Die anderen Zahlen sind die gepaarten Mitglieder
l
und jedes zweite Element vonl
, sozip(l,l[1::2])
. Wenn dieses Paar ist, passiert(b,c)
die arithmetische Folge(a,b,c)
füra=2*b-c
. Nach dem Generieren dera
zu vermeidenden Menge von 's nimmt der Code das Minimum des Komplements, druckt es aus und stellt es der Liste voran. (Tatsächlich wird die Berechnung mit Zahlen durchgeführt, die um 1 verringert und um 1 höher gedruckt wurden, damitrange(n)
sie als Universum von Kandidaten dienen können.)quelle
Mathematica, 95 Bytes
Mit Sicherheit nicht der golferischste Ansatz, aber im Vergleich zu den Algorithmen, die ich auf der OEIS-Seite ausprobiert habe, ist dies tatsächlich ziemlich effizient.
Im Gegensatz zur Überprüfung aller verbotenen Werte für jedes s (n), wenn wir dort ankommen, benutze ich einen siebbasierten Ansatz. Wenn wir einen neuen Wert s (n) finden , überprüfen wir sofort, welche Werte dies für m> n verbietet . Dann lösen wir einfach die s (n + 1), indem nach dem ersten Wert suchen, der nicht verboten war.
Dies kann durch Ändern der Bedingung
--i>0
auf noch effizienter gestaltet werden2n-#<=--i>0
. In diesem Fall vermeiden wir es, verbotene Werte auf zu überprüfen n zu größer als die Eingabe sind.Für eine etwas besser lesbare Version habe ich mit diesem Code begonnen, in dem die Ergebnisse
max
in einer Funktionf
gespeichert sind, und dann die obige einzeilige reine Funktion verwendet:quelle
Haskell,
90,89,84, 83 BytesKann wahrscheinlich mehr golfen werden, aber dies ist immer noch ein anständiger
ersterVersuch:Ungolfed:
Dies ist eine einfache Implementierung, die '0' für außerhalb der Grenzen zurückgibt. Dann wird für jeden möglichen Wert geprüft, ob für alle k <= n und in Grenzen [x, a (xk), a (x-2k)] keine arithmetische Folge ist.
Obergrenze für Zeitkomplexität (unter Verwendung der Tatsache von der OEIS-Seite, dass a (n) <= (n + 1) / 2:
Ich bin nicht sicher, wie gut diese Schranke ist, weil die Berechnung der ersten 1k-Werte von 't' und die Verwendung eines linearen Modells in den Protokollen der Werte appx ergab. O (22 ^ n), mit p-Wert <10 ^ (- 1291), falls es darauf ankommt.
Auf Implementierungsebene dauerte das Kompilieren mit '-O2' ~ 35 Minuten, um die ersten 20 Werte zu berechnen.
quelle
Brachylog ,
3331 BytesProbieren Sie es online!
Für den Fall, dass es darauf ankommt: Das 2-Byte-Golfen war dank einer von mir gewünschten Funktion möglich nach der Arbeit an dieser Herausforderung .
Erläuterung
Wir generieren die Sequenz iterativ als Liste in umgekehrter Reihenfolge, z
[2,2,1,1,2,1,1]
und kehren sie am Ende um.Hier gibt es ein paar verschachtelte Prädikate. Schauen wir sie uns von innen nach außen an. Die erste
ġh₃hᵐs₂ᶠ-ᵐ=
nimmt eine Kandidatensubsequenza(n),a(n-1),...,a(0)
und bestimmt, oba(n),a(n-k),a(n-2k)
es sich bei einigen um eine arithmetische Sequenz handeltk
.Zum Beispiel mit Eingabe von
[1,2,1,1,2,1,1]
:Das nächste Prädikat nach außen gibt
~b.hℕ₁≜∧.¬{...}∧
eine Teilfolge eina(n-1),a(n-2),...,a(0)
und gibt die nächstgrößere Teilfolge ausa(n),a(n-1),a(n-2),...,a(0)
.Schließlich nimmt das Hauptprädikat
;Ė{...}ⁱ⁽↔
eine Eingabenummer und gibt so viele Terme der Sequenz aus.quelle
Ruby , 71 Bytes
Probieren Sie es online!
Erzeugt alle verbotenen Werte, nimmt dann das Komplement dieses Arrays in (1..n) und nimmt den ersten Wert des Ergebnisses. Das heißt, ich gehe davon aus, dass
a[n] <= n
für alle n, was durch Induktion leicht bewiesen werden kann (wenn die ersten n / 2 Terme alle kleiner als n / 2 sind, kann es keine arithmetische Progression geben, die zu n führt).Der syntaktische Trick ist auch hier ein wenig interessant: Er
*a
wird verwendet, um ein Array zusätzlicher Argumente zu initialisieren (die ignoriert würden, wenn wir eines übergeben würden), und danna.fill
das Argumentarray zu mutieren und implizit zurückzugeben.quelle
a[s-o]
unda[s-2*o]
können Sie vora[s-=1]
a[s-o]
APL (Dyalog Extended) , 37 Byte SBCS
Vielen Dank an Adám für seine Hilfe beim Schreiben und Golfen dieser Antwort in The APL Orchard , einem großartigen Ort, um die APL-Sprache zu lernen. Probieren Sie es online!
Edit: -6 Bytes dank Adám
Erläuterung
APL (Dyalog Unicode) ,
433938 Byte SBCSHier ist eine schnellere, aber weniger golferische Lösung, die
⍺(10000)
in wenigen Sekunden berechnet werden kann .Probieren Sie es online!
quelle
MATLAB,
156147 BytesIch habe es endlich geschafft, ein bisschen zu golfen:
Ungolfed:
Die Eingabe wird aus STDIN gelesen und der Ausdruck erfolgt automatisch mit
ans=
angehängten Daten . Ich hoffe das qualifiziert sich als "vernünftige" Ausgabe.Dies ist auch eine siebbasierte Lösung: die Variable
s(i,:)
verfolgt die Sequenzwerte, die für verboten sinda(i)
. Dertry-catch
Block wird benötigt, um den Fall einer leeren (dh vollen Null)s
Matrix zu behandeln. In diesem Fall ist der niedrigste Wert von1
bereits zulässig.Jedoch wird der Speicherbedarf (oder die Laufzeit?) Oben ziemlich unordentlich
N=2000
. Hier ist eine nicht konkurrierende, effizientere Lösung:In dieser Implementierung wird die
s
enthält Matrix wiederum verbotene Werte, jedoch auf eine geordnete Weise, ohne Nullblöcke (die in der Konkurrenzversion vorhanden sind). Der Indexvektori
verfolgt die Anzahl der verbotenen Vektoren ins
. Auf den ersten Blick wären Zellen großartig, um den Überblick über die darin gespeicherten Informationen zu behaltens
, aber diese wären langsam, und wir könnten nicht einen Haufen von ihnen gleichzeitig indizieren.Eine unangenehme Eigenschaft von MATLAB ist, dass, während Sie sagen können
M(1,end+1)=3;
eine Matrix und automatisch erweitern können, mit der linearen Indizierung jedoch nicht dasselbe tun können. Es ist irgendwie sinnvoll (wie sollte MATLAB die resultierende Array-Größe kennen, in deren Rahmen es die linearen Indizes interpretieren sollte?), Aber es hat mich trotzdem überrascht. Dies ist der Grund für die überflüssige Zeiles(N,max(i(j))) = 0;
: Dies erweitert dies
Matrix für uns, wann immer dies erforderlich ist. Die Startgröße erratenN*0.07+20
ergibt sich übrigens aus einer linearen Anpassung an die ersten paar Elemente.Um die Laufzeit zu testen, habe ich auch eine leicht geänderte Version des Codes überprüft, in der ich die
s
Matrix mit der Größe initialisiert habeN/2
. Für die ersten1e5
Elemente scheint dies eine sehr großzügige Vermutung zu sein, daher habe ich dens
im vorherigen Absatz erwähnten Erweiterungsschritt entfernt . Zusammengenommen bedeutet dies, dass der Code schneller ist, bei sehr hohen Werten jedoch auch weniger robustN
(da ich nicht weiß, wie die Serie dort aussieht).Also hier sind ein paar Laufzeiten im Vergleich
Ich habe diese auf R2012b gemessen und dabei das Beste aus 5 Läufen in einer benannten Funktionsdefinition mit genommen
tic/toc
.N=100
:0.011342 s
0.015218 s
0.015076 s
N=500
:0.101647 s
0.085277 s
0.081606 s
N=1000
:0.641910 s
0.187911 s
0.183565 s
N=2000
:5.010327 s
0.452892 s
0.430547 s
N=5000
:2.021213 s
1.572958 s
N=10000
:6.248483 s
5.812838 s
Es scheint, dass die
v3
Version bedeutend, aber nicht überwältigend schneller ist. Ich weiß nicht, ob ein Element der Unsicherheit (für sehr großeN
) die geringfügige Erhöhung der Laufzeit wert ist.quelle
M=1;M(end+1)=2;
Funktioniert das bei mir einwandfrei?M=rand(2); M(end+1)=2
stattdessen :)Gelee ,
2419 BytesDies ist meine erste Gelee-Antwort seit einiger Zeit. Ich bin froh, zurück zu sein.
Dies ist ein Port meiner APL-Antwort, die selbst eine Anpassung vieler der hier verwendeten Algorithmen ist. Der Hauptunterschied besteht darin, dass dies 0-indiziert ist.
Edit: -5 Bytes dank Jonathan Allan.
Probieren Sie es online!
Erläuterung
quelle
ḟ
Genauso gut wie dasœ-
Speichern eines Bytes“”
mit1
einer Jelly Darstellung einer Liste von einem Vollprogramm ausgibt, spart man mehr.Œœị@2
kann zumḊm2
sparen von zwei golfen werden .L‘R
kann man zumŻJ
sparen golfen .ES6, 114 Bytes
Gibt ein Array der ersten n Elemente der Sequenz zurück, sodass die Indizes 1 von der ungolfed-Version unten abweichen. Ich habe den Siebansatz verwendet. Diese Version verlangsamt sich nach etwa n = 2000; Eine frühere Version vermied es, den Anfang des Arrays abzulesen, was bedeutete, dass es nicht langsamer wurde, bis etwa n = 2500. In einer älteren Version wurde das Sieb-Array als Liste verbotener Werte verwendet und nicht als boolesches Array, dessen Werte verboten waren. dies könnte zu ungefähr n = 5000 kommen, ohne Schweiß zu brechen. Meine ursprüngliche Version versuchte, Bitmasken zu verwenden, aber das erwies sich als nicht hilfreich (und war mit 198 Bytes auch viel zu lang).
Die nicht ganz so langsame Version ungolfed:
quelle
Ich denke, ein Teil davon ist ein Fraktal und es kann bewiesen werden. Ich überprüfe immer noch meinen Beweis. Das heißt, ich habe es nicht bewiesen.
quelle