Legendre's Conjecture Explorer

Verifying primes between n² and (n+1)²

Overview

Legendre's Conjecture Explorer verifies that there is always at least one prime number between n² and (n+1)² for any positive integer n. All prime checking and square calculations are performed using Romasm assembly.

Legendre's Conjecture

What is it?

Legendre's Conjecture states that for every positive integer n, there exists at least one prime number between n² and (n+1)².

Examples:

  • n=1: Between 1²=1 and 2²=4, we have primes: 2, 3
  • n=2: Between 2²=4 and 3²=9, we have primes: 5, 7
  • n=3: Between 3²=9 and 4²=16, we have primes: 11, 13
  • n=4: Between 4²=16 and 5²=25, we have primes: 17, 19, 23

Status: Unproven, but verified for very large values of n.

Romasm Implementation

The explorer uses Romasm assembly to calculate squares and check for primes:

; Check Legendre's Conjecture for n
; Input: R0 = n
; Output: List of primes between n² and (n+1)²

; Calculate n²
LOAD R1, R0
MUL R1, R0       ; R1 = n²

; Calculate (n+1)²
LOAD R2, R0
INC R2           ; R2 = n+1
LOAD R3, R2
MUL R3, R2       ; R3 = (n+1)²

; Search for primes in range [n²+1, (n+1)²-1]
LOAD R4, R1
INC R4           ; Start from n²+1

search_loop:
  INC R4
  CMP R4, R3
  JGE done       ; If R4 >= (n+1)², done
  
  ; Check if R4 is prime
  LOAD R0, R4
  CALL is_prime
  CMP R0, 1
  JEQ found_prime  ; If prime, add to list
  
  JMP search_loop

found_prime:
  PRINT R4       ; Print the prime
  JMP search_loop

done:
  RET

Using the Explorer

  1. Enter a value for n
  2. Click "Verify Conjecture"
  3. View all primes found between n² and (n+1)²
  4. See verification that at least one prime exists

Related Documentation