Euler Project using Postgres

This is the first post of a series about using SQL, and postgres of course, to solve Project Euler problems. This started as an exercise to master advanced features of postgres/SQL. When I realized that some solutions were quite elegant, I decided to share them here. I’ve also setup github discussions in this blog so that you can give a feedback.

Problem 2

Fibonacci Series! This is a classic problem usually solved with a loop. Ops, we don’t have loops in SQL, at least not explictly. More specifically, this loop is a while and not a for loop. The closest thing I’ve found is a recursive CTE. As explained in the docs, recursive CTEs are internally evaluated as an iteration.

This solution use the most basic features of recursive CTEs. Let’s not hurry. We have enough complexity to start with. It is easier to explain the syntax of a recursive CTE with an example:

with recursive t(n) as (
    values(1) -- initial value of t(n)
  union 
    select n+1 from t -- iteration step
)
select * from t limit 5;

n
1
2
3
4
5

The query above generates a incremental sequence starting from 1. It is an infinite sequence so if we do not put a limit the query will never end. The structure of the recursive CTE has two placeholders: the stuff before union and the stuff after union. They are respectively the initial content of the table and the iteration step by which the table grows. The rest follows as a standard CTE.

Generating a Fibonacci table

with recursive fibonacci(previous_term, term) as (
    values (1, 1)
  union
    select term                 as previous_term,
           previous_term + term as term
    from   fibonacci
)
select * from fibonacci limit 10;

previous_term	term
1	1
1	2
2	3
3	5
5	8
8	13
13	21
21	34
34	55
55	89

Final solution

This problem asks all even numbers in the series below a given threshold. Inside the recursive CTE we cut the series with a where term and we sum all even terms in the concluding select statement.

with recursive fibonacci(previous_term, term) as (
    values (1, 1)
  union
    select term                 as previous_term,
           previous_term + term as term
    from   fibonacci
    where  term < 4*1000*1000
)
select sum(term) from fibonacci where mod(term,2)=0

Now that I’m used to the recursive CTE syntax, this solution seems quite elegant to my eyes. Well, maybe I write too much SQL…