18
\$\begingroup\$

Let me explain one by one the above terms...

We will call \$\text{Z-Factorial}(n)\$ of a positive integer \$n\$, \$n!\$ (i.e. \$n\$ factorial) without any trailing zeros. So, \$\text{Z-Factorial}(30)\$ is \$26525285981219105863630848\$ because \$30!=265252859812191058636308480000000\$

We will call Modified Z-Factorial of \$n\$, the \$\text{Z-Factorial}(n) \mod n\$.
So, Modified Z-Factorial of \$30\$, is \$\text{Z-Factorial}(30) \mod 30\$ which is \$26525285981219105863630848 \mod 30 = 18\$

We are interested in those \$n\$'s for which the Modified Z-Factorial of n is a Prime Number

Example

The number \$545\$ is PMZ because \$\text{Z-Factorial}(545) \mod 545 = 109\$ which is prime

Here is a list of the first values of \$n\$ that produce 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...         

Task

The above list goes on and your task is to find the \$k\$th PMZ

Input

A positive integer \$k\$

Output

The \$kth\$ PMZ

Test Cases

here are some 1-indexed test cases.
Please state which indexing system you use in your answer to avoid confusion.
Your solutions need only work within the bounds of your language's native integer size.

input -> output     
 1        5     
 10       1355       
 21       2615     
 42       5465     
 55       7265      
 100      15935
 500      84815

This is , so the lowest score in bytes wins.

\$\endgroup\$
10
  • \$\begingroup\$ I think we have Z-Factorial(755) mod 755 = 151, which is prime. Yet it's not included in your list. Am I missing something? \$\endgroup\$ – Arnauld Aug 17 '20 at 17:59
  • \$\begingroup\$ You are right! Let me fix this... \$\endgroup\$ – ZaMoC Aug 17 '20 at 18:02
  • 1
    \$\begingroup\$ Do you mind me adding in some MathJax to the question body? It's slightly hard to read with all the code blocks \$\endgroup\$ – caird coinheringaahing Aug 17 '20 at 18:19
  • \$\begingroup\$ @cairdcoinheringaahing be my guest! \$\endgroup\$ – ZaMoC Aug 17 '20 at 18:20
  • 1
    \$\begingroup\$ @Shaggy Absolutely yes \$\endgroup\$ – ZaMoC Aug 17 '20 at 22:51
3
\$\begingroup\$

05AB1E, 16 bytes

[N!0ÜN%pi®>©¹Q#N

Input is 1-based k.

Outputs the k-th PMZ.

Explanation:

[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

Try it online!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Seems like you’re not aware of the µ built-in. 9 bytes: µNN!0ÜN%p \$\endgroup\$ – Grimmy Aug 18 '20 at 17:34
  • \$\begingroup\$ How did I missed that?! Thank you.. Should I add it to this answer? \$\endgroup\$ – SomoKRoceS Aug 18 '20 at 17:57
  • 1
    \$\begingroup\$ Yep feel free to edit it in! \$\endgroup\$ – Grimmy Aug 19 '20 at 2:44
3
\$\begingroup\$

Jelly,  13  11 bytes

!Dt0Ḍ%⁸Ẓµ#Ṫ

A full program reading from STDIN which prints the result to STDOUT.

Try it online!

How?

!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
\$\endgroup\$
8
  • 1
    \$\begingroup\$ @FryAmTheEggman Ah, I thought I could remove the ³. \$\endgroup\$ – Jonathan Allan Aug 17 '20 at 18:42
  • \$\begingroup\$ @FryAmTheEggman ...turns out I can if I use a link rather than a chain, so back to 13 again :) \$\endgroup\$ – Jonathan Allan Aug 17 '20 at 18:45
  • \$\begingroup\$ Nice! When you are done golfing I'm really curious what the 5 is doing. I only know Jelly mildly and it seems quite odd (removing it sometimes causes off by one errors?). \$\endgroup\$ – FryAmTheEggman Aug 17 '20 at 19:02
  • 1
    \$\begingroup\$ @FryAmTheEggman 5 is the starting value of the incremental search which otherwise defaults to the input (so we find the first n integers starting at 5 counting up that satisfy the property rather than the first n integers starting at n) - the just gives us the last one. EDIT: Although saying that we can get rid of it by using STDIN... \$\endgroup\$ – Jonathan Allan Aug 17 '20 at 19:06
  • 1
    \$\begingroup\$ Not the most usual method of golf help, but if it works it works :) I was wondering why it wasn't beating my test program in Pyth by more since you had access to trim, now it seems much cleaner! \$\endgroup\$ – FryAmTheEggman Aug 17 '20 at 19:17
2
\$\begingroup\$

Add++, 58 bytes

D,f,@,Rb*BDBGbUdb*!!*BFJiA%P
x:?
Wx,`y,+1,`z,$f>y,`x,-z
Oy

Try it online!

Times outs for \$k \ge 30\$ on TIO

How it works

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
\$\endgroup\$
2
\$\begingroup\$

Japt, 13 bytes

0-indexed. Only works, in practice, for 0 & 1 as once we go over 21! we exceed JavaScript's MAX_SAFE_INTEGER.

ÈÊsÔsÔuX j}iU

Try it

ÈÊ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
\$\endgroup\$
2
\$\begingroup\$

R, 99 93 bytes

Edit: -6 bytes (and -4 bytes from arbitrary-precision version) thanks to 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

Try it online!

Uses the straightforward approach, following the steps of the explanation. Unfortunately goes out of limits of R's numerical accuracy at factorial(21), so fails for any k>2.

An arbitrary-precision version (which is not limited to small k, but is less golf-competitive) is:
R + gmp, 115 bytes

\$\endgroup\$
2
  • \$\begingroup\$ 93 bytes. Similar golfs can (probably) be applied to the gmp approach \$\endgroup\$ – Giuseppe Aug 18 '20 at 19:39
  • \$\begingroup\$ Thanks Giuseppe! \$\endgroup\$ – Dominic van Essen Aug 19 '20 at 7:25
2
\$\begingroup\$

Husk, 11 bytes

!foṗS%ȯ↔↔ΠN

Try it online!

Explanation

!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
\$\endgroup\$
1
\$\begingroup\$

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)

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ g=y (15 chars) \$\endgroup\$ – null Aug 18 '20 at 9:12
  • \$\begingroup\$ @HighlyRadioactive What do you mean? \$\endgroup\$ – Arnauld Aug 18 '20 at 9:17
  • \$\begingroup\$ A bad, dirty joke. Never mind. \$\endgroup\$ – null Aug 18 '20 at 9:18
1
\$\begingroup\$

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

Try it online!

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

Try it online!


Explanation: Keep dividing by 10 as long as the current factorial is divisible by 10, and then check the factorial modulo current number for primality.

Thanks to caird coinheringaahing for -20 bytes and Dominic van Essen for -9 bytes!

\$\endgroup\$
4
1
\$\begingroup\$

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]]

Try it online!

g removes 0s from number.

f takes kth element from an infinite list comprehension where:
[x|x<-[2..p],mod p x==0]==[p] is prime condition( compares list of divisors of p and a list of just p).

And p is mod(g$foldr(*)1[1..n])n the modulo of factorial passed through g.

Saved 18 thanks to user

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Wow, this is way more concise than the one I got. I think you can reduce it even more to 123 bytes \$\endgroup\$ – user Aug 18 '20 at 16:59
  • 1
    \$\begingroup\$ Make that 113 \$\endgroup\$ – user Aug 18 '20 at 17:03
  • 1
    \$\begingroup\$ Thanks @user I don't know these tricks! \$\endgroup\$ – AZTECCO Aug 18 '20 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.