Legendre's (Unsolved) Conjecture

Question

Legendre's Conjecture is an unproven statement regarding the distribution of prime numbers; it asserts there is at least one prime number in the interval \$(n^2,(n+1)^2)\$ for all natural \$n\$.

The Challenge

Make a program which only halts if Legendre's conjecture is false. Equivalently, the program will halt if there exists \$n\$ which disproves the conjecture.

Rules

• This is code-golf so the shortest program in bytes wins.

• No input shall be taken by the program.

• The program only needs to halt or not halt in theory; memory and time constraints shall be ignored.

• One may use methods other than checking every \$n\$ if they can prove their program will still only halt if Legendre's conjecture is false.

Answer 1

JavaScript (Node.js),  49  47 bytes

A full program that stops only if there's some \$n\ge2\$ such that all \$x\in[(n-1)^2..n^2]\$ are composite.

for(x=n=2n;x-n*n;d?0:x=n*n++)for(d=x++;x%d--;);

Try it online!

Commented

for(                  // outer loop:
  x = n = 2n;         //   start with x = n = 2
  x - n * n;          //   stop if x = n²
  d ? 0 : x = n * n++ //   if d = 0, set x = n² and increment n
)                     //
  for(                //   inner loop:
    d = x++;          //     start with d = x and increment x
    x % d--;          //     stop if d divides x; decrement d
  );                  //     if we end up with d = 0, then x is prime

Answer 2

Raku, 34 bytes

1...{is-prime none $_²..($_+1)²}

Try it online!

Counts upwards until it finds a number where none of the given range are prime.

Answer 3

05AB1E, 17 11 bytes

∞.∆DnÅNs>n@

Try it online!

-6 bytes thanks to @ovs

Explained

∞.∆DnÅNs>n@ 
∞                   Push an infinite list
 .∆                 Find the first item in that list that:
   D                  
       s>n              (n+1)^2 is
          @             larger or equal than
    nÅN                 the next prime from n^2

Answer 4

R, 60 55 54 bytes

Edit: -1 byte thanks to Robin Ryder

while(sd(sapply(lapply(T^2:(T=T+1)^2,`%%`,2:T),all)))T

Try it online!, or, since it's rather boring to run a program that (probably) never halts and produces no output, try a slightly longer version (exchanging n=sum( for any() that prints n and the number of primes in the interval (n-1)^2..n^2 for each n>2.

Commented original version:

while(                                  # keep looping as long as...
    any(                                # there is at least one true result among...
        sapply(T^2:(T=T+1)^2,           # the loop from T^2 up to (T+1)^2
                                        # (& use this opportunity to increment T)...
            function(x)all(x%%(2:T))    # tested for primality by checking that all 
                                        # modulo divisions from 2..T have a non-zero result
        )
    )   
){}

Answer 5

Jelly, 7 bytes

‘ɼ²ÆCµƬ

A niladic Link which, if the conjecture is False, will yield a list of counts of primes between \$2\$ and \$k^2\$ where \$k\$ is the zero-based index of the element (although the zero-indexed element will be None rather than 0). The final value in the list will be the count of primes between \$2\$ and \$n^2\$ (the next term would be the count between \$2\$ and \$(n+1)^2\$, and would be equal to that).

Note: Since this uses one of Jelly's prime related built-ins, this is subject to the underlying implementation's (sympy's) primality check, and help(sympy.ntheory.isprime) states ...[If] the number is larger than 2^64, a strong BPSW test is performed. While this is a probable prime test and we believe counterexamples exist, there are no known counterexamples).

Try it online!

How?

Collects the counts of primes between \$2\$ and \$(k+1)^2\$ starting with \$k=0\$ until repetition would be present by appending the result. This implies there are no new primes between \$(k+1)^2\$ and \$(k+2)^2\$ (i.e. \$n^2\$ and \$(n+1)^2\$). The final result, if any, will have a leading None - the initial input to the function that performs the counting.

‘ɼ²ÆCµƬ - Link: no arguments
      Ƭ - collect up (the initial input (None) and each result) until repetition:
     µ  -   apply the monadic chain - i.e. f(x=previousResult):
 ɼ      -     recall (k) from the register (initially 0), apply, store back, and yield:
‘       -     increment -> k+1
  ²     -     square -> (k+1)²
   ÆC   -     count primes from 2 to (k+1)² inclusive

Answer 6

Jelly, 9 bytes

²+æR$Ṇµ2#

Try it online!

-1 byte thanks to caird coinheringaahing
-1 byte thanks to Jonathan Allan

Answer 7

Retina 0.8.2, 67 62 bytes

_¶¶_
{`(_+)¶_*(¶_+)
_$1$2$2$1$1_
¶(_+)¶(?!_*(?!(__+)\2+$)\1)

Don't try it online! Instead, try a Retina 1 version which takes as input the number of iterations. Explanation:

_¶¶_

The working area contains n+1, n² and (n+1)², where n starts at 0 but is immediately incremented (saving 5 bytes over my previous answer which started with n=1).

{`

Repeat until Legendre's conjecture is false.

(_+)¶_*(¶_+)
_$1$2$2$1$1_

Increment n; the old (n+1)² becomes the new n² and the new (n+1)² is calculated.

¶(_+)¶(?!_*(?!(__+)\2+$)\1)

If none of the numbers between n² and (n+1)² are prime, then delete n² and (n+1)², which causes the loop to terminate, as neither stage can now match.

Answer 8

C (gcc), 194 180 169 bytes

#include<gmp.h>
main(){mpz_t n,l,h;for(mpz_init_set_ui(n,1),mpz_init(l),mpz_init(h);mpz_mul(l,n,n),mpz_add_ui(n,n,1),mpz_mul(h,n,n),mpz_nextprime(l,l),mpz_cmp(l,h)<1;);}

Try it online!

-14 bytes thanks to ceilingcat!

-11 bytes again thanks to ceilingcat!

To test, here's one that outputs the prime in each range:

C (gcc), 352 bytes

 #include<stdio.h>
#include<gmp.h>
#define m(X) mpz_##X
main(){m(t) n,l,h;m(init_set_ui)(n,1);m(init)(l);m(init)(h);for(;;){m(mul)(l,n,n);m(add_ui)(n,n,1);m(mul)(h,n,n);
 printf("In (");
 m(out_str)(stdout,10,l);
 printf(", ");
 m(out_str)(stdout,10,h);
 printf("): ");
m(nextprime)(l,l);if(m(cmp)(l,h)>0)return;
 m(out_str)(stdout,10,l);
 puts("");
}}

Try it online!

Note: This is probably very optimizable. When certain users inevitably improve the solution, I'll update. ;)

Answer 9

Python 2, 45 bytes

i=k=P=1
while~i*~i-k:P*=k;k+=1;i+=i*i<k>0<P%k

Try it online!

Here's a demonstration of the code halting if we modify it to claim that all of range(36,49) is non-prime.

We use the Wilson's Theorem prime generator. We count up potential primes k, and the condition P%k>0 is met exactly for primes. Except, we use P*=k instead of P*=k*k which makes k=4 also be called prime, but that doesn't matter here.

Here's how we halt if there's not prime between two consecutive squares. The value i tries to track the smallest number so that the square i*i is at least the current potential prime k. Every time we hit a prime k, we update i by checking if i*i<k, and if so, increment i. This makes it so that k<=i*i afterwards. But, if there is no prime between i**2 and (i+1)**2, then i won't update in that interval, and k will reach all the way to (i+1)**2. The while loop conditions checks for this (writing ~i*~i for (i+1)**2) and terminates the loop if it happens.

---

73 bytes

n=2
while any(all(k%i for i in range(2,k))for k in range(n*n,~n*~n)):n+=1

Try it online!

A more direct approach of checking that each interval between squares contains a prime, based on the solution of Manish Kundu

Answer 10

05AB1E, 11 bytes

First attempt:

[N>nÅMNn‹#]

Fixed (after @ovs notes):

[NÌnÅMN>n‹#

Explanation:

[NÌnÅMN>n‹# 
[                     Infinite Loop
 N                    Current loop index (starts from 0 to Infinity)
  Ì                   add 2 ( we want to start from N=1 instead of N=0)
   n                  Squaring - (N+1)**2
    ÅM                Find the previous prime. Highest prime less than (N+1)**2
      N>               Push Current loop index + 1
        n              Squaring - N**2
         ‹             Does  Highest prime less than (N+1)**2 < N**2  ?
          #            If true, break the loop

Try it online!

Answer 11

Io, 124 bytes

method(x :=1;loop(s :=0;for(i,x*x,x*(x+2)+1,if(Range 1 to(i)asList select(o,i%o<1)size<3,s :=1;break));if(s<1,break);x=x+1))

Try it online!

Answer 12

MATL, 11 10 bytes

`@U_Yq@QU<

Try it online!

-1 byte thanks to Luis Mendo. Otherwise, pretty straightforward.

`  % Start a loop
@  % Push loop index (n)
U  % square
_Yq % Get next prime
@QU % Loop index plus one, squared
<   % Continue loop if the prime is smaller than this.

Answer 13

><>, 51 bytes

/;?)*:&+1}::&<
\~:*>2:}}:}=?^:}}:}$%?2~1+l3+1.15a&4

Try it online!

Try it online! (2) shows the program terminating if starting above last prime in first range.

Explanation

/;?)*:&+1}::&<
\~:*

Prime branch, checks if first found prime is below \$(n+1)^2\$ and then increments \$n\$ and jumps up to the next range, otherwise terminates

    >2:}}:}=?^

Ends trial division if we have found a prime

              :}}:}$%?2~1+l3+1.

Branch-free trial division

/
\                             .15a&4

Initial values, starts at 10 trying to find primes below \$4^2\$

Answer 14

Python 3, 107 99 88 86 90 86 79 bytes

n=2
while n:n+=0<sum(min(i%j for j in range(2,i))for i in range(n*n,~n*~n))or-n

Try it online!

Initially, n=2. Then it checks if any of the 2n numbers between n^2 and (n+1)^2 are prime or not. If yes, then n is incremented, otherwise n is set to 0 and the loop terminates.

-7 bytes thanks to Jo King

Answer 15

Wolfram Language (Mathematica), 30 bytes

For[n=1,NextPrime[n++^2]<n^2,]

Try it online!

Special thankks to @att for saving 9 bytes

Answer 16

C (gcc), 88 84 bytes

Saved 4 bytes thanks to ceilingcat!!!

q;h;i;j;f(n){for(h=n=1;h;++n)for(h=0,i=n*n;q=j=++i<~n*~n;h|=q)for(;++j<i;)q=q&&i%j;}

Try it online!

Will run forever on an infinite machine (with new infinity-bit int types!) so long as there's always a prime number in the interval \$(n^2,(n+1)^2)\$.

Here's the same code modified to print the primes as they are found:

C (gcc), 161 bytes

q;h;i;j;f(n){for(h=n=1;h;++n)for(h=0,i=n*n;q=j=++i<~n*~n;h|=q){for(;++j<i;)q=q&&i%j;if(q)printf("Found prime %d in the interval (%d, %d)\n",j,n*n,(n+1)*(n+1));}}

Try it online!

Answer 17

Japt, 12 11 bytes bytes

_²ôZÑ dj}f1

Test it (May cause your browser to explode!)

_               :Function taking an integer Z as argument
 ²              :  Z squared
   ZÑ           :  Z times 2
  ô             :  Range [Z²,Z²+Z*2]
      d         :  Any
       j        :    Prime
        }       :End function
         f1     :Return the first Z≥1 that returns false

Answer 18

Brachylog, 12 bytes

+₁;?≜^₂ᵐ⟧₂ṗⁿ

Try it online!

How it works

Brachylog will try to find a value N that fulfills the following program:

+₁;?≜^₂ᵐ⟧₂ṗⁿ
+₁            N+1
  ;?          [N+1, N]
    ≜         Try possible numbers, e.g. [5, 4]
     ^₂ᵐ      Map square [25, 16]
        ⟧₂    Range from min to max
          ṗⁿ  Succeeds if there is no prime in this range

Answer 19

Scala, ^{98 93 91} 87 bytes

-7 bytes thanks to Dominic Van Essen

Stream.iterate(2:BigInt)(_+1)find(n=>n*n to n*n+2*n forall(x=>n to(2,-1)exists(x%_<1)))

Without BigInt, it could be made a few bytes shorter, but then it would overflow.

It first creates an infinite list starting at 2, then tries to find an n in that list such that every number x in the range n^2 to (n+1)^2 is composite.

Try it in Scastie