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 9

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

The Problem

The Text of the Problem

Special Pythagorean Triplet

A Pythagorean triplet is a set of three natural numbers, $ a < b < c $, for which, $ a^2 + b^2 = c^2 $. For example, $ 3^2 + 4^2 = 9 + 16 = 25 = 5^2 $. There exists exactly one Pythagorean triplet for which $ a + b + c = 1000 $. Find the product $ abc $.

Thinking through the Problem

The Pythagorean theorem ( $ a^2 + b^2 = c^2 $ ) describes the relationships of the sides of right triangles. The most famous Pythagorean triplet is $ { 3, 4, 5 } $, which satisfies the theorem because $ 9 + 16 = 25 $.

Pythagorean Triangle: 3, 4, 5

This problem asks me to find such a triplet of numbers that add up to 1000.

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

Project Euler Problem 10

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

The Problem

The Text of the Problem

Summation of Primes

The sum of the primes below 10 is $ 2 + 3 _ 5 + 7 = 17 $. Find the sum of all the primes below two million.

Thinking through the Problem

This is another trivial problem. The question asks me to add up all the primes up to a certain point.

Read More

Project Euler Problem 8

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

The Problem

The Text of the Problem

Largest Product in a Series

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832. 1000-digit number Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

Thinking through the Problem

This problem asks me to scan a large number and find sequential digits that yield a high product. Somewhere in the 1000-digit number is the sequence 9989 and those 4 digits make the highest product.

Read More

Today I Learned: Agnostic Line Split in Javascript

A log of things I learn as I learn them.

I am keeping a log of things I learn as I learn them. I'm using GitHub and I'm going to try to commit to keeping that log. I want to post occassional summaries of things I learned relating to math, programming, and similar topics.

Agnostic Line Split in Javascript

2016 Jul 21

I've found a need to split a string (read from text file) into a list where each string in the list is the content of a single line. This is normally easy to accomplish:

1
fileText.split ( '\n' );

But the above snippet assumes normal Unix file endings. Sometimes files don't end with '\n', but with '\r\n' instead. The string.split() method can take a regular expression instead of a string, and the following command will split the string properly regardless of which type of line ending is present:

1
fileText.split ( /\r?\n/ );