# Shobute☘

## Project Euler 17

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

This problem can be solved by hand. I essentially used Python as a calculator to solve it:

len("onethousand" + 900*"hundred" + 190*"onetwothreefourfivesixseveneightnine" +
100*"twentythirtyfortyfiftysixtyseventyeightyninety" + 891*"and" +
10*"teneleventwelvethirteenfourteenfifteensixteenseventeeneighteennineteen")


Last updated on .

## Project Euler 16

What is the sum of the digits of the number 21000?

Very easy in Java thanks to BigInteger:

import java.math.BigInteger;

public class Problem16 {
public static void main(String[] args) {
BigInteger number = new BigInteger("2").pow(1000);
int sum = 0;
while (number.compareTo(BigInteger.ZERO) > 0) {
sum += number.remainder(BigInteger.TEN).intValue();
number = number.divide(BigInteger.TEN);
}
System.out.println(sum);
}
}


Last updated on .

## Project Euler 15

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

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

If you know anything about combinations in mathematics this problem is easy to solve without a line of code. You just use the binomial coefficient: $$\binom{40}{20} = \frac{40!}{20!^2}$$

Last updated on .

## Project Euler 14

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

n → n/2 (n is even)
n → 3n + 1 (n is odd)

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

Here’s my solution in Java:

public class Problem14 {
public static void main(String[] args) {
final int MAX = 1_000_000;
int longestChain = 0;
int result = -1;
int cache[] = new int[MAX];
for (int n = 2; n < MAX; n++) {
int terms = 1;
long m = n;
while (m >= n) {
m = (m % 2 == 0) ? m / 2 : 3 * m + 1;
terms++;
}
terms += cache[(int)m];  // safe to cast because m < n
cache[n] = terms;
if (terms > longestChain) {
longestChain = terms;
result = n;
}
}
System.out.println(result);
}
}


It stores the results it finds as it goes, so it doesn’t have to repeat the same computations.

Last updated on .

## Project Euler 13

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

Here’s my solution in Java, I left out a lot of the numbers for clarity’s sake:

public class Problem13 {
private static double[] NUMS = {
37107287.533902102798797998220837590246510135740250,
46376937.677490009712648124896970078050417018260538,
/* 96 other numbers go here... */
20849603.980134001723930671666823555245252804609722,
53503534.226472524250874054075591789781264330331690
};
public static void main(String[] args) {
double sum = 0;
for (double num : NUMS) sum += num;
System.out.println((long)sum);
}
}


It almost feels like cheating by storing the numbers as doubles but it works well because precision is not important and by putting the decimal point after 8 digits I end up with 10 digits after adding together 102 of them.

Last updated on .

## Project Euler 12

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

Here’s my solution in Java:

public class Problem12 {
public static void main(String[] args) {
int triangle = 0;
for (int n = 1, numFactors = 0; numFactors <= 500; n++) {
triangle = n * (n + 1) / 2;
numFactors = 2;
for (int div = 2; div * div <= triangle; div++) {
if (triangle % div == 0) numFactors += 2;
}
}
System.out.println(triangle);
}
}


Last updated on .

## Project Euler 11

What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?

I was going to solve this in Java but ended up just using my eyes (with a little help from Vim).

Last updated on .

## Project Euler 10

Find the sum of all the primes below two million.

Here’s my solution in Java:

public class Problem10 {
public static void main(String[] args) {
int max = 2_000_000;
boolean[] isComposite = new boolean[max + 1];
for (int i = 2; i * i <= max; i++) {
if (!isComposite[i]) {
for (int j = i; i * j <= max; j++) isComposite[i*j] = true;
}
}
long sum = 0;
for (int i = 2; i <= max; i++) if (!isComposite[i]) sum += i;
System.out.println(sum);
}
}


It uses the sieve of Eratosthenes algorithm. It could be optimized by using the sieve of Atkin, and/or using a bit vector instead of a boolean array, but as is it runs in a very fast time.

Last updated on .

## Project Euler 1

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

Very simple, just go through every number between 0 and 1000, and if it’s a multiple of 3 or 5 add it to the running total.

Here’s my initial solution in Java:

public class Problem1 {
public static void main(String[] args) {
int sum = 0;
for (int i = 0; i < 1000; i++) {
if (i % 3 == 0 || i % 5 == 0) sum += i;
}
System.out.println(sum);
}
}

This is fine if you only want to find the multiples below 1000, but for big ranges we can do far better.

We can solve this problem in constant time by making use of the fact that: $$\sum_{i=1}^ni = \frac{n(n+1)}2$$

The sum of all multiples of 3 and 5 below n can be calculated as: $$3\sum_{i=1}^{\lfloor\tfrac{1}{3}n-1\rfloor}i + 5\sum_{i=1}^{\lfloor\tfrac{1}{5}n-1\rfloor}i - 15\sum_{i=1}^{\lfloor\tfrac{1}{15}n-1\rfloor}i$$

Multiples of 15 have to be subtracted to remove duplicates which were multiples of both 5 and 3. One needs to be subtracted from each range because the questions says below 1000.

Using the earlier formula, this expands to: $$\frac{3\lfloor\tfrac{1}{3}m\rfloor(\lfloor\tfrac{1}{3}m\rfloor+1) + 5\lfloor\tfrac{1}{5}m\rfloor(\lfloor\tfrac{1}{5}m\rfloor+1) - 15\lfloor\tfrac{1}{15}m\rfloor(\lfloor\tfrac{1}{15}m\rfloor+1)}2$$ where $$m = n -1$$.

Translating into Java we get:

public class Problem1 {
public static void main(String[] args) {
final long RANGE = 1000;
long m = RANGE - 1;
long sum = (3 * (m / 3) * (m / 3 + 1) + 5 * (m / 5) * (m / 5 + 1) -
15 * (m / 15) * (m / 15 + 1)) / 2;
System.out.println(sum);
}
}

Last updated on .

## Least Restrictive Go Ruleset

Go is a game often praised for its simple rules, and the great complexity and depth that comes from them.

“The rules of Go are so elegant, organic, and rigorously logical that if intelligent life forms exist elsewhere in the universe, they almost certainly play Go.” — Edward Lasker

I have written what I consider to be the simplest ruleset for the game of go. It’s designed to be the least restrictive ruleset possible, while still keeping the essence of what makes go go. Here’s a complete definition of the rules:

1. The game is played on a finite graph.
2. Each player is assigned a discrete colour.
3. Play is alternate colouring of a non-coloured node.
4. A play of a colour causes loss of the other colours of all nodes without a path along the other colours to no colour and subsequently causes a loss of the colour of all nodes without a path along the colour to no colour.
5. No colouring after a play and its caused losses may be recreated.

The rules are based on graph theory. Unlike traditional rulesets they don’t specify the kind of board to play on, the number of players, the colours, or even passes and how to win. The result is a variant of go that can be played on any board, with any number of players, and play continues until there are no legal moves left (or more than likely the other players forfeits).

Last updated on .