Solving Project Euler problems with SPARQL and Wikidata

by Envel Le Hir — CC BY-SA 4.0 — May 1, 2020 — SPARQL, Wikidata

Founded in 2001, Project Euler is a website offering a series of more than 700 mathematical problems that you can solve with the programming language of your choice. Unsurprisingly, Python, C/C++, and Java are the most popular languages used by visitors of the website. I wanted to know if it was possible to use Wikidata and its SPARQL endpoint to solve these problems.

Spoiler: this post gives the solution of the first problem and discusses how to solve the second. Don’t hesitate to first go to Project Euler and to find the solutions by yourself.

Problem 1

The objective of the first problem is to find the sum of all the multiples of 3 or 5 below 1,000.

Let’s find all natural numbers in Wikidata, with their numerical values:

SELECT ?item ?value {
  ?item wdt:P31 wd:Q21199 ; wdt:P1181 ?value .
}
ORDER BY ?value

As you can see, Wikidata has more than 10,000 items about natural numbers. Some values are duplicated, like Q199 (the number 1) and Q713113 (the number 0.999… which is equal to 1).

Let’s remove the duplicates and filter the numbers to keep only the ones below 1,000:

SELECT DISTINCT ?value {
  ?item wdt:P31 wd:Q21199 ; wdt:P1181 ?value .
  FILTER (?value < 1000) .
}
ORDER BY ?value

There are exactly 999 numbers between 1 and 999, so none is missing.

Let’s keep only the numbers that are the multiples of 3 or 5, by checking that their division by 3 or 5 has no remainder:

SELECT DISTINCT ?value {
  ?item wdt:P31 wd:Q21199 ; wdt:P1181 ?value .
  FILTER (?value < 1000 && (floor(?value / 3) = (?value / 3) || floor(?value / 5) = (?value / 5))) .
}
ORDER BY ?value

Here are the results.

Now, we just have to sum the numbers:

SELECT (SUM(DISTINCT ?value) AS ?sum) {
  ?item wdt:P31 wd:Q21199 ; wdt:P1181 ?value .
  FILTER (?value < 1000 && (floor(?value / 3) = (?value / 3) || floor(?value / 5) = (?value / 5))) .
}

And Wikidata gives us the solution of the problem!

Problem 2

The objective of the second problem is to find the sum of even Fibonacci numbers below 4,000,000.

Let’s find Fibonacci numbers available in Wikidata:

SELECT ?value {
  ?item wdt:P31 wd:Q47577 ; wdt:P1181 ?value .
}
ORDER BY ?value

Only the twenty first ones, below 10,000, are known in Wikidata. As a general-purpose database, Wikidata is certainly not made to store every existing numbers under 4,000,000. It makes the method previously used in the first problem not applicable here.

At the moment, I don’t see any simple solution to solve this second problem using Wikidata’s SPARQL endpoint, and probably neither to the following ones. Maybe you can do it?

For your information, more complex problems, not related to Project Euler, have been solved using SPARQL, outside of Wikidata’s endpoint, like Sudoku (for instance here or there).