Prime Modified Z-Factorials
Lassen Sie mich nacheinander die oben genannten Begriffe erklären ...
Wir werden \ anrufen$\text{Z-Factorial}(n)\$einer positiven ganzen Zahl \$n\$, \$n!\$(dh \$n\$Fakultät) ohne nachgestellte Nullen. Also, \$\text{Z-Factorial}(30)\$ist \$26525285981219105863630848\$weil \$30!=265252859812191058636308480000000\$
Wir werden Modified Z-Factorialvon \ anrufen$n\$, das \$\text{Z-Factorial}(n) \mod n\$.
Also Modified Z-Factorialvon \$30\$ist \$\text{Z-Factorial}(30) \mod 30\$welches ist \$26525285981219105863630848 \mod 30 = 18\$
Wir sind in den Interessenten \$n\$'s für die das Modified Z-Factorial of neine Primzahl ist
Beispiel
Die Nummer \$545\$ist PMZ weil \$\text{Z-Factorial}(545) \mod 545 = 109\$ Das ist Prime
Hier ist eine Liste der ersten Werte von \$n\$ das produzieren Prime Modified Z-Factorial (PMZ)
5,15,35,85,545,755,815,1135,1165,1355,1535,1585,1745,1895,1985,2005,2195,2495,2525,2545,2615,2705,2825,2855,3035,3085,3155,3205,3265,3545,3595,3695,3985,4135,4315,4385,4415,4685,4705,4985,5105,5465,5965,6085,6155,6185,6385,6415,6595...
Aufgabe
Die obige Liste geht weiter und Ihre Aufgabe ist es, das \ zu finden$k\$th PMZ
Eingang
Eine positive ganze Zahl \$k\$
Ausgabe
Das \$kth\$ PMZ
Testfälle
Hier sind einige 1-indizierte Testfälle.
Bitte geben Sie an, welches Indizierungssystem Sie in Ihrer Antwort verwenden, um Verwirrung zu vermeiden.
Ihre Lösungen müssen nur innerhalb der Grenzen der nativen Ganzzahlgröße Ihrer Sprache funktionieren.
input -> output
1 5
10 1355
21 2615
42 5465
55 7265
100 15935
500 84815
Dies ist Code-Golf , also gewinnt die niedrigste Punktzahl in Bytes.
Antworten
05AB1E , 16 Bytes
[N!0ÜN%pi®>©¹Q#N
Die Eingabe ist 1-basiert k.
Gibt die k-te PMZ aus.
Erläuterung:
[N!0ÜN%pi®>©¹Q#N
[ Start infinite loop
N! Factorial of the index
0Ü Remove trailing zeros
N% Mod index
p Is prime?
i If it is:
®>© Increment the value stored in register c (initially -1)
¹Q Is the value equals the input?
#N If it does, push the index (which is the PMZ) and break
Probieren Sie es online aus!
Gelee , 13 11 Bytes
!Dt0Ḍ%⁸Ẓµ#Ṫ
Eine vollständige Programmlesung von STDIN, die das Ergebnis an STDOUT druckt.
Probieren Sie es online aus!
Wie?
!Dt0Ḍ%⁸Ẓµ#Ṫ - Main Link: no arguments
# - set n=0 (implicit left arg) and increment getting the first
(implicit input) values of n which are truthy under:
µ - the monadic chain (f(n)):
! - factorial -> n!
D - convert from integer to decimal digits
t0 - trim zeros
Ḍ - convert from decimal digits to integer
⁸ - chain's left argument, n
% - modulo
Ẓ - is prime?
Ṫ - tail
- implicit print
Add ++ , 58 Bytes
D,f,@,Rb*BDBGbUdb*!!*BFJiA%P
x:?
Wx,`y,+1,`z,$f>y,`x,-z
Oy
Probieren Sie es online aus!
Zeitüberschreitung für \ $ k \ ge 30 \ $ bei TIO
Wie es funktioniert
D,f,@, ; Define a function, f, taking 1 argument, n
; Example: STACK = [30]
Rb* ; Factorial STACK = [265252859812191058636308480000000]
BD ; Convert to digits STACK = [2 6 5 ... 0 0 0]
BGbU ; Group adjacents STACK = [[2] [6] [5] ... [8] [4] [8] [0 0 0 0 0 0 0]]
db*!! ; If last is all 0s
*BF ; remove it STACK = [[2] [6] [5] ... [8] [4] [8]]
Ji ; Join to make integer STACK = [26525285981219105863630848]
A% ; Mod n STACK = [18]
P ; Is prime? STACK = [0]
; Return top value 0
x:? ; Set x to the input
Wx, ; While x > 0
`y,+1, ; y = y + 1
`z,$f>y, ; z = f(y)
`x,-z ; x = x - z
; We count up with y
; If y is PMZ, set z to 1 else 0
; Subtract z from x, to get x PMZs
Oy ; Output y
Japt , 13 Bytes
0-indiziert. Funktioniert in der Praxis nur für 0& 1, sobald wir darüber 21!nachdenken, überschreiten wir JavaScript MAX_SAFE_INTEGER.
ÈÊsÔsÔuX j}iU
Versuch es
ÈÊsÔsÔuX j}iU :Implicit input of integer U
È :Function taking an integer X as argument
Ê : Factorial
s : String representation
Ô : Reverse
sÔ : Repeat (There has to be a shorter way to remove the trailing 0s!)
uX : Modulo X
j : Is prime?
} :End function
iU :Pass all integers through that function, returning the Uth one that returns true
R , 99 93 Bytes
Bearbeiten: -6 Bytes (und -4 Bytes aus der Version mit beliebiger Genauigkeit) dank Giuseppe
k=scan();while(k){F=F+1;z=gamma(F+1);while(!z%%5)z=z/10;x=z%%F;k=k-(x==2|all(x%%(2:x^.5)))};F
Probieren Sie es online aus!
Verwendet den einfachen Ansatz und folgt den Schritten der Erklärung. Leider überschreitet er die Grenzen der numerischen Genauigkeit von R bei Fakultät (21) und schlägt daher für jedes k> 2 fehl.
Eine Version mit beliebiger Genauigkeit (die nicht auf kleine k beschränkt ist, aber weniger wettbewerbsfähig ist) ist:
R + gmp, 115 Bytes
Schale , 11 Bytes
!foṗS%ȯ↔↔ΠN
Probieren Sie es online aus!
Erläuterung
!foṗS%ȯ↔↔ΠN
f N filter list of natural numbers by:
Π take factorial
↔↔ reverse twice, remove trailing zeros
S% mod itself
ṗ is prime?
! get element at index n
JavaScript (Node.js) , 89 ... 79 77 Bytes
n=>(g=y=>y%10n?(p=k=>y%--k?p(k):~-k||--n?g(x*=++i):i)(y%=i):g(y/10n))(x=i=2n)
Probieren Sie es online aus!
Python 3 , 145 140 138 129 Bytes
def f(n,r=0):
c=d=2
while r<n:
c+=1;d*=c
while 1>d%10:d//=10
i=d%c;r+=i==2or i and min(i%j for j in range(2,i))
return c
Probieren Sie es online aus!
Python 2 , 126 125 Bytes
def f(n,r=0):
c=d=2
while r<n:
c+=1;d*=c
while d%10<1:d/=10
i=d%c
r+=i==2or i and min(i%j for j in range(2,i))
print c
Probieren Sie es online aus!
Erläuterung: Teilen Sie weiter durch 10, solange die aktuelle Fakultät durch 10 teilbar ist, und überprüfen Sie dann die aktuelle Modulo-Modulo-Zahl auf Primalität.
Dank caird coinheringaahing für -20 Bytes und Dominic van Essen für -9 Bytes!
Haskell , 129 111 Bytes
g n
|n`mod`10>0=n
|0<1=g$div n 10 f=(!!)[n|n<-[1..],let p=mod(g$product[1..n])n,[x|x<-[2..p],mod p x<1]==[p]]
Probieren Sie es online aus!
gentfernt 0s von Nummer.
fnimmt kte Element aus einem unendlichen Liste Verständnis wo:
[x|x<-[2..p],mod p x==0]==[p]ist primeBedingung (vergleicht Liste der Divisoren pund eine Liste von nur p).
Und pwird mod(g$foldr(*)1[1..n])ndas Modulo der Fakultät durchlaufen g.
18 dank Benutzer gespeichert