Ihre Aufgabe ist es, die Ganzzahlfolge A130826 zu implementieren :
a n ist die kleinste positive ganze Zahl, so dass a n - n ein ganzes Vielfaches von 3 ist und die doppelte Anzahl von Teilern von (a n - n) / 3 den n- ten Term in den ersten Differenzen der vom Flavius erzeugten Sequenz ergibt Josephus Sieb.
Schon verloren? Nun, es ist eigentlich ganz einfach.
Das Flavius Josephus-Sieb definiert eine ganzzahlige Folge wie folgt.
Beginnen Sie mit der Folge positiver Ganzzahlen und setzen Sie k = 2 .
Entferne jede k- te ganze Zahl der Sequenz, beginnend mit der k- ten .
Inkrementiere k und gehe zurück zu Schritt 2.
f n ist die n- te Ganzzahl (1-indiziert), die niemals entfernt wird.
Wenn - wie üblich - σ 0 (k) die Anzahl der positiven Teiler der ganzen Zahl k bezeichnet , können wir ein n als die kleinste positive ganze Zahl definieren, so dass 2σ 0 ((a n - n) / 3) = f n + 1 ist - f n .
Herausforderung
Schreiben Sie ein Programm oder eine Funktion, die eine positive Ganzzahl n als Eingabe verwendet und eine n ausgibt oder zurückgibt .
Es gelten die Standardregeln für Code-Golf . Möge der kürzeste Code gewinnen!
Arbeitsbeispiele
Wenn wir jedes zweite Element der positiven ganzen Zahlen entfernen, bleibt uns nichts anderes übrig
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 ...
Nachdem wir jedes dritte Element des Restes entfernt haben, erhalten wir
1 3 7 9 13 15 19 21 25 27 31 33 37 39 ...
Wenn wir nun jedes vierte, dann fünfte und dann sechste Element entfernen, erhalten wir
1 3 7 13 15 19 25 27 31 37 39 ...
1 3 7 13 19 25 27 31 39 ...
1 3 7 13 19 27 31 39 ...
1 3 7 13 19 27 39 ...
Die letzte Zeile zeigt die Terme f 1 bis f 7 .
Die Unterschiede der aufeinanderfolgenden Elemente dieser Begriffe sind
2 4 6 6 8 12
Teilen Sie diese Vorwärtsdifferenzen durch 2 , erhalten wir
1 2 3 3 4 6
Dies sind die Zieldivisorenzahlen.
- 4 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 1) / 3) = 1 ist . Tatsächlich ist σ 0 (1) = 1 .
- 8 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 2) / 3) = 2 ist . In der Tat, & sgr; 0 (2) = 2 .
- 15 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 3) / 3) = 3 ist . In der Tat, & sgr; 0 (4) = 3 .
- 16 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 4) / 3) = 3 ist . In der Tat, & sgr; 0 (4) = 3 .
- 23 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 5) / 3) = 4 ist . In der Tat, & sgr; 0 (6) = 4 .
- 42 ist die erste ganze Zahl k, so dass & sgr; 0 ((k - 6) / 3) = 6 ist . In der Tat, & sgr; 0 (12) = 6 .
Testfälle
n a(n)
1 4
2 8
3 15
4 16
5 23
6 42
7 55
8 200
9 81
10 46
11 119
12 192
13 205
14 196622
15 12303
16 88
17 449
18 558
19 127
20 1748
21 786453
22 58
23 2183
24 3096
25 1105
26 786458
27 12582939
28 568
29 2189
30 2730
quelle
Antworten:
Jelly,
30292725 Bytes2 Bytes gespart dank @Dennis, der mich benachrichtigt hat
Æd
, und weitere 2 Bytes für das Kombinieren der beiden Ketten.Probieren Sie es online!
Das war wahrscheinlich der Spaß, den ich je mit Jelly hatte. Ich habe mit der zweiten Zeile begonnen, die f n aus n mit der Formel in OEIS berechnet, und sie ist ziemlich schön.
Erläuterung
quelle
Python 2 ,
121119118 BytesDie Laufzeit sollte ungefähr 0 (16 n ) bei 0 (4 n ) Speichernutzung betragen. Ersetzen
4**n
durch5<<n
- was ich für ausreichend halte - würde dies dramatisch verbessern, aber ich bin nicht davon überzeugt, dass es für beliebig große Werte von n funktioniert .Probieren Sie es online!
Asymptotisches Verhalten und Obergrenzen von a n
Definiere b n als (a n - n) / 3 , dh die kleinste positive ganze Zahl k, so dass σ 0 (k) = ½ (f n + 1 - f n ) .
Wie auf der OEIS-Seite angegeben, ist f n ~ ¼πn 2 , also f n + 1 - f n ~ ¼π (n + 1) 2 - ¼πn 2 = ¼π (2n + 1) ~ ½πn .
Auf diese Weise ½ (f n + 1 - f n ) ~ ¼πn . Wenn die tatsächliche Zahl eine Primzahl p ist , ist die kleinste positive ganze Zahl mit p- Teilern 2 p-1 , so dass b n durch 2 c n angenähert werden kann , wobei c n ~ ¼πn ist .
Daher gilt b n <4 n für ausreichend großes n , und da 2 ¼πn <2 n << (2 n ) 2 = 4 n ist , bin ich zuversichtlich, dass es keine Gegenbeispiele gibt.
Wie es funktioniert
Dies legt einige Referenzen für unseren iterativen Prozess fest.
n ist die Benutzereingabe: eine positive ganze Zahl.
r ist die Liste [1, ..., 4 n - 1] .
s ist eine Kopie von r .
Wenn Sie die Liste einmal mit wiederholen,
r*1
wird eine flache Kopie erstellt. Wenn Sie also s ändern, wird r nicht geändert .d wird als das Tupel initialisiert (n) .
Dieser erste Wert ist nicht wichtig. Alle anderen Werte enthalten Divisoren für positive ganze Zahlen.
Für jede ganze Zahl k von 1 bis 4 n - 1 machen wir folgendes.
del s[k::k+1]
Nimmt jede (k + 1) -te Ganzzahl in s - beginnend mit der (k + 1) -ten - und löscht diesen Slice aus s .Auf diese einfache Weise kann ein Anfangsintervall des Flavius-Josephus-Siebs in s gespeichert werden . Es wird viel mehr als die erforderlichen n + 1 anfänglichen Terme berechnet , aber die Verwendung einer einzelnen
for
Schleife zum Aktualisieren von s und d spart einige Bytes.d+=sum(k%j<1for j in r)*2,
zählt, wie viele Elemente von r k gleichmäßig teilen und fügt 2σ 0 (k) an d an .Da d als Singleton-Tupel initialisiert wurde, wird 2σ 0 (k) am Index k gespeichert .
Dies findet den ersten Index von f n + 1 - f n in d , der das kleinste k ist, so dass 2σ 0 (k) = f n + 1 - f n ist , berechnet dann ein n als 3k + 1 und gibt das Ergebnis aus.
quelle
Java 8,
336,305,303,287,283,279 Bytes57 Bytes dank Kritixi Lithos entfernt
Golf gespielt
Ungolfed
quelle
int
ist kürzer als das Verwendenjava.util.Scanner
. Aber auch wenn Sie Scanner verwenden, können SieSystem.out.print(h(new java.util.Scanner().nextInt()))
die vorherige Zeileint h()
können Sie es ändernint v = (g(k,k)-g(k,k-1))/2,u = 0,t = 1;
. Sie können Ihre if-Anweisung (die sich in Ihrer for-Schleife befindet) vonif(t%i==0)
aufif(t%i<1)
g
, dass sie mit ternären Operatoren wiereturn s==0?N+1:g(s-1,N+N/2)
-ishMathematica,
130116106103 Bytesoder
Am Ende war es fast identisch mit @ Pietu1998s Jelly-Code ...
Erläuterung
Catch
was auch immerThrow
geworfen wird.Endlosschleife;
k
geht von1
jeder Iteration aus und inkrementiert sie.Zuweisen
f
:Finden
{1, 2, ... , n}
. Dreh es um.Eine Funktion, die ceil (n1 / n2 + 1) * n2 ausgibt
Weisen Sie
f
eine Funktion zu, die die obige Funktion rekursiv aus zwei Schritten auf die Liste anwendet, wobei jeder Ausgang als erster Eingang und jedes Element der Liste als zweiter Eingang verwendet wird. Die anfängliche "Ausgabe" (erste Eingabe) ist das erste Element der Liste.Prüfen Sie, ob die doppelte Anzahl der Teiler von
k
gleich f (n + 1) - f (n) ist.Wenn die Bedingung lautet
True
, istThrow
der Wert vonk
. Wenn nicht, fahren Sie mit der Schleife fort.Multiplizieren Sie die Ausgabe mit 3 und addieren Sie n.
130-Byte-Version
quelle
Perl 6 ,
154149136107 BytesUngolfed:
quelle
05AB1E ,
353439 BytesEs sieht schrecklich aus, genauso wie die Laufzeitleistung. Es dauert einige Sekunden, bis Eingaben kleine Werte ergeben. Versuche keine Zahlen wie 14; es wird schließlich das Ergebnis finden, aber es würde ewig dauern.
Erläuterung
Es funktioniert als 2 nacheinander aufgerufene Programme. Der erste berechnet F n + 1 - F n und der zweite bestimmt ein n basierend auf seiner Definition unter Verwendung eines Bruteforce-Ansatzes.
F n + 1 - F n wird für jede Iteration ausgewertet, obwohl sie schleifeninvariant ist. Dadurch wird die Codezeit ineffizient, aber der Code wird kürzer.
Probieren Sie es online!
quelle
žHL
) generiert werden und dann die Werte herausgefiltert werden, die die Siebbedingungen nicht erfüllen. Ich denke, der erste Teil dieses Programms sollte mit einer völlig anderen Herangehensweise umgeschrieben werden, um es golffähig zu machen.given enough time and memory
, da ich bereits mehrere Antworten auf andere Fragen gesehen habe, die so langsam abliefen, dass es fast unmöglich war zu sagen, ob sie die richtige Ausgabe lieferten oder nicht. Aus diesem Grund habe ich die Siebberechnung von der Schleife genommen und es hat mich 2 Bytes gekostet.