Problem 28 : Number Spiral Diagonals

Number spiral diagonals

Problem 28

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.
What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

                                                                                                       (https://projecteuler.net/problem=28)

There are LOTS of possible solutions for this problem.

I will suggest you two of them, including my own and the good one I found online and in the forum.

1) Algorithmic approach using iteration

This is most computer-science-ish solution I can come up with, as I didn't use my brain at all while writing this solution. If you look at the second solution, you will see what I mean.

Let's look at the red numbers and the distance between them.

In the center, it's 1. Okay, we get that.

In the second layer, where the numbers 2 - 9 are located, we see that the difference between the number is 2. Keep that in mind.

In the third layer, where the numbers 10 - 25 are located, we see that the difference between the number is 4.

In the fourth layer..? the difference will be 6. A simple arithmetic progression -> 2n, where n ≥ 1

So from this, we know that we need to:

1) find the incrementation for each layer and
2) increase the number by the incrementation x 4 (four corners) and add them to our total sum

Here is the implementation:

private static final int LEN = 1001;

    public static void run()
    {
        int currentNum = 1;
        int sum = currentNum;
        
        for (int i = 1; i <= LEN/2; i++)
        {
             int incr = 2*i;
             for (int j = 0; j < 4; j++) // calculate all 4 sides
             {
                  currentNum += incr;
                  sum += currentNum;
              }
        }
        System.out.println(sum);
}

2) Mathematical approach using universal formula

I found this solution in: http://www.mathblog.dk/project-euler-28-sum-diagonals-spiral/

Kristian explained his logic really well, but I will briefly go over his solution.

The most gorgeous part of his solution is that we don't need any computer algorithm to solve this problem.

We can manually find the total sum of red numbers for L x L square:

n	0	1	2	3	4	5	6
f(n)	1	25	101	261	537	961	1565
∆1		24	76	160	276	424	604
∆2			52	84	116	148	180
∆3				32	32	32	32

where n = [L / 2]

Because ∆₃ has all the constant incrementation, we will use 3rd-order polynomial function.

f(n) = ax³ + bx² + cx + d

We will use the following four equations to find the four constants a, b, c, and d:

d = 1

a + b+ c + d = 25

8a + 4b + 2c + d = 101

27a + 9b + 3c + d = 261

After solving the equations:

a = 16/3, b = 10, c = 26/3, d = 1

So our final formula is:

f(n) = 16/3x³ + 10x² + 26/3x + 1

If we plug in n = [L / 2] = [1001 / 2] = 500,

f(n) = f(500) = f(n) = 16/3(500)³ + 10(500)² + 26/3(500) + 1 = 669171001

Answer is 669171001
Execution time is .692364 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem028.java

Problem 25 : 1000-Digit Fibonacci Number

1000-digit Fibonacci number

Problem 25

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

F₁ = 1
F₂ = 1
F₃ = 2
F₄ = 3
F₅ = 5
F₆ = 8
F₇ = 13
F₈ = 21
F₉ = 34
F₁₀ = 55
F₁₁ = 89
F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

                                                                                                       (https://projecteuler.net/problem=25)
Okie, guys. We are going to explore Fibonacci Sequence.

If we say

                                                                       F₀=0, F₁=1,

then

F_n = F_n-1 + F_n-2
So the Recursive Definition of Fibonacci Sequence would be our focus.

And here is a formula for finding the nth term of Fibonacci sequence:

                                                         a_n = [ Phiⁿ - (phi)ⁿ ]/Sqrt[5]                                                           

where Phi = (1+Sqrt[5])/2 is golden ratio (1.61803398875), and phi = (1-Sqrt[5])/2 is an associated golden number.

(phi also equals to -1/Phi)

Yes, Fibonacci number is related to the golden number. It is as beautiful as that ratio in nature.

(Yet there are lots of disputes on the existence of "golden ratio" and its aesthetic impact. You can google them later.)

Anyway this problem requires the number TOO LARGE to use int data type. We are going to use BigInteger instead.

Set the limit first:

private static final int DIGIT = 1000;
private static final BigInteger LIMIT = BigInteger.TEN.pow(DIGIT-1);

Then initialize the starting terms of the recursive function:

int index = 2; // f1 and f2
BigInteger f1 = BigInteger.ONE, f2 = BigInteger.ONE;

Finally, implement the recursion:

while (f2.compareTo(LIMIT) < 0)
{
    BigInteger temp = f1.add(f2);
    f1 = f2;
    f2 = temp;
    index++;
}
System.out.println(index);

Answer is 4782
Execution time is 5.803691 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem025.java

Problem 14 : Longest Collatz Sequence

Longest Collatz sequence

Problem 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)

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

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 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.

                                                                                                       (https://projecteuler.net/problem=14)
Problem 14 is about Collatz sequence.



Assuming the Collatz conjecture that this process will eventually reach the number 1, regardless of which positive integer is chosen initially, we will find the longest chain under one million.

This problem can be solved using something similar to the Sieve of Eratosthenes.

Basically, the computer is calculating and memorizing the information (storing the information into an array) and reusing it later to reduce the time, as there are going to be lots of repetitions and redundancies in calculation.

The first step is simple.

If you take any number under half of one million, or five hundred thousand, that number will not be the longest chain.

Why does that happen? Let's say you choose 40 and 80.

40 has 9 terms in its sequence. 80, which is double of 40, will go through extra n / 2 step in the beginning, and therefore will have 10 terms in its sequence.

Aha! So if any number within the range of 1 to 500,000 will have shorter chain length than its doubled value, as long as they are in the range also.

So here is our limit:

private static final int LIMIT = 1000000;

...

for (int i = LIMIT/2 + 1; i <= LIMIT; i++)
{...}

And keep in mind that we don't need to find the length of the longest chain, we just need the starting number that has the longest chain.

That's the reason why I'm not going to keep track of the actual length; I will just record the relative length of each chain.

We are going to make an array that will store the information.

private static int[] collatz = new int[LIMIT+1];

Now, let's look at the method that will store the information.

// fill the collatz array : memorization
public static void fillCollatz(int n)
{...}

We initialize the variables that will keep track of the chain length and the current value of calculation.

int count = 0;
int current = n;

If the number is even number, then we will divide it by 2.

if (current%2 == 0) current /= 2;

Once it is divided by 2, it will be smaller than our starting value.

If the current value is smaller than the starting value, then that means somewhere in the previous steps (in our for-loop) we already calculated the chain length for that current value as a starting value.

And here is the advantage of memorization; we just skip the entire step and save tons of time.

collatz[n] = collatz[current] + count;

Here is an example. Say we have 40 and 80, like we did before.

Let's say the computer already calculated the chain length for 40 already (9 terms) and stored in the array.

  step: value

     0: 40
     1: 20
     2: 10
     3: 5
     4: 16
     5: 8
     6: 4
     7: 2
     8: 1

And the computer has to calculate the chain length for 80 now.

The computer will divide 80 by 2, and get 40, and current chain length will be 1.

And it will recognize that it already calculated the chain length for 40 in the past.

So it will recall the number 9 from its array and add it to the current chain length.

  step: value

     0: 80
     1: 40 (from here, the calculation is identical to the former one.)
     2: 20 (we don't want to waste our time on calculating exactly same stuffs.)
     3: 10
     4: 5
     5: 16
     6: 8
     7: 4
     8: 2
     9: 1

Now, let's deal with the numbers that are not even numbers.

Because those odd numbers will be multiplied by 3, it will get really large number that int will not be able to hold.

So we need to set the limit as one-third of integer max_value, and use long instead:

private static final int MAX = Integer.MAX_VALUE/3;

// fill the collatz array : memorization
public static void fillCollatz(int n)
{

   ...

   else if (current >= MAX)
   {
       long cur = current;
       ...
   }

   ...

}

And notice that odd * 3 + 1 always become an even number, and we can reduce the step by immediately calculating (odd*3 + 1) / 2 and increasing the number of chain length by 2.

Math: new number = (odd*3 + 1) / 2 = odd + (odd + 1) / 2

if (cur%2 == 0) cur /= 2;
else
{
 cur += (cur + 1)/2;
 count++;
}

At the end, we will store the information by adding new calculation and previous memory.

collatz[n] = collatz[current] + count;

Integrated solution:

// fill the collatz array : memorization
public static void fillCollatz(int n)
{
    int count = 0;
    int current = n;
    for ( ; current >= n; count++)
    {
        if (current%2 == 0) current /= 2;
        else if (current >= MAX)
        {
            long cur = current;
            for ( ; cur >= MAX; count++)
            {
                if (cur%2 == 0) cur /= 2;
                else
                {
                    cur += (cur + 1)/2;
                    count++;
                }
            }
            current = (int)cur;
            count--;
        }
        else
        {
            current += (current + 1)/2;
            count++;
        }
    }
    collatz[n] = collatz[current] + count;
}

And our main body will iterate through the numbers until it reaches one million:

public static void run()
{
    int num = 0, maxLength = 0;
  
    collatz[1] = 1;
    for (int i = LIMIT/2 + 1; i <= LIMIT; i++)
    {
        fillCollatz(i);
        if (collatz[i] >= maxLength)
        {
            maxLength = collatz[i];
            num = i;
        }
    }
    System.out.println(num);
}

Answer is 837799
Execution time is 38.619629 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem014.java

Picture by: https://www.jasondavies.com/collatz-graph/

Problem 29 : Distinct Powers

Distinct powers

Problem 29

Consider all integer combinations of a^b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

                                                                                                       (https://projecteuler.net/problem=29)
You know what. If you struggled with this problem, here is a cheat that you can follow.

It's not actual cheating, but there is no complicated algorithms used in this problem like my other solutions in this blog. I'll tell you one thing, and you're all-set.

In Java, there is a type of list called HashSet which only stores distinct values.

For example, I will add 1, 2, 2, 2, 4, 7, and 7 into an ArrayList.

index	0	1	2	3	4	5	6
data	1	2	2	2	4	7	7

Now, I will add 1, 2, 2, 2, 4, 7, and 7 into an HashSet.

index	?	?	?	?
data	1	2	4	7

We cannot directly know in what order the HashSet stores its data, yet we find that all the duplicate values were automatically eliminated, or not stored from the beginning.

And this is why it fulfills our goal: how many distinct terms are in the sequence.

Set<BigInteger> list1 = new HashSet<BigInteger>();
  
for (int a = 2; a <= 100; a++)
{
    for (int b = 2; b <= 100; b++)
    {
     list1.add(BigInteger.valueOf(a).pow(b));
    }
}
System.out.println(list1.size());

We will get 38.04139449846139 ms, or 0.038 seconds. Decent efficiency.

And I will tell you now that I lied. There is actually one more cheat that we can use here.

When we reach some numbers extremely large like a^b where 2 ≤ a, b ≤ 100, they are large enough that each number becomes extremely unique numbers.

So do we need precision? Does it matter that 123456789 is different from 123456788?

... Not really. It's just large number that is about 1.23 x 10⁸. That's all we need.

Therefore, I will simply use double instead of BigInteger.

I guarantee that double will provide enough precision for our calculation for this problem.

Set<Double> list = new HashSet<Double>();
  
for (int a = 2; a <= 100; a++)
{
    for (int b = 2; b <= 100; b++)
    {

        list.add(Math.pow(a, b));
    }
}
System.out.println(list.size());

Yay! 8.5 millisecond!

Answer is 9183
Execution time is 8.553895 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem029.java

Problem 23 : Non-Abundant Sums

Non-abundant sums

Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

                                                                                                       (https://projecteuler.net/problem=23)

A few days ago, we had a discussion about amicable numbers.

And I mentioned about 6, which was "amicable" to itself, and now it appears again.

As the problem explains, s(6) = 1 + 2 + 3 = 6, which means it is "amicable" number to itself, or we mathematically call it a perfect number.

Numbers like 12, where s(12) = 1 + 2 + 3 + 4 + 6 = 16 > 12, is called an abundant number.



Personally this problem was one of some tedious problems in Project Euler.

I couldn't come up with an efficient algorithm (even though I met the Project Euler standard efficiency: 1 minute), so I ended up using sieve, reducing redundancies, and half-cutting the limit in order to meet my personal premise in problem-solving (under 1 second).

Here is my algorithm.

The problem hints us that the limit is 28123, and that the smallest abundant number is 12, and therefore the sum of two abundant numbers is 24.

From now on, I will just call such integers that is the sum of two abundant numbers abby numbers.
(for convenience)

(This term is not a defined mathematical term, so don't use it anywhere else.)

We are going to find the sum of non-abby numbers.

Here is my algorithm for abundant number sieve:

public static boolean[] sieveAbundance(int limit)
{
    boolean[] abun = new boolean[limit + 1];
    for (int i = 12; i <= limit; i++)
    {
        if (!abun[i])
        {
            if (abun[i] = isAbundant(i))
            {
                for (int j = i; j <= limit; j += i)
                    abun[j] = true;
            }
        }
    }
    return abun;
}

Overall similar principle to Sieve of Eratosthenes (problem 10), yet I have one thing to point out.

Once the number is proven to be an abundant number, then its multiples are all abundant numbers.

The proof is simple. If the sum of the proper divisors of a certain number is already greater than itself, then doubling the number will produce twice as much proper divisors for the number (and the sum of the values will definitely exceeds the original number), and the number will clearly be an abundant number.

Next, we need to determine if the number is an abundant number.

public static boolean isAbundant(int n)
{
    int original = n;
    int sum = 1;
 
    if (n % 2 == 0)
    {
        int temp = 1;
        for (int mult = 2; n % 2 == 0; n /= 2, mult *= 2)
            temp += mult;
        sum *= temp;
    }
    for (int i = 3, end = (int)Math.sqrt(n); i <= end; i += 2)
    {
        if (n % i == 0)
        {
            int temp = 1;
            for (int mult = i; n % i == 0; n /= i, mult *= i)
                temp += mult;
            sum *= temp;
            end = (int)Math.sqrt(n);
        }
    }
    if (n != 1) sum *= 1 + n;
    return original + original < sum;
}

In this algorithm, I divided the division part into [2] and [odd numbers].
(By checking the divisibility by 2, I can skip rest of even numbers.)

And the logic behind the algorithm is written here:

Let's say our number is 36. Its proper divisors are 1, 2, 3, 4, 6, 9, 12, 18.

The sum is 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 = 55 > 36. It is an abundant number.

Prime factorization: 36 = 2² x 3².

With 2², we can produce 1, 2, and 4. Let's add them up. 1 + 2 + 4 = 7.

Now, we have 3². We can produce 1, 3, and 9. Let's add them up. 1 + 3 + 9 = 13.

Let's multiply those two sums. 7 * 13 = 91.

91 minus the original number 36 equals 91 - 36 = 55. The sum of the proper divisors.

What?! How could that happen??

Ok, here is the proof.

36	20 (A)	21 (B)	22 (C)
30 (D)	1	2	4
31 (E)	3	6	12
32 (F)	9	18	36

where each un-bolded numbers in the table is the multiplication of two elements.

For example, 18 in the box is the product of 2¹ x 3², or column x row.

Instead of adding all the element manually, we are going to use multiplication of polynomials in order to quickly get the sum of the factors. (including itself)

We want to get AD + AE + AF + BD + BE + BF + CD + CE + CF, which we can factor out into (A + B + C)(D + E + F). And this is (1 + 2 + 4)(1 + 3 + 9) = 91, which I did above.

Because this is the sum of every factor, we need to subtract the original number in order to get the sum of the proper factors.

Last step is to find abby number from the information on abundant numbers we calculated.

Because it tends to have abundant numbers in bigger numbers than small numbers, the algorithm will start finding the abundant pairs from the biggest to smallest. For example, if we want to check if 72 is abby number, we will divide it into half and start with (36, 36) pair, which is more likely than (1, 71) pair.

public static boolean isSumOfTwoAbundant(int n)
{
    for (int i = n / 2; i >= 12; i--)
        if (isAbundant[i] && isAbundant[n - i]) return true;
    return false;
}

and WE ARE FINALLY DONE!

int sum = 0;
for (int i = 1; i <= LIMIT; i++)
{
    if (!isSumOfTwoAbundant(i)) sum += i;
}
System.out.println(sum);

Answer is 4179871
Execution time is 28.948803 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem023.java

Problem 22 : Names Scores

Names scores

Problem 22

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.
What is the total of all the name scores in the file?

                                                                                                       (https://projecteuler.net/problem=22)

Simple problem, simple algorithm, so let's directly get into the solution.

We will read in that 46K files, because I don't want to manually store the five thousand Strings into a giant array... I mean... really....

public static String[] read()
{
    String[] text = new String[5000];
    File file = new File(text022);
    try (BufferedReader br = new BufferedReader(new FileReader(file)))
    {
        String line = br.readLine();
        line = line.replace("\"", "");
        text = line.split(" ");
    }
    catch (IOException e)
    {
        System.err.println(e);
    }
    return text;
}

After that, we sort the array, as the problem stated, in alphabetical order.

I used java.util.Arrays to use the function sort() to put them in order.

If we want to create our own solution for sorting, (and if so, I have to talk about either one of Quicksort, Mergesort, or heapsort, which are considered the fastest sorting algorithms out there), yet most programmers will use the built-in functions to quickly solve the problem.

import java.util.Arrays;

...

public class Problem022 implements textFile.Texts
{
    private static String[] NAME = read();
 
    public static void run()
    {
        Arrays.sort(NAME);
  
        ...
    }
 
}

For each name, we will get the value for each char in the String.

Here, I will use the trick I used in the problem 20, where I used the intrinsic value of the primitive data types stored in Java:

for (int i=0; i < NAME.length; i++)
{
    sum = 0;
    char[] arr = NAME[i].toCharArray();
    for (char c : arr) sum += c - 'A' + 1;
    score += sum * (i+1);
}

The logic behind this algorithm is simple.

The character 'A' will have some value in computer. And character 'B' will also have some value in computer, but no matter what value that is, its value will be 1 bigger than the value of 'A' because the computer stores the values in chronological order.

So value('B') - value('A') = 1.

Because the problem counts the characters from 1 starting with 'A', we will simply add +1 at the end.

(Look at the code above.)

Combined solution:

Arrays.sort(NAME);
  
int score = 0, sum = 0;
  
for (int i=0; i < NAME.length; i++)
{
    sum = 0;
    char[] arr = NAME[i].toCharArray();
    for (char c : arr) sum += c - 'A' + 1;
    score += sum * (i+1);
}
System.out.println(score);

Answer is 871198282
Execution time is 27.967796 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem022.java

Problem 21 : Amicable Numbers

Amicable numbers

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

                                                                                                       (https://projecteuler.net/problem=21)

Kudos to the one who found out amicable numbers!

Studying amicable numbers allows you to explore the deeper side of the nature of numbers, and you will be amazed at their intrinsic properties involving factors.

If we denote that for an amicable pair (m, n):


where

                 

where   is the divisor function.

And therefore we can derive the fact that:

                

(Learn more about amicable numbers.)

As the problem stated, the most well-known amicable pair is (220, 284), as they are the first amicable numbers and the only numbers under 1000.



Let's get into the problem-solving.

The most important function will be finding the sum of the proper divisors.

public static int sumFactor(int n) {...}

As always, we need the base case.

if (n == 0) return 0;

Let's initialize the sum as 1, for the sum of the proper divisors will always be at least 1 (prime numbers will have the sum of the proper divisors of 1):

int sum = 1;

As discussed in the problem 3, our limit for the division will be the square root of the number:

int sqrt = (int) Math.sqrt(n);

Starting with 2, we will check the divisibility and add BOTH the divisor and paired divisors (for example, if 36 is divisible by 3, then we add 3 and its paired divisor 12, or 36 divided by 3):

for (int i = 2; i <= sqrt; i++)
{
    if (n%i == 0) sum += i + n/i;
}

Last step is to check if the number is a perfect square. So if the number is 25, then in the previous step we added 5 twice as the divisor is 5 and its paired divisor is also 5. We need to get rid of this redundancy):

if (n == sqrt*sqrt) sum -= sqrt;

Combined algorithm:

public static int sumFactor(int n)
{
    if (n == 0) return 0;
    int sum = 1;
    int sqrt = (int) Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++)
    {
        if (n%i == 0) sum += i + n/i;
    }
    if (n == sqrt*sqrt) sum -= sqrt;
    return sum;
}

Now, we want to know if the number is amicable number.

The one thing I want to point out is that an amicable pair cannot contain a duplicate number.

For example, 6 has proper divisors of 1,2, and 3, so s(6) = 1 + 2 + 3  = 6.

6 is an "amicable number" of itself, which is against the definition of amicable number.

So we need the condition that a != s(a)

public static boolean isAmicable(int a)
{
    int b = sumFactor(a);
    return (a != b) && (a == sumFactor(b));
}

We are all set! Let's iterate through the integers until we reach 10,000:

int sum = 0;
for (int i = 1; i < 10000; i++)
    if (isAmicable(i)) sum += i;
System.out.println(sum);

Answer is 31626
Execution time is 8.740898 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem021.java

Problem 20 : Factorial Digit Sum

Factorial digit sum

Problem 20

n! means n × (n − 1) × ... × 3 × 2 × 1
For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!

                                                                                                       (https://projecteuler.net/problem=20)

This one looks like a factorial problem, and it is, but more importantly, it is BigInteger again!

Factorial is really fun mathematical operator, as it will make a growth sharper than exponential function after a certain point.

So if you graph the function into a calculator, you will see that:

where red graph is y = e^x exponential graph,
and purple graph is y = x! factorial graph.

If we zoom in closer for 0 < x:

They meet each other at (5.29, 198.406), and after that point, factorial has much greater growth rate.

So, that being said, we definitely need BigInteger to get the value.


Starting with 1, up to 100, we use for-loop to multiply BigInteger values to get factorial 100!:

int ans = 0;
BigInteger num = BigInteger.ONE;
for (int i=1; i <= 100; i++) num = num.multiply(BigInteger.valueOf(i));

Just to let you know, there are default constants of BigInteger.ONE, BigInteger.ZERO, and BigInteger.TEN for convenience; there is multiply() function that you can use for multiplication; and you initialize the value using valueOf() function.

After that, we use the great advantage of Java BigInteger: the fact that it uses String to store the info.

So I will convert the String into char array, and use the char values to get each digit and their sum:

char[] arr = num.toString().toCharArray();
for (char c : arr) ans += c - '0';

System.out.println(ans);

And we will have the answer.

Answer is 648
Execution time is 2.634032 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem020.java

Graph Calculated from: https://www.desmos.com/calculator

Problem 19 : Counting Sundays

Counting Sundays

Problem 19

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 divisible 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)?

                                                                                                       (https://projecteuler.net/problem=19)
Now we are on the problem with calendar counting.

I have always hoped that our current calendar becomes simpler and more uniform (without any confusing leap years and varying month lengths, ... etc), but, whatever.

At least it makes calendar counting problems more fun and exciting, so I'm ok with it now.

We are dating back to January 1st, 1901, when 20^th century began.

Here are some important events in 1901.

Ok. Let's start writing our algorithm.

First method that I want is to determine if the year is leap year or not.

Because leap years are divisible by 4, but centuries don't count, but 400-multiple centuries do count, it seems tedious, and we need several steps.

public static boolean isLeap(int y)

{...}

So first filter is whether the year is multiple of 4; if it is, then that year can be leap year possibly; if not, then no chance.

if (y%4 == 0)
{
    ...
}
return false;

Second, if the year is divisible by 4, then we check if the year is multiple of 400; if it is, then it is a leap year; if not, then we'll see.

if (y%4 == 0)
{
    if (y%400 == 0) return true;
    else ...
}

Third, if the year isn't multiple of 400, then we check if the year is multiple of 100; if it is. then it is not a leap year; if not, it is.

if (y%4 == 0)
{
    if (y%400 == 0) return true;
    else if (y%100 == 0) return false;
    return true;
}

When we combine them:

public static boolean isLeap(int y)
{
    if (y%4 == 0)
    {
        if (y%400 == 0) return true;
        else if (y%100 == 0) return false;
        return true;
    }
    return false;
}

After making that method, I worked on how to easily find out Sundays without using complicated algorithms involving arrays or Strings.

So here is the system that I designed, and it worked perfectly:

S	M	T	W	T	F	S
0	1	2	3	4	5	6

Using divisibility by 7, we can get the reminders from 0-6.

if the day count divided by 7 gives us 1, then we know that it is Monday.

For example, starting with Monday, we want to know what day it is after 24 days.

Because Monday is 1 in the chart, and 1 + 24 = 25, we divide it by 7, and we will get 4 as a reminder.

And 4 is Thursday, according to the chart I made. Ah! It is Thursday after 24 days.

My algorithm is the Modulus Representation of Days (Modulo 7).

From now on, it becomes really easy implementation.

We start with 0 Sunday count, and day 2 (which is Tuesday, according to the chart I made):

int count = 0, day = 2;

Year from 1901 to 2000 and month from 1 to 12:

for (int y = 1901; y <= 2000; y++) // years
{
    for (int m = 1; m <= 12; m++) // months
    {
        ...
    }
    ...
}

If months are April, June, September, and November, there are 30 days always:

if (m == 4 || m == 6 || m == 9 || m == 11)
    day += 30;

If February, then we check leap-year-ity of the year:

else if (m == 2)
{
    if (isLeap(y)) day += 29;
    else day += 28;
}

Rest of the months are 31 days:

else day += 31;

After that, we divide by 7 and get the reminder. If the reminder is 0 on the first day of each month, we know that it is Sunday:

day %= 7;
if (day == 0) count++; // if it is sunday

Combining all that:

int count = 0, day = 2; // modulus representation of days (modulo 7) : SMTWTFS == 0123456
  
for (int y = 1901; y <= 2000; y++) // years
{
    for (int m = 1; m <= 12; m++) // months
    {
        if (m == 4 || m == 6 || m == 9 || m == 11)
            day += 30;
        else if (m == 2)
        {
            if (isLeap(y)) day += 29;
            else day += 28;
        }
        else day += 31;
  
        day %= 7;
        if (day == 0) count++; // if it is sunday
    }
}
System.out.println(count);

Answer is 171
Execution time is .796564 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem019.java