site logo

Project Euler: The first 5

Published on 2026-09-21

Project Euler is one of the first websites I stumbled upon in the early days of my programming journey. I gave up pretty quickly due to my lack of experience and limited resources. But now I’ve decided to take another trip up the mountain with Awk. Of course I’m not going to spoil the latest programming challenges here. I’m just working through the Archive section. The solutions to those problems have already been posted over and over again, and some of them are regurgitated when you ask LLMs for help.

Of course I should note here that I found all of the solutions on my own without knowingly accepting help from AI. This is actually quite difficult on the modern Web, even when viewing solutions from Stack Overflow and Reddit. LLMs have already been fed the vast majority of the world’s code, and people can easily ask Claude/Gemini/whatever to solve a problem, tweak the resulting code a bit, and post the answer as their own.

But as far as I know, I found all of the solutions on my on.

Problem 1: Multiples of 3 or 5

Here’s the challenge text verbatim from the web page.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6, and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

This looked like a variant of the classic FizzBuzz programming problem, which is easily solved with the modulo operator % in most of today’s programming languages.

Here’s my solution.

# file: multiples_of_3_or_5.awk
# Find all multiples of 3 OR 5 BELOW 1000.
# Then add them to together.
BEGIN {
  total = 0;
  for (i = 999; i > 2; i--) {
    if ((i % 3) == 0 || (i % 5) == 0) {
      print(i);
      total += i;
    }
  }

  print("TOTAL: ", total)
}

The first thing to note here is that I’m using a BEGIN block. This block is always executed by Awk before any input files are processed. Because I just want to run the programs with awk -f fileName.awk without any input files, all of my solutions have to run inside a BEGIN block.

Because the challenge said below 1000, I started my loop at 999 and worked my way down. Inside the if statement, I used the modulo operator twice. The modulo operator performs division and returns the remainder instead of the quotient. If the remainder of i % 3 is 0, then we know that i is cleanly divisible by 3. Therefore, i has to be a multiple of 3. Throw in a logical or operator (||) and you’ve basically solved the problem.

As the loop counts down from the 999, it adds each qualifying value to a total that is displayed at the end.

...
15
12
10
9
6
5
3
TOTAL:  233168

DIY Modulo

Now let’s pretend for moment that Awk has no modulo operator. How would I solve the problem? Well, as far as I know, Awk does not support user-defined operators. That means a function will have to be used instead.

# file: bring_your_own_modulo.awk
# Let's pretend that Awk has no modulo operator.
function modulo(a, b,   result) {
  result = 0;
  while (a > 0) {
    result = a - b;
    a -= b;
  }

  return result;
}

# Find all multiples of 3 OR 5 BELOW 1000.
# Then add them to together.
BEGIN {
  total = 0;
  for (i = 999; i > 2; i--) {
    if (modulo(i, 3) == 0 || modulo(i, 5) == 0) {
      print(i);
      total += i;
    }
  }

  print("TOTAL: ", total)
}

Division is simply a shorthand for repeated subtraction. In classical integer division, we get a quotient and a remainder. The quotient is the number of times we can subtract b from a without turning a into a negative number. We don’t care about that here. We want the remainder, which is what a becomes at the end of the process.

This version of the program returns the same result:

...
15
12
10
9
6
5
3
TOTAL:  233168

The first approach is the technically correct solution, but the second approach is a bit more realistic. No programming language has built-in solutions for every conceivable problem. Sometimes you have to write your own. That where libraries come from!

Problem 2: Even Fibonacci numbers

Challenge text from the web page:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

This problem uses the classic Fibonacci sequence in an interesting way. The traditional way to solve such a problem is with functions and recursion, but I decided to take a more conventional approach.

Here is my solution:

file: even_fibonacci_sum_of_terms.awk
# Find the sum of all EVEN Fibonacci numbers under 4,000,000.
BEGIN {

  # Initialize the variables.
  first = 0;
  second = 1;
  result = 0;
  answer = 0;

  # Start the infinite loop.
  while (1) {

    # Add first and second numbers.
    result = first + second;

    # First becomes second.
    first = second;

    # Second becomes result.
    second = result;
    #print(result);

    # If the result of adding the 2 numbers is even, add it to the final answer.
    if ((result % 2) == 0) {
      answer += result;
      #print(answer);
    }

    # We only want values less than 4,000,000.
    if (result > 4000000) {
      break;
    }
  }

  print("ANSWER: ", answer);
}

At first glance, this may seem a bit a strange. The problem implies that you should start with the values 1 and 2, not 0 and 1! So let’s walk through the loop a few times.

With each run through the loop, it checks if result is an even number. If it is, then result is added to answer. The loop keeps running until result exceeds 4,000,000. Then the loop breaks and the final answer is printed.

Sample run that prints answer on each iteration:

2
10
44
188
798
3382
14328
60696
257114
1089154
4613732
ANSWER:  4613732

Problem 3: Find the largest prime factor of 600,851,475,143

Challenge text from the web page:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

This one was a bit of a pain to work through. First I got hung up on the idea of primeness. Then I tried a naive solution to check if a number was a factor of another number.

WRONG ROUTE: Logically correct, painfully slow.

# file: largest_prime_wrong_way.awk
function isFactor(a, b) {
  # If 'a / b' returns a remainder of 0, then the division is clean and 'b'
  # must be a factor of 'a'.
  if ((a % b) == 0) {
    # TRUE
    return 1;
  } else {
    # FALSE
    return 0;
  }
}

function isPrime(num,   result, limit) {
  # Set 'result' to default value of False.
  result = 0;

  # Prime numbers have to be greater than 1.
  if (num > 1) {
    # 2 is the first prime number, so there's no point in continuing.
    if (num == 2) {
      result = 1
    } else {
      limit = num;

      # Loop as long as limit is over 2.
      while (limit > 2) {
        # As soon as a factor is found, break.
        # 'num' is NOT prime.
        if (isFactor(num, limit)) {
          break;
        }
        
        # Else, decrement limit and continue.
        limit--;
      }
    }
  }
  
  return result;
}

BEGIN {
  starting = 600851475143
  answer = 600851475143

  print("STARTING: ", starting);

  while (answer > 0) {
    #print("CHECKING: ", answer);
    if (isFactor(starting, answer) && isPrime(answer)) {
      print("ANSWER: ", answer);
      break;
    }

    answer--;
  }
}

The above seems logically correct, but it takes forever to actually run. After two hours my computer still didn’t have an answer. That told me that it probably wasn’t the intended solution.

The correct solution: squaring the divisor

After some digging, I learned how to find factors more quickly by squaring the divisor.

# file: first_try.awk
# Find the largest prime factor of 600851475143

BEGIN {
  limit = 600851475143; 

  # The lowest squared number is 4, which is 2 * 2.
  # Therefore, the lowest "square factor" is 2.
  divisor = 2;

  print("START: ", limit);

  # Loop until we find a square number less than or equal to 'limit'.
  # Example:
  # 2 * 2 = 4
  # 3 * 3 = 9
  # 4 * 4 = 16
  # 5 * 5 = 25
  # 6 * 6 = 36
  # ...
  while (divisor * divisor <= limit) {
    # If 'limit' / 'divisor' results in nothing leftover, then we found a factor.
    if (limit % divisor == 0) {
      limit = limit / divisor;

      print("LIMIT: ", limit);
      print("DIVISOR: ", divisor);
    } else {
      # Else, increment 'divisor'.
      divisor++;
    }
  }

  print("ANSWER: ", limit);
}

With each iteration, it checks if the result of squaring the divisor is less than or equal to limit. If limit can be cleanly divided by divisor, the result of the division becomes the new value of limit. At the end of each iteration, divisor is incremented.

So as limit gets whittled down, the square of the divisor comes up to meet it. This leads to the correct answer of 6857:

START:  600851475143
LIMIT:  8462696833
DIVISOR:  71
LIMIT:  10086647
DIVISOR:  839
LIMIT:  6857
DIVISOR:  1471
ANSWER:  6857

But something about the solution bothered me. Did it work for other values? What if the starting value was even instead of odd? So I modified the program a bit to try out other numbers.

# file: largest_prime_loop.awk
function largestPrimeFactor(num,   divisor) {
  # The lowest square number is 4, which is 2 * 2.
  # Therefore, the lowest "square factor" is 2.
  divisor = 2;

  print("---------------");
  print("START: ", num);

  # Loop until we find a square number less than or equal to 'num'.
  # Example:
  # 2 * 2 = 4
  # 3 * 3 = 9
  # 4 * 4 = 16
  # 5 * 5 = 25
  # 6 * 6 = 36
  # ...
  while (divisor * divisor <= num) {
    # If 'num' / 'divisor' results in nothing leftover, then we found a factor.
    if (num % divisor == 0) {
      num = num / divisor;

      #print("LIMIT: ", num);
      #print("DIVISOR: ", divisor);
    } else {
      # Else, increment 'divisor'.
      divisor++;
    }
  }

  print("ANSWER: ", num);
  print("---------------");
  return num;
}

BEGIN {
  loopStart = largestPrimeFactor(600851475143); 
  while (loopStart > 1) {
    largestPrimeFactor(loopStart);
    loopStart--;
  }
}

The loop was my attempt to break the program. Here’s the output:

---------------
START:  600851475143
ANSWER:  6857
---------------
---------------
START:  6857
ANSWER:  6857
---------------
---------------
START:  6856
ANSWER:  857
---------------
---------------
START:  6855
ANSWER:  457
---------------
...
redacted
...
---------------
START:  9
ANSWER:  3
---------------
---------------
START:  8
ANSWER:  2
---------------
---------------
START:  7
ANSWER:  7
---------------
---------------
START:  6
ANSWER:  3
---------------
---------------
START:  5
ANSWER:  5
---------------
---------------
START:  4
ANSWER:  2
---------------
---------------
START:  3
ANSWER:  3
---------------
---------------
START:  2
ANSWER:  2
---------------

I cut out a good chunk of it for brevity. If you want to view the full output of 27,428 lines, you may run the program yourself.

In the world of programming, the first solution you come up with may not be best solution. It’s quite common for a problem to have multiple solutions that are not even remotely similar.

Problem 4: Largest palidrome product of a pair of 3-digit numbers

Here’s the challenge text verbatim from the web page.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 times 99.

Find the largest palindrome made from the product of two 3-digit numbers.

This was a fun one because it was the first time I ever heard the word palindrome. A palindrome is a string of characters that reads the same forward and backward, like “121”, “gg”, “ava”, etc. There’s probably a really cool math trick that can reverse a number, but I couldn’t figure it out. So I decided to use the string manipulation method instead.

Here’s my solution:

# file: largest_palindrome_product.awk
# Reverse a string by turning it into an array, flipping it around, and gluing it back together.
function reverseStr(str,   rev, i, lst) {
  rev = "";
  split(str, lst, "");

  for (i in lst) {
    # Put the string back together in reverse order.
    rev = lst[i] rev;
  }

  return rev;
}

BEGIN {
  #print("Reverse of 1234: ", reverseNum(1234));
  factors["left"] = 0;
  factors["right"] = 0;
  pal = 0;
  
  # The highest 3 digit number is 999, and the lowest is 100.
  for (left = 999; left > 101; left--) {
    for (right = left; right > 100; right--) {
      p = left * right;
      if (reverseStr(p) == p) {
        if (p > pal) {
          pal = p;
          factors["left"] = left;
          factors["right"] = right;
        }
      }
    }
  }

  print("ANSWER: " pal);
  print("left: " factors["left"]);
  print("right: " factors["right"]);
}

The function reverseStr() splits a string into an array of characters and puts it back together in reverse order. Awk uses context to automatically convert between numbers and strings, so no explicit conversion is necessary.

After that, the program loops through every pair of 3-digit numbers from 999 to 100. When the program finds a palindrome, it checks to see if it’s higher than the value of pal. If so, it overwrites pal with the new value and records the successful pair of factors.

Here’s the output:

ANSWER: 906609
left: 993
right: 913

So the answer is 906609, which is the product of 993 and 913. Solving this problem was fun, but I wish I understood the mathematical solution for reversing a number.

Problem 5: Smallest multiple

Here’s the challenge text verbatim from the web page.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible with no remainder by all of the numbers from 1 to 20?

This was another problem I wish I knew the maths behind. Instead, I had to brute force it. While the program I wrote prints out the correct answer, it takes a while to run.

BEGIN {
  start = 20;
  answer = start;

  while (1) {
    print("testing " answer);

    pass = 1;
    for (i = start; i > 1; i--) {
      #print(answer % i);

      if ((answer % i) != 0) {
        pass = 0;
        break;
      }
    }

    if (pass) {
      break;
    }

    # The solution MUST be divisible by 20, so we can step by to save a bit of time.
    answer += start;
  }

  print("ANSWER: " answer );
}

Yes, it test every single number front start to 1. I managed to speed it up a little bit by adding start answer on each iteration, but I still think a proper solution would take less than 2.7 seconds to run on an Intel Core i5.

Here’s the sample output, with the “testing” print statement commented out:

ANSWER: 232792560

real    0m2.703s
user    0m2.694s
sys     0m0.009s

The correct answer is 232792560.

Conclusion

I found these first five problems more challenging than expected. That’s probably because my mathematical prowess is a bit on the poor side. I use simple arithmetic in my daily life and rarely dive into anything more complex. Still, I managed to solve these problems on my own, and it was more fun than frustrating.