26
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ @roblogic The conjecture means "between" as the open interval (n^2,(n+1)^2), I will edit to clarify \$\endgroup\$ – golf69 Jul 31 at 6:25
  • 1
    \$\begingroup\$ The definition of "natural numbers" is ambiguous between "positive integers" and "nonnegative integers"; can you use "positive integers" instead? \$\endgroup\$ – L. F. Jul 31 at 15:52
  • 1
    \$\begingroup\$ 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? =) \$\endgroup\$ – Cireo Aug 1 at 0:08
  • 6
    \$\begingroup\$ @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 \$\endgroup\$ – golf69 Aug 1 at 0:16
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – L. F. Aug 1 at 5:19

19 Answers 19

12
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 8
    \$\begingroup\$ Upvoting cause it is literally the only answer i can read lol \$\endgroup\$ – Macindows Jul 31 at 16:49
8
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Instead of finding a single prime, you can just check all numbers in the range with Ÿp_W. \$\endgroup\$ – ovs Jul 31 at 8:18
  • 2
    \$\begingroup\$ And I think this 11-byter should work, but for some reason it outputs the result of every iteration. \$\endgroup\$ – ovs Jul 31 at 9:09
  • \$\begingroup\$ I don't think output is prohibited, it just isn't required. \$\endgroup\$ – Dominic van Essen Jul 31 at 10:14
  • \$\begingroup\$ @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 \$\endgroup\$ – Kevin Cruijssen Aug 4 at 7:50
  • \$\begingroup\$ @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. \$\endgroup\$ – ovs Aug 4 at 8:11
7
\$\begingroup\$

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
        )
    )   
){}
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Robin Ryder Jul 31 at 12:06
7
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Jelly, 9 bytes

²+æR$Ṇµ2#

Try it online!

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 10 bytes \$\endgroup\$ – caird coinheringaahing Jul 31 at 11:23
  • \$\begingroup\$ 9 bytes \$\endgroup\$ – Jonathan Allan Jul 31 at 12:54
  • \$\begingroup\$ @cairdcoinheringaahing thanks I tried using that on a different algorithm and it didn't work and I forgot to retry lol \$\endgroup\$ – HyperNeutrino Jul 31 at 15:11
  • \$\begingroup\$ @JonathanAllan thanks! \$\endgroup\$ – HyperNeutrino Jul 31 at 15:11
5
\$\begingroup\$

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, 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 and the new (n+1)² is calculated.

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

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

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – LambdaBeta Jul 31 at 17:32
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This cannot halt because there is no prime below 1: tio.run/##yy9OTMpM/f/f8HCr7///AA \$\endgroup\$ – ovs Jul 31 at 16:23
  • \$\begingroup\$ Interesting... Well I can increment the N so it will actually start from N=1. I'll edit it soon. \$\endgroup\$ – SomoKRoceS Jul 31 at 17:46
  • 1
    \$\begingroup\$ You don't need the trailing ], so you can still do it in 11 bytes. \$\endgroup\$ – ovs Jul 31 at 17:55
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Does (x+1)^2 not work in Io? It doesn't seem to give an error... \$\endgroup\$ – Dominic van Essen Jul 31 at 15:52
  • 1
    \$\begingroup\$ @DominicvanEssen ^ is bitwise xor in Io. To actually do exponentiation, you have to do: (x+1)pow(2). \$\endgroup\$ – user96495 Jul 31 at 23:16
  • \$\begingroup\$ Got it. Thanks for the mini Io lesson! \$\endgroup\$ – Dominic van Essen Aug 1 at 8:47
3
\$\begingroup\$

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.
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think you need to count the n=2 for the code's length. \$\endgroup\$ – xnor Aug 2 at 6:48
  • \$\begingroup\$ @xnor I wasn't aware, thanks for pointing it out. Updated. \$\endgroup\$ – Manish Kundu Aug 2 at 8:05
  • \$\begingroup\$ @JoKing thanks ^^ \$\endgroup\$ – Manish Kundu Aug 20 at 11:37
  • \$\begingroup\$ You can save 6 bytes by directly checking it in the while loop's condition. \$\endgroup\$ – user Nov 10 at 20:04
2
\$\begingroup\$

Wolfram Language (Mathematica), 30 bytes

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

Try it online!

Special thankks to @att for saving 9 bytes

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – att Jul 31 at 17:39
2
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Dominic van Essen Jul 31 at 15:16
  • \$\begingroup\$ @DominicvanEssen You were right! Ignore my previous comment, I thought you said x to 2 instead of n to 2 \$\endgroup\$ – user Jul 31 at 15:29
  • 2
    \$\begingroup\$ 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...) \$\endgroup\$ – Dominic van Essen Jul 31 at 15:33
  • 3
    \$\begingroup\$ @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) \$\endgroup\$ – user Jul 31 at 15:37
  • 2
    \$\begingroup\$ n pow 2 -> n*n and !=0 -> >0 to save 5 more bananas. \$\endgroup\$ – Dominic van Essen Jul 31 at 16:07
1
\$\begingroup\$

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
| improve this answer | |
\$\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.