Project Euler Problem 19

This post is part of a series about solving Project Euler problems. This is the post about Problem #19.

The Problem

The Text of the Problem

Counting Sundays

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September, April, June, and November. All the rest have thirty-one, Saving February alone, which has twenty-eight, rain or shine. And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisibly by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

Thinking through the Problem

This problem requires looking at the 1st of the month for every month of the 20th century. This is complicated by variant month lengths, especially Februaries. The native time objects in computer languages only track time starting at midnight on 1970 Jan 1, which complicates looking at any dates prior to that time.

Read More

Project Euler Problem 18

This post is part of a series about solving Project Euler problems. This is the post about Problem #18.

The Problem

The Text of the Problem

Maximum Path Sum I

By starting at the tope of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

1
2
3
4
5
>    3
> 7 4
> 2 4 6
> 8 5 9 3
>

>

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

triangle_data

Thinking through the Problem

This problem asks me to find the highest sum path from the top of a number triangle to its base. According to a fine print message at the bottom of the problem, there are a total of 16384 possible paths through the given triangle. Trying all of them is not the right way to go about this.

Read More

Book Review: Lying (by Sam Harris)

People lie so that others will form beliefs that are not true... They lie to avoid embarrassment, to exaggerate their accomplishments, and to disguise wrongdoing. They make promises they do not intend to keep... Many of us lie to our friends and family members to spare their feelings. -- Sam Harris

I recently read the book Lying by Sam Harris, after having meant to read it for a while. It's short enough that once I sat down to read it I realized I had no excuse for having put it off. Within the first few pages, I realized I was reading one of the most important books I've ever read.

The book's topic is lying, and it mostly focuses on the casual lying most people probably do daily. I think many people share the intuition that lying is wrong (at least when thought of from the perpective of the person being lied to), but casual lies are too easy to make excuses for in many cases. I'd never come across as clear, solid, and non-dogmatic case against those excuses as the one presented by Sam Harris in Lying.

After reading the book, I was entirely convinced by it. I've always held that lying is wrong, but occasionally made use of the many caveats and excuses for small lies that are all addressed (in my opinion concusively) in this book.

Read More

Project Euler Problem 17

This post is part of a series about solving Project Euler problems. This is the post about Problem #17.

The Problem

The Text of the Problem

Number Letter Counts

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

Thinking through the Problem

While not particularly difficult, this problem is significantly more involved than many of the ones before. Fortunately, English numbers are spoken according to a straightforward pattern. The one major exception to this is that the numbers 11-19 are not like 21-29, 31,-39, etc. Furthermore, 11 and 12 and especially unusual (not being oneteen and twoteen).

The problem specifies the use of the word 'and' between the hundred's place and the ten's place, which is not how I say the numbers so it's something extra to keep in mind. I also have to remember not to include spaces in my counts.

Read More

Project Euler Problem 16

This post is part of a series about solving Project Euler problems. This is the post about Problem #16.

The Problem

The Text of the Problem

Power Digit Sum

$ 2^{15} = 32768 $ and the sum of its digits is $ 3 + 2 + 7 + 6 + 8 = 26 $.

What is the sum of the digits of the number $ 2^{1000} $

Thinking through the Problem

This is another straightforward problem. It asks that I raise 2 to the power of 1000 and sum the digits.

Read More

Project Euler Problem 15

This post is part of a series about solving Project Euler problems. This is the post about Problem #15.

The Problem

The Text of the Problem

Lattice Paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Thinking through the Problem

This is the first Project Euler problem that I found really tricky. Going only right and down from one corner to the other is an impossible problem to brute force in a reasonable amount of time for a large grid.

One observation worth noting is that all paths will be same length, and have the same number of down movements and right movements. No matter what path is taken from one corner to the other in a 20 by 20 grid, there must be exactly 20 down movements and exactly 20 right movements.

Read More

Project Euler Problem 14

This post is part of a series about solving Project Euler problems. This is the post about Problem #14.

The Problem

The Text of the Problem

Longest Collatz Sequence

The following iterative sequence is defined for the set of positive integers:

$ n \rightarrow \frac{n}{2} $ if n is even

$ n \rightarrow 3n + 1 $ if n is odd

Using the rule above and starting with 13, we generate the following sequence:

$$ 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 $$

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain.

NOTE: Once the chain starts the terms are allowed to go above one million.

Thinking through the Problem

The Collatz Sequence supposedly goes to 1 no matter what the starting point is. Some numbers will undoubtedly take a long time to get there. This question asks me to find the longest one.

Read More

Project Euler Problem 13

This post is part of a series about solving Project Euler problems. This is the post about Problem #13.

The Problem

The Text of the Problem

Large Sum

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

data

Thinking through the Problem

This straightforward problem asks us to calculate a very large sum.

Read More

Project Euler Problem 12

This post is part of a series about solving Project Euler problems. This is the post about Problem #12.

The Problem

The Text of the Problem

Highly Divisible Triangular Number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be $ 1 + 2 + 3 + 4 + 5 + 6 +7 = 28 $ The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55

Let us list the factors of the first seven triangle numbers:

  • 1: 1
  • 3: 1, 3
  • 6: 1, 2, 3, 6
  • 10: 1, 2, 5, 10
  • 15: 1, 3, 5, 15
  • 21: 1, 3, 7, 21
  • 28: 1, 2, 4, 7, 14, 28

We can see that 28 is the first triangle number to have over five divisors.

what is the value of the first triangle number to have over five hundred divisors?

Thinking through the Problem

Triangle numbers are numbers that could make a good bowling pin arrangement. They are generated by a very simple pattern. This problem asks me to generate those numbers and count up divisors.

Read More

Project Euler Problem 11

This post is part of a series about solving Project Euler problems. This is the post about Problem #11.

The Problem

The Text of the Problem

Largest Product in a Grid

In the 20x20 grid below, four numbers along a diagonal line have been marked in red. number_grid The product of these numbers is $ 26 \cdot 63 \cdot 78 \cdot 14 = 1788696 $. What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20x20 grid?

Thinking through the Problem

This problem presents a grid of numbers and asks me to find the greatest product derived by multiplying 4 numbers in a row in any direction.

Read More