20
\$\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, 2020 at 17:59
  • \$\begingroup\$ You are right! Let me fix this... \$\endgroup\$
    – ZaMoC
    Aug 17, 2020 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\$ Aug 17, 2020 at 18:19
  • \$\begingroup\$ @cairdcoinheringaahing be my guest! \$\endgroup\$
    – ZaMoC
    Aug 17, 2020 at 18:20
  • 1
    \$\begingroup\$ @Shaggy Absolutely yes \$\endgroup\$
    – ZaMoC
    Aug 17, 2020 at 22:51

9 Answers 9

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, 2020 at 17:34
  • \$\begingroup\$ How did I missed that?! Thank you.. Should I add it to this answer? \$\endgroup\$
    – SomoKRoceS
    Aug 18, 2020 at 17:57
  • 1
    \$\begingroup\$ Yep feel free to edit it in! \$\endgroup\$
    – Grimmy
    Aug 19, 2020 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\$ Aug 17, 2020 at 18:42
  • \$\begingroup\$ @FryAmTheEggman ...turns out I can if I use a link rather than a chain, so back to 13 again :) \$\endgroup\$ Aug 17, 2020 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\$ Aug 17, 2020 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\$ Aug 17, 2020 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\$ Aug 17, 2020 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, 2020 at 19:39
  • \$\begingroup\$ Thanks Giuseppe! \$\endgroup\$ Aug 19, 2020 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, 2020 at 9:12
  • \$\begingroup\$ @HighlyRadioactive What do you mean? \$\endgroup\$
    – Arnauld
    Aug 18, 2020 at 9:17
  • \$\begingroup\$ A bad, dirty joke. Never mind. \$\endgroup\$
    – null
    Aug 18, 2020 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, 2020 at 16:59
  • 1
    \$\begingroup\$ Make that 113 \$\endgroup\$
    – user
    Aug 18, 2020 at 17:03
  • 1
    \$\begingroup\$ Thanks @user I don't know these tricks! \$\endgroup\$
    – AZTECCO
    Aug 18, 2020 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.