Wiki Agenda Contact Version française

Infinity of primes

A constructive proof that there is an infinity of primes


Authors: Jean-Christophe Filliâtre

Topics: Mathematics

Tools: Why3

see also the index (by topic, by tool, by reference, by year)


A constructive proof that there is an infinity of primes

The idea is to build the sequence a(O) = 1 a(n) = a(n-1) * (a(n-1) + 1) and to show that a(n) has (at least) n distinct prime factors. See http://oeis.org/A007018

Author: Jean-Christophe FilliĆ¢tre (CNRS)

use int.ComputerDivision
use number.Divisibility
use number.Prime

let lemma prime_factor (n: int) : (p: int)
  requires { n >= 2 }
  ensures  { prime p }
  ensures  { divides p n }
= for p = 2 to n do
    invariant { forall d. 2 <= d < p -> not (divides d n) }
    if mod n p = 0 then return p
  done;
  return n

use set.Fset

let lemma infinity_of_primes (n: int) : (s: fset int)
  requires { n >= 0 }
  ensures  { cardinal s = n }
  ensures  { forall k. mem k s -> prime k }
= let ref s = empty in
  let ref x = 1 in
  for i = 0 to n-1 do
    invariant { x >= 1 }
    invariant { cardinal s = i }
    invariant { forall k. mem k s -> prime k }
    invariant { forall k. mem k s -> divides k x }
    let p = prime_factor (x+1) in
    x <- x * (x+1);
    s <- add p s
  done;
  s

download ZIP archive

Why3 Proof Results for Project "infinity_of_primes"

Theory "infinity_of_primes.Top": fully verified

ObligationsAlt-Ergo 2.4.0CVC4 1.7Z3 4.8.6
VC for prime_factor---------
split_vc
loop invariant init---0.04---
precondition---0.04---
postcondition---0.09---
postcondition---0.04---
loop invariant preservation---0.05---
postcondition---0.03---
postcondition---0.04---
out of loop bounds---0.03---
VC for infinity_of_primes---------
split_vc
loop invariant init---0.04---
loop invariant init---0.06---
loop invariant init---0.05---
loop invariant init---0.06---
precondition---0.05---
loop invariant preservation---0.07---
loop invariant preservation------0.05
loop invariant preservation---0.09---
loop invariant preservation0.05------
postcondition---0.05---
postcondition---0.07---
out of loop bounds---0.04---