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