Skip to content

Instantly share code, notes, and snippets.

@luqui
Created November 20, 2011 02:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save luqui/1379703 to your computer and use it in GitHub Desktop.
Save luqui/1379703 to your computer and use it in GitHub Desktop.
A (haskell program representing a) lambda term whose normalization is not known
sq = floor . sqrt . fromIntegral
primes = 2:filter (\n -> all (\m -> not (m `divides` n)) (cand n)) [3..]
where cand n = takeWhile (<= sq n) primes
m `divides` n = n `mod` m == 0
fibs = 0:1:zipWith (+) fibs (tail fibs)
l5 p | p5 == 1 || p5 == 4 = 1
| p5 == 2 || p5 == 3 = -1
where
p5 = p `mod` 5
-- checks whether a prime p is a Wall-Sun-Sun prime
wallSunSun p = (p^2) `divides` (fibs !! (p - l5 p))
normalizes_questionmark = head . filter wallSunSun . dropWhile (<= 5) $ primes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment