31
\$\begingroup\$

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 , 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
\$\endgroup\$
3
  • 8
    \$\begingroup\$ It's too bad that this challenge requires finding whether numbers are actually prime, which means golfing yet another primality check in addition to the original definition at the core of the challenge. I get that it's thematic with pseudoprimes, but I was kind-of disappointed when reading a "no not actual primes" challenge and it turned out to have a "but yes actual primes" step. \$\endgroup\$ – xnor Oct 13 '20 at 21:44
  • 2
    \$\begingroup\$ @xnor I normally agree with that, but decided to overlook it because of the theme. I assumed that since nobody else brought it up while the challenge was in the sandbox, other people had the same idea. And besides, I'm pretty sure there is an algorithm for finding these numbers without having to include a primality check - generating all composite numbers is as easy as generating all pairs of integers above two and taking each pair's product, and then you just check those known composites for coprimality with b and b±1 \$\endgroup\$ – Sara J Oct 13 '20 at 23:58
  • \$\begingroup\$ @SaraJ Good point about composite numbers, and in particular that generating them is nicer than generating primes. It is a bit tricky with sorting since you need the composite numbers in ascending order, so it's not enough to do two nested loops. \$\endgroup\$ – xnor Oct 14 '20 at 0:07

20 Answers 20

9
\$\begingroup\$

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!

\$\endgroup\$
1
  • 3
    \$\begingroup\$ This took me a second to validate but it is a really slick way to inline that primality test and the requested check, kudos. \$\endgroup\$ – CR Drost Oct 14 '20 at 19:38
8
\$\begingroup\$

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

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
\$\endgroup\$
2
  • 3
    \$\begingroup\$ I don't know Gaia, but would it be any shorter to compute \$b^3-b\$ instead of \$b(b-1)(b+1)\$? \$\endgroup\$ – Arnauld Oct 13 '20 at 18:04
  • \$\begingroup\$ @Arnauld yes it is, two bytes shorter. Thanks! \$\endgroup\$ – Giuseppe Oct 13 '20 at 18:30
5
\$\begingroup\$

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).
\$\endgroup\$
4
\$\begingroup\$

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

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I don't know Scala, but you should be able to use <2 instead of ==1 for the GCD and <1 instead of ==0 for the prime check. Nice answer! :) \$\endgroup\$ – Sisyphus Oct 14 '20 at 9:15
  • 1
    \$\begingroup\$ Nice trick with BigInt! You can get 91 bytes by rearranging some stuff \$\endgroup\$ – user Oct 14 '20 at 12:48
3
\$\begingroup\$

Husk, 18 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?
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 22 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.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ The first part can be ^₃;?-ḋF \$\endgroup\$ – Zgarb Oct 14 '20 at 17:32
3
\$\begingroup\$

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

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can remove the all() and just do (math.gcd(b**3-b,m)<2). \$\endgroup\$ – Arnauld Oct 13 '20 at 18:16
  • \$\begingroup\$ (So, 98 bytes by re-arranging a bit.) \$\endgroup\$ – Arnauld Oct 13 '20 at 18:17
  • \$\begingroup\$ @Arnauld Beautiful, multiply \$b-1\$, \$b\$, and \$b+1\$ together and test if coprime with m - thanks! :D \$\endgroup\$ – Noodle9 Oct 13 '20 at 18:21
2
\$\begingroup\$

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

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.

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

Stax, 12 bytes

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

Run and debug it

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

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can use b*~-b*~b instead of (b*b*b-b), saving a byte. \$\endgroup\$ – Arnauld Oct 13 '20 at 23:03
  • \$\begingroup\$ @Arnauld That's magic - thanks! :D \$\endgroup\$ – Noodle9 Oct 13 '20 at 23:26
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ It looks like you can get away with p*k instead of p*k*k, since this only makes 4 be called prime, but this is only relevant for b=2 and b=3 for which it's not relatively prime. \$\endgroup\$ – xnor Oct 14 '20 at 2:31
  • \$\begingroup\$ For the gcd test, I had found a trick to write import math;math.gcd(x,y)<2 as 2**(x*y)/~-2**x%~-2**y<1 (for x>1). But it's unlikely to be of use here where one of the arguments is b**3-b. \$\endgroup\$ – xnor Oct 14 '20 at 2:37
  • \$\begingroup\$ Thanks @xnor, that's a good observation. The gcd trick is nice too, even though it doesn't save bytes here - I'll have to squirrel that away in my mental list of 'short ways to do common things in Python'. \$\endgroup\$ – Sisyphus Oct 14 '20 at 4:54
2
\$\begingroup\$

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

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
)                                   
\$\endgroup\$
6
  • \$\begingroup\$ 99 by using outer instead of sapply (with some rearrangement) EDIT: never mind, you've golfed it down quite a bit \$\endgroup\$ – Giuseppe Oct 14 '20 at 13:14
  • \$\begingroup\$ Thanks @Giuseppe! Sadly it's even shorter to just bin the entire sapply/outer and do the calculations separately in separate variables... \$\endgroup\$ – Dominic van Essen Oct 14 '20 at 13:15
  • \$\begingroup\$ In that case 73 bytes \$\endgroup\$ – Giuseppe Oct 14 '20 at 13:19
  • \$\begingroup\$ Thanks very much! I seem to love punctuation... \$\endgroup\$ – Dominic van Essen Oct 14 '20 at 13:29
  • \$\begingroup\$ 72 bytes. I'm pretty sure the all() statement "each integer from 2:n doesn't divide a OR doesn't divide b^3-b" should work. I noted first that any could be substituted in place of sum, and then just tried De Morgan's laws from there. \$\endgroup\$ – Giuseppe Oct 14 '20 at 17:03
2
\$\begingroup\$

Charcoal, 35 bytes

Nθ≔X²⁻Xθ³θηW∨﹪Π…¹θθ﹪÷Xηθ⊖η⊖X²θ≦⊕θIθ

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:

Nθ

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

≔X²⁻Xθ³θη

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

W∨

While either...

﹪Π…¹θθ

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

﹪÷Xηθ⊖η⊖X²θ

... \$ 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 \$.

Iθ

Output the final value of \$ n \$.

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

Nθ≔E³X²⊖⁺θιηW∨﹪Π…¹θθ⊙η﹪÷Xκθ⊖κ⊖X²θ≦⊕θIθ

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

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

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)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Maybe not the shortest, but definitely deserves +1 for effort, though... \$\endgroup\$ – Dominic van Essen Oct 14 '20 at 13:14
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ @ceilingcat Thanks! And your golf made me realize it can be even shorter without the t like this: i=g%(g=i). \$\endgroup\$ – Kevin Cruijssen Oct 14 '20 at 17:51

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.