For the last few days, I’ve been going through Advent of Code. It’s not that its problems aren’t fun, but I find Project Euler a bit more suited for myself, a mathematics undergrad student. It’s in this spirit, that I’ve focused a bit more time on it.

Having lost my account, I had to tackle Problem 0.

Disclaimer: Project Euler #0

This exposes a solution for Project Euler Problem 0

source: https://projecteuler.net/register

Introduction #

Got a bit winded with Advent of Code, so I chose to explore Project Euler again. Looked around, and couldn’t find my account details for it. So my original account with a few dozen solutions has been frozen. Back to registration.

While trying to register, I found that there was an initial problem, a so called “Problem Zero”.

Following a similar path to the Advent of Code adventure, I created a repository to hold my python code.

The repository holding the solutions: https://codeberg.org/cpmachado/eulerpy

Problem Statement #

Problem 0

A number is a perfect square, or a square number, if it is the square of a positive integer. For example, 25 is a square number because
$5^2 = 5 \times 5 = 25$ ; it is also an odd square.

The first $5$ square numbers are: 1, 4, 9, 16, 25 and the sum of the odd squares is 1 + 9 + 25 = 35.

Among the first $N$ square numbers, what is the sum of all the odd squares?

Credits: Project Euler https://projecteuler.net/register

source: https://projecteuler.net/register

Analysis #

Reading the statement #

We are given a natural number $N$, and intend to sum the odd square numbers that are squares of numbers between 1 and $N$. Thus a function that encapsulates this, will have $N$ as a parameter.

def sum_square_odd_numbers(n: int) -> int:
    """Computes the sum of the odd squares of [1, n]"""
    pass

Given that the square numbers are odd, we can deduce that they are squares of odd numbers, because they won’t be congruent with 2.

Let there be $L = \lceil N / 2\rceil$, we can write it as:

Write a test #

Before computing, we need to validate. From the statement, and a couple of edge cases, results in:

Snippet: Very rudimentary test

def test_p0():
    assert sum_square_odd_numbers(1) == 1
    assert sum_square_odd_numbers(2) == 1
    assert sum_square_odd_numbers(3) == 10
    assert sum_square_odd_numbers(4) == 10
    assert sum_square_odd_numbers(5) == 35
    # test negative and 0
    assert sum_square_odd_numbers(-1) == 0
    assert sum_square_odd_numbers(0) == 0

Naive solution #

In Python, the trivial solution for this is to sum over a range construct, with start from $1$, limit set at $n + 1$, as to include $n$, and step of $2$.

Snippet: The one liner solution basically

def sum_square_odd_numbers(n: int) -> int:
    """Computes the sum of the odd squares of [1, n]"""
    return sum(k**2 for k in range(1, n + 1, 2))

This should work for our purpose, but it’s linear complexity can be replaced by a constant solution, which we’ll analyse in the next section.

Closed form solution #

Due to the nature of the underlying series, there’s a closed form that is able to compute in constant time.

As stated before, let $L = \lceil N / 2\rceil$, we can write it as:

Assuming we know the closed forms for the sum of squares($\sum^n_k k^2$) and the sum of naturals($\sum_k^n k$), we get:

This results in a $O(1)$ solution we were searching for. For ceiling, since we are using integer division, we do $(N + 1) \div 2$.

Snippet: An implementation of the closed form

def sum_square_odd_numbers(n: int) -> int:
    """Sum of Square Odd Numbers for the first given N numbers"""
    l = (n + 1) // 2
    return  (4 * l * l - 1) * l // 3

Conclusion #

To start, this made be look back into my Number Theory books, which is always positive. I’m a bit out of form in this field, but soon enough I’ll revise this, and add the aforementioned identities for the sum of squares and the sum of naturals.

Since starting to write this article, I’ve already completed ten more problems, whose analysis are soon to come. My objective is to do this slowly, revise and explore all that this Project has to offer.