Looks prime to me!

Question

Figuring out whether a given number is prime, while not very complicated, is kind of hard. But making a guess doesn't need to be.

Seeing whether a number is a multiple of 2 or 5 is easy - you can just look at the last digit. Multiples of 3 isn't much harder, just add up the digits and see if you end up with a multiple of 3. Multiples of 11 are also easy enough, at least as long as they're fairly small. Any other number might not be prime, but at least they look like they might be prime. Or at least, that's how it works in base ten. As a person who frequently uses base ten, you can probably also identify the single-digit primes, and know that 11 is a prime as well.

We can generalize this to other bases. In some base \$b \ge 2\$, you can find fairly simple divisibility rules for any factor of \$b, b-1 \text{ or }b+1\$. You also presumably know all the prime numbers up to and including \$b+1\$.

But in any base, you eventually start running into numbers that look prime, but aren't. And I want to know when that happens. I know that in base 10, the first such number is 49 (not divisible by 2, 3, 5 or 11, but also not prime), in base 12 it's 25 (not divisible by 2, 3, 11 or 13), and in base 27, it's 55 (not divisible by 2, 3, 7 or 13, and unlike 25 it's also big enough to require two digits!). But for other bases? That's where you come in!

Rules

Your task is to write a program or function which takes as input some integer \$b\ge2\$ and outputs the first integer which, when written in base \$b\$ looks like it might be prime, but isn't. That is to say, the smallest integer that

• Is a composite number and
• Is greater than \$b\$ and
• Is coprime with (does not share any prime factors with) \$b-1\$, \$b\$ and \$b+1\$

This is related to OEIS A090092, but starts to diverge at \$b=27\$

This is code-golf, so save those bytes!

Test cases

Base -> Smallest pseudo-prime
2 -> 25
5 -> 49
6 -> 121
10 -> 49
12 -> 25
27 -> 55
32 -> 35
34 -> 169
37 -> 49
87 -> 91
88 -> 91
89 -> 91
121 -> 133
123 -> 125
209 -> 289

Answer 1

Haskell, 53 bytes

f b=[x|x<-[b..],k<-[2..x-1],mod x k+gcd(b^3-b)x<2]!!0

Try it online!

Answer 2

JavaScript (ES6),  91 83 79  76 bytes

f=(b,n=b,k=n)=>(g=d=>k<2?d<n:k%d?g(d+1):b*~-b*~b%d&&g(d,k/=d))(2)?n:f(b,n+1)

Try it online!

How?

Given the base \$b\$, we look for the smallest integer \$n\ge b\$ with a prime divisor \$d\$ which is neither \$n\$ itself nor a divisor of \$b-1\$, \$b\$ or \$b+1\$.

Commented

f = (                  // f is a recursive function taking:
  b,                   //   b = input base
  n = b,               //   n = candidate number, starting at b
  k = n                //   k = copy of n
) => (                 //
  g = d =>             // g is a recursive function taking a divisor d
    k < 2 ?            // if k = 1:
      d < n            //   successful if d is smaller than n
    :                  // else:
      k % d ?          //   if d is not a divisor of k:
        g(d + 1)       //     do recursive calls with d + 1 until it is
      :                //   else:
        b * ~-b * ~b   //     if b(b - 1)(b + 1) ...
        % d &&         //     ... is not divisible by d:
          g(d, k /= d) //       do a recursive call with k divided by d
  )(2)                 // initial call to g with d = 2
  ?                    // if successful:
    n                  //   return n
  :                    // else:
    f(b, n + 1)        //   try again with n + 1

Answer 3

Gaia, 21 20 18 bytes

1⟨+:ṗ!¤@3*@⁻S&⟩#e+

Try it online!

-2 thanks to Arnauld!

1⟨	      ⟩#	% Find the first 1 positive integers n where:
  +:			% b + n
    ṗ!			% is not prime
	    S&		% and is coprime with
      ¤@3*@⁻		% b^3 - b, the product of b-1,b,b+1
		e+	% and return b + n

Answer 4

Husk, 13 bytes

ḟȯ≥3Λ`%-¹^3¹p

Try it online!

Explanation

ḟȯ≥3Λ`%-¹^3¹p   Input is a number b.
ḟ               Find first number ≥b that satisfies:
 ȯ              Composition of 3 functions:
                 Argument is a number n.
            p    1) Prime factors of n (with repetitions).
    Λ            2) All of them satisfy this:
           ¹      b
         ^3       cubed
       -¹         minus b
     `%           modulo the prime (is nonzero).
                  Λ returns either 0 or length+1.
  ≥3             3) Is at least 3.
                  This means n has at least 2 prime factors and none of them divide b^3-b = b*(b+1)*(b-1).

Answer 5

Jelly, 15 bytes

’r‘Ɗg’;Ẓ}E
ç@1#

Try it online!

How it works

’r‘Ɗg’;Ẓ}E - Helper link. Takes b on the left and n on the right
   Ɗ       - Run the previous 3 commands over b:
’          -   Yield b-1
  ‘        -   Yield b+1
 r         -   Yield [b-1, b, b+1]
    g      - Take the GCD between each of these and n
     ’     - Decrement, yielding 0 for co-primes
       Ẓ}  - Is n prime?
      ;    - Concatenate to the list of decremented GCDs
         E - Are they all equal i.e. do they all equal 0?

ç@1# - Main link. Takes b on the left
  1# - Count up from b and return the first integer, n, which is true when: 
ç@   -   run through the helper link with b on the left and n on the right

Answer 6

Scala, 97 96 91 bytes

b=>{def g(i:Int):Int=if(BigInt(b*b*b-b).gcd(i)>1|2.to(i-1).forall(i%_>0))g(i+1)else i
g(b)}

Try it online!

• Thanks to Sisyphus for -1!
• Thanks to user for -5!

Answer 7

Husk, ¹⁸ 17 bytes

ḟ(EM⌋m+¹ṡ1)fo¬ṗ↓N

Try it online! or Verify all test cases

-1 byte after rearranging stuff.

Explanation

ḟ(EM⌋m+¹ṡ1)fo¬ṗ↓N
               ↓N drop first b elements from natural numbers.
           fo¬ṗ   filter out primes
ḟ                 get first element which satisfies the following:
 (        )       co-prime check
        ṡ1        range -1..1
     m+¹          add each to b
   M⌋             GCD of each and b
  E               are all equal?

Answer 8

Brachylog, ²² 16 bytes

-6 thanks to Zgarb

^₃;?-ḋF&<.ḋṀ;Fx×

Try it online!

• ^₃;?-ḋF: all the prime factors of B^3-B
• &<.: the output N is greater than B
• ḋṀ: N's prime factors are at least 2
• ;Fx×: and the product of the prime factors without the ones in F unifies with the output N.

Answer 9

Jelly, 13 bytes

’r‘²Pg€ƊỤẒÞḊḢ

A monadic Link accepting an integer, \$b\$, which yields the first integer that "looks prime but isn't".

Try it online! (Too inefficient for even quite small inputs due to golfing.)

How?

This is really just a golfed version of this 15 byter which is not so ridiculously inefficient: ’r‘ṀÆn²g€ƲỤẒÞḊḢ.

’r‘²Pg€ƊỤẒÞḊḢ - Link: b
’             - decrement -> b-1
  ‘           - increment -> b+1
 r            - inclusive range -> [b-1, b, b+1]
       Ɗ      - last three links as a monad:
   ²          -   square -> [(b-1)², b², (b+1)²]
    P         -   product -> (b(b-1)(b+1))²
                  (this is always greater than ṀÆn²
                     - the square of the next prime above b+1
                   and saves us two precious bytes)
      €       -   for each (v in [1..(b(b-1)(b+1))²]:
     g        -     greatest-common-divisor (between v and each of [b-1, b, b+1])
        Ụ     - grade-up -> 1-based indices sorted by the values at those positions
          Þ   - sort by:
         Ẓ    -   is prime?
           Ḋ  - dequeue (since 1 gets GCDs [1,1,1] so it also looks prime and isn't prime)
            Ḣ - head -> the smallest number that looks prime and isn't prime

Answer 10

Python 3.8, 115 98 89 bytes

Saved a whopping 17 bytes thanks to the man himself Arnauld!!!

f=lambda b,m=9:(m>b)*(perm(m-1)**2%m!=1)*m*(gcd(b**3-b,m)<2)or f(b,m+1)
from math import*

Try it online!

Explanation

f=lambda  b                       # recursive function taking b  
           ,m=9                   # init possible answer to largest single  
                                  # digit (of which none of them can be  
                                  # the solution because they're either  
                                  # prime or divisible by 2 or 3)  
               :                  # the start of a chain of logical  
                                  # tests, if any of them are False the  
                                  # chain will be 0 invoking recursion  
    (m>b)*                        # first one makes sure m is >= b + 1  
      (perm(m-1)**2%m!=1)*        # second tests that m isn't prime using  
                                  # one of xnor's tricks 
        *(math.gcd(b**3-b,m)<2)   # third tests that m is coprime with  
                                  # (b - 1)*b*(b + 1) == b**3 - b  
            *m                    # if all this is True return m  
               or f(b,m+1)        # otherwise try m + 1

Answer 11

Japt, 16 bytes

@Jõ+U ejX «Xj}aU

Try it or run all test cases

@Jõ+U ejX «Xj}aU     :Implicit input of integer U
@                    :Function taking an integer X as argument
 J                   :  -1
  õ                  :  Range [-1,1]
   +U                :  Add U to each
      e              :  All
       jX            :    Co-prime with X
          «          :  Logical AND with the boolean negation of
           Xj        :  Is X prime?
             }       :End function
              aU     :Starting from U, get the first X that returns true

Answer 12

Retina 0.8.2, 58 bytes

.+
$*11¶$&$*
+`^(11+)\1*1?1?¶\1+$|¶(?!(11+)\2+$)
$&1
r`1\G

Try it online! Link includes test cases. Explanation:

.+
$*11¶$&$*

Convert b to unary, and make a copy as b+1, which will be used for GCD testing.

+`^(11+)\1*1?1?¶\1+$|¶(?!(11+)\2+$)
$&1

Keep incrementing the result while it's prime or shares a common factor with either b+1, b or b-1.

r`1\G

Convert the result back to decimal.

Answer 13

Stax, 12 bytes

öα•○¼¿¼╓♫├û•

Run and debug it

Answer 14

C (gcc), 87 86 84 bytes

Saved a byte thanks to the man himself Arnauld!!!

i;q;p;m;f(b){for(p=m=b;p|!q;++m)for(q=p=i=1;++i<m;)q=m%i<1?p=0,q&&b*~-b*~b%i:q;--m;}

Try it online!

Port of my Python answer.

Answer 15

Python 3, 81 bytes

f=lambda b,k=1,p=1:(k<b)|p%k|math.gcd(b**3-b,k)-1and f(b,k+1,p*k)or k
import math

Try it online!

---

Uses xnor's corollary to Wilson's theorem. I still find it unbelievable that the shortest way to test for coprimality is import math;math.gcd(x,y)<2, but I couldn't find a shorter way.

-2 due to xnor, since we only need the regular factorial here (instead of factorial squared). The special case k=4 is taken care of by the other conditions.

Answer 16

05AB1E, 15 14 bytes

∞+.ΔαD3mαy¿yp+

Inspired by @Giuseppe's Gaia answer, so make sure to upvote him as well!

Try it online or verify all test cases.

Explanation:

∞            # Push an infinite positive list: [1,2,3,...]
 +           # Add the (implicit) input `n` to each: [n+1,n+2,n+3,...]
  .Δ         # Find the first `n+b` which is truthy for:
    α        #  Take the absolute difference with the (implicit) input: [1,2,3,...]
     D       #  Duplicate this `b`
      3m     #  Cube it: b³
        α    #  Take the absolute difference with the `b` we've duplicated: |b-b³|
         y¿  #  Get the greatest common divisor with the current `b+n`: gcd(|b-b³|,b+n)
    yp       #  Check whether `b+n` is a prime number (1 if prime; 0 if not)
    +        #  Add them together: gcd(|b-b³|,b+n)+isPrime(b+n)
             #  (NOTE: only 1 is truthy in 05AB1E)
             # (after which the result is output implicitly as result)

Answer 17

R, 100 81 73 72 bytes

Edit1: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks

Edit2: -8 bytes, and then -1 more byte thanks to Giuseppe

f=function(b,n=b)`if`(sum(a<-!n%%2:n)>1&all(!a|(b^3-b)%%2:n),n,f(b,n+1))

Try it online!

Sadly, although checking for primality by counting divisors and checking for co-primality by counting shared divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...

Thanks to Giuseppe for ruthlessly pruning all the unneccessary variables, parentheses, square-brackets and so on...

How? (code before golfing by Giuseppe)

f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)                                   

Answer 18

Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Sisyphus's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Much faster 38-byte version which performs separate coprimaility testing on \$ b - 1 \$, \$ b \$ and \$ b + 1 \$:

Ｎθ≔Ｅ³Ｘ²⊖⁺θιηＷ∨﹪Π…¹θθ⊙η﹪÷Ｘκθ⊖κ⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code.

Answer 19

Python 3, 145 143 137 bytes

from math import*
p=lambda b,h=2,c=inf:h>c and c or p(b,h+1,([h*i for i in range(2,h+1)if 2>gcd(h*i,b**3-b)and h*i<c and b<h*i]or[c])[0])

Try it online!

• -2 bytes by reformatting the condition in the list comprehension and removing an unnecessary space.
• -6 bytes from removing a special case when c is 0 by making it default to math.inf instead

Wanted to test how a solution that doesn't involve prime checking might fare, just out of curiosity. Worse than the competition, it seems. Oh well, at least I had fun.

Works by generating all composite numbers. On each pass, we generate some numbers that are definitely composite, then update our best guess (which we'll call \$x\$) to be the smallest number we find that's between \$b\$ and \$x\$ and also coprime with \$b^3 - b\$ - if we didn't end up generating a number like that, we keep our existing \$x\$. Eventually we reach a point where we know we'll no longer generate any numbers that are below our current \$x\$, which means \$x\$ must be the correct answer.

Ungolfed

from math import gcd, inf

def pseudoprime(base, high=2, candidate=inf):
    if high > candidate:
        # We can no longer find anything that's small enough to care about
        return candidate
    else:
        valid_multiples = [high * i for i in range(2, high+1) if # Generate all multiples of "high", then filter them
            base < high * i and # Exclude single-digit numbers
            math.gcd(high * i, base ** 3 - base) < 2 and # Check for coprimality
            high * i < candidate # Make sure it's not bigger than our best guess, assuming we've found one
        ]
        if valid_multiples:
            return pseudoprime(base, high + 1, valid_multiples[0])
        else:
            return pseudoprime(base, high + 1, candidate)

Answer 20

Java 8, 106 105 104 100 bytes

n->{for(int b=0,p,g,i;;){for(g=p=++n;n%--p>0;);for(i=++b*b*b-b;i>0;)i=g%(g=i);if(p>1&g<2)return n;}}

-1 byte thanks to @ceilingcat.

Try it online.

Explanation:

n->{                 // Method with integer as both parameter and return-type
  for(int b=0,       //  Start integer `b` at 0
          p,         //  Temp-integer to check for primes
          g,i;       //  Temp-integers to check for the gcd
      ;){            //  Loop indefinitely:
    for(g=p=++n;     //   Increase n by 1 first with `++n`
                     //   And then set both g and p to this new n
        n%--p>0;);   //   Decrease p by 1 before every iteration with `--p`
                     //   and continue looping as long as n is NOT divisible by p
    for(i=++b*b*b-b; //   Then increase b by 1 first with `++b`
                     //   And set i to b³-b
        i>0;)        //   Loop as long as i is still positive:
      i=g%(g=i);     //    First set g to i
                     //    And then set i to old_g modulo-new_g
    if(p>1           //   If `p` is larger than 1 (this means it's NOT a prime)
       &g<2)         //   and the greatest common divisor is 1:
      return n;}}    //    Return the modified n as result