Package natural-prime-sieve-def: Definition of the sieve of Eratosthenes

Information

name	natural-prime-sieve-def
version	1.9
description	Definition of the sieve of Eratosthenes
author	Joe Hurd <joe@gilith.com>
license	MIT
provenance	HOL Light theory extracted on 2012-06-17
requires	bool list natural natural-prime-stream pair relation
show	Data.Bool Data.List Data.Pair Number.Natural Number.Natural.Prime.Sieve

Files

Package tarball natural-prime-sieve-def-1.9.tgz
Theory file natural-prime-sieve-def.thy (included in the package tarball)

Defined Type Operator

Number
- Natural
  - Prime
    - Sieve
      - sieve

Defined Constants

Number
- Natural
  - Prime
    - Sieve
      - dest
      - increment
      - incrementCounters
      - initial
      - invariant
      - invariantCounters
      - max
      - mk
      - next
      - primes

Theorems

⊦ ∀a. mk (dest a) = a

⊦ ∀n i. invariantCounters n i []

⊦ initial = mk (1, [])

⊦ ∀s. max s = fst (dest s)

⊦ ∀s. primes s = map fst (snd (dest s))

⊦ ∀r. invariant r ⇔ dest (mk r) = r

⊦ ∀n i. incrementCounters n i [] = (⊤, (n, 0, 0) :: [])

⊦ ∀s.
next s = let (b, s') ← increment s in if b then max s', s' else next s'

⊦ ∀n ps.
invariant (n, ps) ⇔
¬(n = 0) ∧ map fst ps = Prime.below (n + 1) ∧ invariantCounters n 0 ps

⊦ ∀n i p k j ps.
invariantCounters n i ((p, k, j) :: ps) ⇔
¬(p = 0) ∧ (k + i) mod p = n mod p ∧ invariantCounters n (i + j) ps

⊦ ∀s.
    increment s =
    let (n, ps) ← dest s in
    let n' ← n + 1 in
    let (b, ps') ← incrementCounters n' 1 ps in
    b, mk (n', ps')

⊦ ∀n i p k j ps.
    incrementCounters n i ((p, k, j) :: ps) =
    let k' ← (k + i) mod p in
    let j' ← j + i in
    if k' = 0 then ⊥, (p, 0, j') :: ps
    else let (b, ps') ← incrementCounters n j' ps in b, (p, k', 0) :: ps'

Input Type Operators

→
bool
Data
- List
  - list
- Pair
  - ×
Number
- Natural
  - natural

Input Constants

=
select
Data
- Bool
  - ∀
  - ∧
  - ⇒
  - ∃
  - ∨
  - ¬
  - cond
  - ⊥
  - ⊤
- List
  - ::
  - []
  - map
- Pair
  - ,
  - fst
  - snd
Number
- Natural
  - +
  - bit0
  - bit1
  - mod
  - suc
  - zero
  - Prime
    - Prime.below

Assumptions

⊦ ⊤

⊦ ¬⊥ ⇔ ⊤

⊦ ¬⊤ ⇔ ⊥

⊦ bit0 0 = 0

⊦ ⊥ ⇔ ∀p. p

⊦ (¬) = λp. p ⇒ ⊥

⊦ (∃) = λp. p ((select) p)

⊦ ∀t. (λx. t x) = t

⊦ (∀) = λp. p = λx. ⊤

⊦ Prime.below 2 = []

⊦ ∀t. (t ⇔ ⊤) ⇔ t

⊦ ∀t. ⊤ ∧ t ⇔ t

⊦ ∀t. t ∧ ⊤ ⇔ t

⊦ ∀t. t ⇒ ⊤ ⇔ ⊤

⊦ ∀n. ¬(suc n = 0)

⊦ ∀n. 0 + n = n

⊦ ∀f. map f [] = []

⊦ ∀n. bit1 n = suc (bit0 n)

⊦ (⇒) = λp q. p ∧ q ⇔ p

⊦ ∀t. (t ⇔ ⊤) ∨ (t ⇔ ⊥)

⊦ ∀t₁ t₂. (if ⊥ then t₁ else t₂) = t₂

⊦ ∀t₁ t₂. (if ⊤ then t₁ else t₂) = t₁

⊦ ∀x y. fst (x, y) = x

⊦ ∀x y. snd (x, y) = y

⊦ ∀p x. p x ⇒ p ((select) p)

⊦ ∀n. bit0 (suc n) = suc (suc (bit0 n))

⊦ ∀xy. ∃x y. xy = (x, y)

⊦ (∧) = λp q. (λf. f p q) = λf. f ⊤ ⊤

⊦ (∃) = λp. ∀q. (∀x. p x ⇒ q) ⇒ q

⊦ ∀m n. suc m + n = suc (m + n)

⊦ (∨) = λp q. ∀r. (p ⇒ r) ⇒ (q ⇒ r) ⇒ r

⊦ ∀f. ∃fn. ∀x y. fn (x, y) = f x y

⊦ ∀p. (∀x. ∃y. p x y) ⇔ ∃y. ∀x. p x (y x)

⊦ ∀p g h. ∃f. ∀x. f x = if p x then f (g x) else h x

⊦ ∀b f. ∃fn. fn [] = b ∧ ∀h t. fn (h :: t) = f h t (fn t)