14
\$\begingroup\$

A Pillai prime is a prime number \$p\$ for which there exists some positive \$m\$ such that \$(m! + 1) \equiv 0 \:(\text{mod } p)\$ and \$p \not\equiv 1\:(\text{mod }m)\$.

In other words, an integer \$p\$ is a Pillai prime if it is a prime number, if there exists another positive integer \$m\$ such that the factorial of \$m\$, plus \$1\$ is divisible by \$p\$ and if \$p - 1\$ isn't divisible by \$m\$.


Given a positive integer as input, decide whether it is a Pillai prime. The sequence of Pillai primes is OEIS A063980.

For example, \$23\$ is a Pillai prime because:

  • It is a prime number, having only 2 factors.
  • \$m = 14\$ and \$m = 18\$ satisfy the above conditions: \$23 \mid (14! + 1)\$ and \$14\$ does not divide \$22\$; \$23 \mid (18! + 1)\$ and \$18\$ does not divide \$22\$ either.

Test cases

Truthy:

23
59
83
109
139
593

Falsy:

5
7
8
73
89
263
437

For the truthy cases, the respective m's are [(23, [14, 18]), (59, [15, 40, 43]), (83, [13, 36, 69]), (109, [86]), (139, [16]), (593, [274])].


You can either follow the standard output format (that is, truthy / falsy values) or have a consistent value for Pillai primes and a non-consistent value otherwise or vice-versa.

You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is , so the shortest submission (in bytes) for every language wins.

\$\endgroup\$
  • \$\begingroup\$ Can the input be a composite integer? \$\endgroup\$ – JungHwan Min Apr 27 '18 at 17:59
  • \$\begingroup\$ @JungHwanMin Yes, the input can be a composite integer. \$\endgroup\$ – Mr. Xcoder Apr 27 '18 at 18:01
  • \$\begingroup\$ I suggest a test case like 437, which is composite but divides 18!+1. \$\endgroup\$ – Nitrodon Apr 27 '18 at 18:16
  • \$\begingroup\$ @Nitrodon Added that test case, thank you! \$\endgroup\$ – Mr. Xcoder Apr 27 '18 at 18:19
  • 1
    \$\begingroup\$ @DanielIndie Here you go: [(23, 14), (23, 18), (59, 15), (59, 40), (59, 43), (83, 13), (83, 36), (83, 69), (109, 86), (139, 16), (593, 274)]. I've also added them to the challenge. \$\endgroup\$ – Mr. Xcoder Apr 27 '18 at 18:39

15 Answers 15

9
\$\begingroup\$

Python 2, 115 111 110 109 bytes

-6 bytes thanks to Mr. Xcoder

lambda n:n>2and cmp(*map(all,zip(*[[n%x==1or~f(x)%n,n%x]for x in range(2,n)])))<0
f=lambda x:0**x or x*f(x-1)

Try it online!

The functions consist of two parts ~-n%x<1or~f(x)%n>0 that verifies if n don't satisfies the "Pillai conditions", and n%x>0 for the prime validation.
After that all is applied to both items, the first item will contain False/0 if there is a valid "Pillai number", and the second will contain True/1 if n is prime.
These are passed to cmp that will return -1 in this cenario (is a valid Pillai prime). The other combinations [[0, 0], [1, 0], [1, 1]] will return 0 or 1

\$\endgroup\$
  • 2
    \$\begingroup\$ +1, clever algorithms (and their explanations) are why I love this SE \$\endgroup\$ – IanF1 Apr 27 '18 at 20:25
8
\$\begingroup\$

Jelly, 11 8 bytes

Ṗ!%ẹ’ḍ’E

Returns 0 for Pillai prime, 1 otherwise.

Try it online!

How it works

Ṗ!%ẹ’ḍ’E  Main link. Argument: n

Ṗ         Pop; yield [1, ..., n-1].
 !        Take the factorial of each integer.
  %       Take the factorials modulo p.
   ẹ’     Find all indices of n-1.
     ḍ’   Test n-1 for divisibility by each of these indices.
       E  Return 1 if all of the resulting Booleans are equal (all 1 means there is
          no suitable m, all 0 means n is not prime), 0 if they are different.
\$\endgroup\$
  • 1
    \$\begingroup\$ That's roughly how I would have done it too, but I didn't manage to prove that m ∈ [1, n). \$\endgroup\$ – Erik the Outgolfer Apr 28 '18 at 16:32
  • 4
    \$\begingroup\$ If m ≥ n, then m! is divisble by n, so m! + 1 ≡ 1 (mod n). \$\endgroup\$ – Dennis Apr 28 '18 at 22:41
6
\$\begingroup\$

Pari/GP, 44 bytes

p->isprime(p)&&sum(m=2,p,p%m-1&&!((m!+1)%p))

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Brachylog, 19 bytes

ṗ>.ḟ+₁;?%0&-₁;.%>0∧

Try it online!

Pretty straightforward translation of the question:

ṗ          Input is a prime
>.         And output is a number less than the input
ḟ+₁;?%0    And output's factorial + 1 mod input is 0
&-₁;.%>0   And input - 1 mod output is greater than 0
∧          No further constraints
\$\endgroup\$
3
\$\begingroup\$

J, 30 26 bytes

-4 bytes thanks to FrownyFrog

1 e.i.((|1+!)~<1~:|)1&p:*]

Try it online!

Explanation:

                        1&p:*]      checks if the number is prime and if not sets it to 0
                   1~:|             checks if p is not 1 mod m
           (|1+!)~                  m factorial plus 1 modulo n
                  <                 are both conditions met?  
       i.                           generates successive m's (a list 0..n-1)
   1 e.                             1's are at the indices of m, so if there's 1 - Pillai
\$\endgroup\$
  • 1
    \$\begingroup\$ Check that modulo n is less than 1~:| to save 2 bytes. \$\endgroup\$ – FrownyFrog Apr 28 '18 at 8:49
  • 1
    \$\begingroup\$ (]|1+!@[) is just (|1+!)~ \$\endgroup\$ – FrownyFrog Apr 28 '18 at 8:51
  • \$\begingroup\$ @FrownyFrog - Thank you! I was thinking about ~ and it makes sence with your previous comment. \$\endgroup\$ – Galen Ivanov Apr 28 '18 at 9:05
3
\$\begingroup\$

Python 2, 65 64 53 52 bytes

f=lambda n,k=3,m=2:~m%n<1<n%k%(n%~-k)or f(n,k+1,m*k)

Output is via presence or absence of an error.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 109 107 bytes

lambda p:any(~-p%m>~l(m)%p<1for m in range(2,p))*all(p%i for i in range(2,p-1))
l=lambda a:0**a or a*l(a-1)

Try it online!


Explanation

The l finds the factorial of the number passed in, so 5 as input returns 120.

The all(p%i for i in range(2,p-1)) checks to see if a number is prime, we ignore 0 and 1 as our other conditions already rule those out.

Finally, we use any(~-p%m>-~l(m)%p==0for m in range(2,p)) to iterate through all potential m's looking to see if any satisfies our needs. ~-p means p+1. Then we check to see if it is greater than -~l(m)%p (which translates to (m!-1)%p, and then we compare it to 0. Basically ~-p%m must be greater than 0 and -~l(m)%p must be 0.


Sources


Improvements

\$\endgroup\$
2
\$\begingroup\$

as you probably can see in the tio link not all cases pass, thats because js cant handle big numbers,if such requirement exists ill try to implement it :)

there is a double check F%n>n-2&(F+1)%n<1 to prevent false positive(but not the other way around with js big number issues,we do really need (F+1)%n<1 for smaller numbers whice reduces the solution byte count to 60

JavaScript (Node.js), 90 88 86 72 68 bytes

  • thanks to Arnauld for reducing by 1 byte
f=(n,F=i=2,g=0)=>n%i?f(n,F*=++i,g|=F%n>n-2&(F+1)%n<1&~-n%i>0):i==n*g

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 13 bytes

>.ḟ+₁ḋ∋?-₁f≡ⁿ

Try it online!

Succeeds for Pillai primes, providing the smallest m through the output variable, and fails for anything else. Since a large part of how this saves bytes over sundar's solution is that it repeatedly computes the prime factorizations of some pretty big numbers, it's quite incredibly slow on larger inputs. (I'll probably run those cases on my local Brachylog installation once my laptop isn't on battery power.)

 .               The output
>                is less than the input,
       ?         the input
      ∋          is an element of
     ḋ           the prime factorization of
 .               the output's
  ḟ              factorial
   +₁            plus one,
           ≡ⁿ    and the output is not an element of
          f      the list of all factors of
       ?         the input
        -₁       minus one.
\$\endgroup\$
1
\$\begingroup\$

[Perl], 45 bytes

use ntheory":all";is_prime($n)&&is_pillai($n)

The number theory module has the predicates as built-in functions (is_pillai actually returns either 0 or the smallest m, so solves A063828 as well). The underlying C and Perl code is not golfed (of course). The C code looks like:

UV pillai_v(UV n) {
  UV v, fac = 5040 % n;
  if (n == 0) return 0;
  for (v = 8; v < n-1 && fac != 0; v++) {
    fac = (n < HALF_WORD) ? (fac*v) % n : mulmod(fac,v,n);
    if (fac == n-1 && (n % v) != 1)
      return v;
  }
  return 0;
}

(generically replace UV with uint64_t or similar, and HALF_WORD decides whether we can optimize the mulmod into simple native ops).

The pure Perl code is similar to:

sub is_pillai {
  my $p = shift;
  return 0 if $p <= 2;
  my($pm1, $nfac) = ($p-1, 5040 % $p);
  for (my $n = 8; $n < $p; $n++) {
    $nfac = mulmod($nfac, $n, $p);
    return $n if $nfac == $pm1 && ($p % $n) != 1;
  }
  0;
}
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 64 bytes

f(n,k,m,r){for(k=m=1,r=0;k<n;m=m*++k%n)r|=m/~-n<<(n%k==1);r/=3;}

Try it online!

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

Whispers v2, 230 bytes

> 1
> Input
>> 1…2
>> L!
>> L+1
>> L∣2
>> L⋅R
>> 2%L
>> Each 4 3
>> Each 5 9
>> Each 6 10
>> Each 7 11 3
> {0}
>> 12∖13
>> Each 8 14
>> L≠1
>> Each 16 15
>> Each 7 17 15
>> 18∖13
>> [19]
>> 2’
>> 21⋅20
>> Output 22

Try it online!

This returns an empty list for non-Pillai primes, and a non-empty list otherwise.

How it works

Whispers was designed for manipulation on real/complex numbers, with a little bit of array commands added for good measure, hence the repeated use of Each to iterate over the generated lists.

A bit of background on Whispers:

Whispers is slightly different in it's execution path to most other languages. Rather than work through each line linearly, only branching at conditionals, Whispers begins on the last line in the file beginning with > (the rules are slightly more complicated than that, but that's all we need to know for now), and the meanings of numbers differ, depending on whether the line starts with > or >>.

If the line starts with >, such as > 1 or > Input, this is a constant line - it returns the same value each time. Here, numbers represent their numerical form, so the first line will always return 1 when called.

If the line starts with >> however, numbers are treated as references to other lines, sort of like function calls, if you will. For example, in the line >> 1…2, this does not perform the command on the integers 1 and 2, but rather on the values returned from lines 1 and 2. In this case, those values are the integer 1 and whatever integer we're passed as input.

For this example, let's consider the input of 23. Keep in mind that, due to Whispers' preprocessing, the second line (> Input) is converted to > 23.

Our first command is on line 3: >> 1…2. is dyadic range, in this case from 1 to 23, yielding {1, 2, ... 22, 23}. Next, we skip down to lines 9 through 12:

>> Each 4 3
>> Each 5 9
>> Each 6 10
>> Each 7 11 3

Here we have 4 consectutive Each statements, each of which iterate over the previous result, essentially mapping the 4 commands over the array on line 3: the range. The first three statements are simple maps, with lines 4, 5 and 6:

>> L!
>> L+1
>> L∣2

These three commands, over an integer n, yields (n!+1)∣x, where ! denotes factorial, denotes divisbility and x is the input. Finally, line 12 has a dyadic map structure.

A dyadic map structure takes three integers: the target, the left and the right, each indexes to other lines. Here, we zip the left and the right to produce a list of pairs, then reduce each pair by the dyadic command (the target). Here, if the input is 23, the lists are {1, 2, ... 22, 23} and {0, 0, ... 1, 0} and the command is

>> L⋅R

which multiplies the left argument by the right. This produces an array of integers, with 0 at the indexes of integers whose factorials incremented aren't divisible by the inputs, and the original index where they are. We'll call this array A. Next, we remove the 0s from A by taking the set difference between {0} and A:

> {0}
>> 12∖13

With our example input, this produces the set {14, 18, 22}. Next we take the remainder of the input being divided by each value in the set, and check if that remainder is not equal to 1:

>> 2%L
>> Each 8 14
>> L≠1
>> Each 16 15

Again, we have a list of either 0 or 1s and need to remove the 0s and replace the 1s with the original values. Here we repeat the code we saw above, but with >> 18∖13 rather than 12. Finally, we cast this resulting set to a list for a final check. Unfortunately, our code must also reject composite numbers which achieve all these criteria, such as 437. So we add our final check, multiplying our final list by the primality of the input. Due to how Python multiplication works on lists, 0 replaces it with an empty list, and 1 has no effect. So we calculate the primality of the input, multiply that by the list of ms for the input and ouput the final result:

>> 2’
>> 21⋅20
>> Output 22
\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 65 chars, 130 bytes

{∼0π⍵:0⋄m←⎕ct⋄⎕ct←0⋄r←⍬≢a/⍨{0≠⍵∣p}¨a←k/⍨0=⍵∣1+!k←⍳p←¯1+⍵⋄⎕ct←m⋄r}

Here 23x it would mean 23r1 and so the fraction 23/1, so all the others; test:

  f←{∼0π⍵:0⋄m←⎕ct⋄⎕ct←0⋄r←⍬≢a/⍨{0≠⍵∣p}¨a←k/⍨0=⍵∣1+!k←⍳p←¯1+⍵⋄⎕ct←m⋄r}
  f¨23x 59x 83x 109x 139x 593x
1 1 1 1 1 1 
  f¨5x 7x 73x 89x 263x 437x
0 0 0 0 0 0 
\$\endgroup\$
0
\$\begingroup\$

C# (Visual C# Interactive Compiler), 138+22=160 bytes

n=>Enumerable.Range(2,n-2).All(x=>n%x>0)&Enumerable.Range(1,n).Any(x=>{BigInteger a,b=1;for(a=1;a<=x;a++)b*=a;return(b+1)%n<1&(n-1)%x>0;})

TIO has not implemented the System.Numerics library in it's release of Mono, so you can see the results Try it online! Here instead.

Explanation:

using System.Numerics; //necessary to handle large numbers created by the factorials

return 
    Enumerable.Range(2,n-2).All(x=>n%x>0)       // is prime
    &
    Enumerable.Range(1,n).Any(x=>
    {
        BigInteger a,b=1;for(a=1;a<=x;a++)b*=a; //b = a!
        return (b+1)%n<1
               &                                //the condition for PPs
               (n-1)%x>0;             
    });
\$\endgroup\$
0
\$\begingroup\$

CJam, 37 bytes

ri_mp\[_{_M)m!)@%!\_M)%1=!@&\}fM]);:|

Outputs 11 if input is a pillai prime, otherwise 00, 01 or 10

Explanation:

                                         e# Explanation | Stack
ri_mp\[_{_M)m!)@%!\_M)%1=!@&\}fM]);:|    e# Whole code | Example input: 593
ri                                       e# Read input as integer | 593
  _                                      e# Duplicate | 593 593
   mp                                    e# Is it prime? | 593 1
     \                                   e# Swap top two stack elements | 1 593
      [                         ]        e# Delimits an array. Any operations that
                                         e# push a value are placed into the array
       _                                 e# Duplicate | 1 593 [593]
        {                    }fM         e# A for loop from 0 to (n-1) looped through
                                         e# variable M
         _                               e# Duplicate top stack value | ...[593 593]
          M)                             e# Get M+1, as if we try M=0 we get an error
                                         e# | ...[593 593 1]
            m!                           e# Factorial | ...[593 593 1]
              )                          e# Add one | ...[593 593 2]
               @                         e# Rotate stack | ...[593 2 593]
                %                        e# Modulus | ...[593 2]
                 !                       e# Equal to 0? | ...[593 0]
                  \_                     e# Swap and duplicate | ...[0 593 593]
                    M)                   e# Push M+1 | ...[0 593 593 1]
                      %                  e# Modulus | ...[0 593 0]
                       1=!               e# Not equal to 1? | ...[0 593 1]
                          @              e# Rotate | ...[593 1 0]
                           &             e# AND | ...[593 0]
                            \            e# Swap | ...[0 593]
                             }     
                                ]
                                 );      e# Dump and discard last element
                                         e# | 1 593 [...]
                                   :|    e# Flatten array with OR | 1 1
                                         e# Implicit output

Try it online!

\$\endgroup\$

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.