Skip to content

Instantly share code, notes, and snippets.

@csoroz

csoroz/Hofstadters.hs

Created May 10, 2017 15:55
Show Gist options
  • Save csoroz/c49ff8c65fd98c223f627b733fef475e to your computer and use it in GitHub Desktop.
Save csoroz/c49ff8c65fd98c223f627b733fef475e to your computer and use it in GitHub Desktop.
Download ZIP
Hofstadter Figure-Figure sequences
Raw
Hofstadters.hs
import Data.List
-- https://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Figure-Figure_sequences
-- Hofstadter Figure-Figure sequences [R](https://oeis.org/A005228) and [S](https://oeis.org/A030124)
-- R(0) = 1; S(0) = 2; {S(n)} = increasing series of positive integers not present in {R(n)}
-- R(n+1) = R(n) + S(n)
r = 1:zipWith (+) r s
s = 2:4:drop 2 (concat $ zipWith ss r (tail r)) where ss x y = [x+1..y-1]
main = print (take 22 r) -- [1,3,7,12,18,26,35,45,56,69,83,98,114,131,150,170,191,213,236,260,285,312]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment