Rechte und tfeL abgeschnittene Primzahlen

11

Eine rechtsabschneidbare Primzahl ist eine Primzahl, bei der jedes Präfix eine Primzahl ist (in Basis 10). Eine linksabschneidbare Primzahl ist genau das Gegenteil, wobei jedes Postfix eine Primzahl ist (Primzahlen, die mit 0 beginnen, sind nicht zulässig). Beide Sequenzen sind endlich (es gibt nur 83 rechtsabschneidbare Elemente, während es 4260 linksabschneidbare Elemente gibt).

Sie müssen ein Programm schreiben, das eine einzelne Zahl als Eingabe akzeptiert und die n- te rechtskürzbare Primzahl erzeugt. Wenn das Programm jedoch rückwärts angeordnet gelesen wird , sollte es die n- te linksabschneidbare Primzahl erzeugen .

Um ein Programm rückwärts anzuordnen, teilen wir das Programm in Wörter auf und kehren dann die Reihenfolge der Wörter um. Ein Wort kann aus einer beliebigen Anzahl von Zeichen bestehen.

Zum Beispiel, wenn Folgendes Ihr Programm war:

hello world
1234567890

Folgendes wäre als mögliche Rückwärtsanordnungen zulässig:

Aufteilen auf jeden Charakter:

0987654321
dlrow olleh

Aufteilen auf Leerzeichen:

1234567890
world hello

Beliebige Aufteilung (zur Verdeutlichung Rohre hinzugefügt):

hel|lo w|orld
1|23456|7|8|90

908723456orld
1lo whel

Wenn Sie Ihr Programm rückwärts anordnen, müssen alle Leerzeichen wie bei jedem anderen Zeichen berücksichtigt und umgekehrt werden.

Vorwärts-Testeingaben:

1:  2
2:  3
21: 379
60: 239933
83: 73939133

Rückwärtstest-Eingaben:

1:    2
2:    3
39:   647
187:  29173
4260: 357686312646216567629137

Programme sollten in angemessener Zeit (weniger als eine Minute) ausgeführt werden können.

Dies ist ein , also gewinnt das Programm mit den wenigsten Bytes!

Nathan Merrill
quelle
Nein. Das Atom danach lo wist orld\n1. Die Newline beendet das Atom nicht
Nathan Merrill
Ah danke. Ich habe es verstanden. Entfernen meiner beiden vorherigen Kommentare, um Verwirrung zu vermeiden
Luis Mendo

Antworten:

6

Gelee , 26 23 Bytes

Nach vorne

Ѷp9¶7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Probieren Sie es online aus!

Wörter

Ñ p 9 7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Rückwärts

7ÆR2ĿV€$ÆPÐf$ÐĿFị@¶9p¶Ñ

Probieren Sie es online aus!

Wörter

7ÆR2ĿV€$ÆPÐf$ÐĿFị@ 9 p Ñ

Wie es funktioniert

Alle Jelly-Programme bestehen aus Links (Jellys übernehmen Funktionen), die durch Zeilenvorschübe oder Pilcrows ( ) getrennt sind. Der letzte von ihnen ist das Hauptglied ; Es wird automatisch aufgerufen, wenn das Programm ausgeführt wird.

Das Vorwärtsprogramm funktioniert wie folgt.

Ñ                   Helper link. Unused.


p9                  Helper link. Take the Cartesian product with [1, ..., 9].


7ÆR2ĿV€$ÆPÐf$ÐĿFị@  Main link. Argument: n

7ÆR                 Yield all primes up to 7.
             ÐĿ     
            $ÐĿ     Combine the two quicklinks to the left into a monadic chain,
                    and call it repeatedly until the results are no longer unique.
                    Return the array of all intermediate results.
       $              Combine the two links to the left into a monadic chain.
   2Ŀ               Call the helper link on line 2.
     Ṿ€                 Eval each array in the product. This casts to string
                        before evaluating, thus concatenating both numbers.
        ÆPÐf        Filter by primality; keep only primes.
               F    Flatten the resulting array.
                ị@  Retrieve the element at index n.

Das Rückwärtsprogramm macht fast genau das gleiche; Es gibt nur zwei Unterschiede.

  • Der Hauptlink ist jetzt Ñ, der einfach den Link darunter aufruft (umlaufen), dh der Hauptlink des Weiterleitungsprogramms.

  • 9panstatt p9das umgekehrte kartesische Produkt zurückzugeben.

Dennis
quelle
4

Python 2, 143 139 Bytes

I=1
a={2}
def f(s):
 for d in'123456789':u=d[I:]+s+d*I;z=int(u);z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
f('')
lambda n:sorted(a)[~-n]
I=0

Besteht aus fünf Teilen:

  1. I=1
  2. Eine neue Zeile
  3. a={2}…[~-n]
  4. Eine neue Zeile
  5. I=0

Die Umkehrung dreht also nur den Wert von um I.

Erläuterung

Die Funktion fführt eine rekursive Suche nach LTPs (Left Truncatable Primes) oder RTPs (Right Truncatable Primes) durch, abhängig vom Wert des Global I. Diese Werte werden dem Satz hinzugefügt a. Dann wird lambda n:sorted(a)[~-n]der n-te zurückgegeben.

Definieren wir ein Blatt entweder als LTP, als RTP, als Ziffer ungleich Null + als LTP oder als RTP + als Ziffer ungleich Null. Dies sind alle Werte, fdie jemals auf Primalität überprüft werden möchten.

Ich habe einen Fermat-Pseudoprime-Test entwickelt, der für alle Blätter funktioniert:

      

(63973 ist eine Carmichael-Nummer .)

Wenn dieser Test true zurückgibt, zsollte er dem Satz hinzugefügt werden aund wir sollten fortfahren str(z). Der verantwortliche Code ist:

z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)

Zunächst möchten wir uns mit dem Fall befassen z == 2. Wir tun dies, indem 2wir es hier einfach ausweichen und beim ersten Definieren hart codieren a! (EDIT: Und nichts Schädliches passiert, wenn wir auch fangen z == 1.) Also können wir das z ≥ 3jetzt annehmen .

Ich habe einige „und“ in einen kurzgeschlossenen verketteten Vergleich übersetzt: Die ersten drei Vergleiche müssen vorher erfolgreich sein a.add(z)und f(u)werden jemals ausgewertet. Hier sind alle ihre Rollen:

  1. z%91>0kodiert unsere erste Bedingung. (63973 ist durch 91 teilbar, was selbst kein Blatt ist, also erkennen wir es so.)
  2. 0<2ist immer wahr, aber die Verkettung ist kürzer als and.
  3. 2==pow(2,z,z) kodiert unsere zweite Bedingung.
  4. pow(2,z,z)>a.add(z)Löst die Addition aus und ist immer wahr, da set.addRückgaben Noneund Ganzzahlen immer größer als sind None.
  5. a.add(z)<f(u)löst die Rekursion aus. Sein Wahrheitswert ist unwichtig.

Danksagung

  • Dennis hat vier Bytes gespeichert ( u=[d+s,s+d][I]u=d[I:]+s+d*I; z==2z<3und den Mod 91- Trick). Vielen Dank!
Lynn
quelle