Legendre's (Unsolved) Conjecture

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

• @roblogic The conjecture means "between" as the open interval (n^2,(n+1)^2), I will edit to clarify – golf69 Jul 31 at 6:25
• The definition of "natural numbers" is ambiguous between "positive integers" and "nonnegative integers"; can you use "positive integers" instead? – L. F. Jul 31 at 15:52
• Based on a careful reading we could just submit a program that waits for input if we include a proof of the conjecture as a comment, yes? =) – Cireo Aug 1 at 0:08
• @Cireo Yes, and that was intentional; tbh if I motivated a proof of a >200yr old problem I would be ecstatic so you can go right ahead – golf69 Aug 1 at 0:16
• @ManfP In some parts of the world, "natural number" unambiguously includes 0. It's clear unless the reader isn't aware of the intended definition at all. Not a big deal, but I still think avoiding the term is better. – L. F. Aug 1 at 5:19

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

• Upvoting cause it is literally the only answer i can read lol – Macindows Jul 31 at 16:49

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.

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

• Instead of finding a single prime, you can just check all numbers in the range with Ÿp_W. – ovs Jul 31 at 8:18
• And I think this 11-byter should work, but for some reason it outputs the result of every iteration. – ovs Jul 31 at 9:09
• I don't think output is prohibited, it just isn't required. – Dominic van Essen Jul 31 at 10:14
• @ovs You're using the wrong ∆. The one you use has codepoint 8710, while the one you should use from 05AB1E's codepage is Δ (codepoint 916). The reason it outputs every iteration is because the . and ∆ in your 11-byter act as no-ops, so it applies all the other commands on the entire infinite list (implicitly mapping those other builtins). You confused me for a moment with your answer, since even the basic ∞.∆ (∞.Δ) wasn't outputting 1, even though that worked before my vacation. xD – Kevin Cruijssen Aug 4 at 7:50
• @KevinCruijssen thanks for looking into this. I guess should just copy commands from the documentation instead of trying to type 05AB1E code with my keyboard. – ovs Aug 4 at 8:11

R, 6055 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
)
)
){}

• any could be sdfor -1 byte. You are then checking whether the vector contains (at least) 2 different values, i.e. both TRUEs and FALSEs. Since (T+1)^2 is necessarily a composite number, the standard deviation will be non-zero iff there is at least one prime number in the interval. – Robin Ryder Jul 31 at 12:06

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


²+æR$Ṇµ2#  Try it online! -1 byte thanks to caird coinheringaahing -1 byte thanks to Jonathan Allan • 10 bytes – caird coinheringaahing Jul 31 at 11:23 • 9 bytes – Jonathan Allan Jul 31 at 12:54 • @cairdcoinheringaahing thanks I tried using that on a different algorithm and it didn't work and I forgot to retry lol – HyperNeutrino Jul 31 at 15:11 • @JonathanAllan thanks! – HyperNeutrino Jul 31 at 15:11 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. C (gcc), 194180 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. ;) • Wow, I really didn't put enough effort into that. Missing the for trick is just a "noob" mistake. But actively "optimizing" a prefix with a define that doesn't save any bytes and actually costs bytes is ridiculous! Nice catch! – LambdaBeta Jul 31 at 17:32 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 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! • This cannot halt because there is no prime below 1: tio.run/##yy9OTMpM/f/f8HCr7///AA – ovs Jul 31 at 16:23 • Interesting... Well I can increment the N so it will actually start from N=1. I'll edit it soon. – SomoKRoceS Jul 31 at 17:46 • You don't need the trailing ], so you can still do it in 11 bytes. – ovs Jul 31 at 17:55 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! • Does (x+1)^2 not work in Io? It doesn't seem to give an error... – Dominic van Essen Jul 31 at 15:52 • @DominicvanEssen ^ is bitwise xor in Io. To actually do exponentiation, you have to do: (x+1)pow(2). – user96495 Jul 31 at 23:16 • Got it. Thanks for the mini Io lesson! – Dominic van Essen Aug 1 at 8:47 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.  Python 3, 1079988869086 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 • I think you need to count the n=2 for the code's length. – xnor Aug 2 at 6:48 • @xnor I wasn't aware, thanks for pointing it out. Updated. – Manish Kundu Aug 2 at 8:05 • @JoKing thanks ^^ – Manish Kundu Aug 20 at 11:37 • You can save 6 bytes by directly checking it in the while loop's condition. – user Nov 10 at 20:04 Wolfram Language (Mathematica), 30 bytes For[n=1,NextPrime[n++^2]<n^2,]  Try it online! Special thankks to @att for saving 9 bytes • n++ evaluates first, so you shouldn't be adding n+1. Also, For with a null incr still saves one byte over While. 30 bytes – att Jul 31 at 17:39 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! 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  ><>, 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\$$

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

• I can't read or write Scala, but wouldn't you save 2 bytes (and make the function much more efficient) if for each x you check for division in the range n to 2 instead of x/2 to 2? – Dominic van Essen Jul 31 at 15:16
• @DominicvanEssen You were right! Ignore my previous comment, I thought you said x to 2 instead of n to 2 – user Jul 31 at 15:29
• I'm probably no smarter than a monkey at a keyboard... but this seems to run without error... (sorry if this is a waste of time: but it's fun to try-out new languages without bothering to try to learn them...) – Dominic van Essen Jul 31 at 15:33
• @DominicvanEssen You know what they say - "If you put a million monkeys at a million keyboards, one of them will eventually write a Java program. The rest of them will write Perl programs." You must be the supermonkey that evolved from a Java-writing monkey to a Scala-writing monkey :) (no offense to Perl programmers intended) – user Jul 31 at 15:37
• n pow 2 -> n*n and !=0 -> >0 to save 5 more bananas. – Dominic van Essen Jul 31 at 16:07

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