PWC 393 Triangles and Primes

A couple of quick mathematical tasks for this week's challenges.

Task 1: Pythagoras Multiplied

Task Description

You are given a positive integer n. Find the number of all positive integer triplets (a,b,c) so that a² + b² = c² and a, b, and c are integers <= n.

• Example 1: n=20 --> 12

  • (3,4,5),(4,3,5),(5,12,13),(6,8,10),(8,6,10),(8,15,17),(9,12,15),(12,5,13),(12,9,15),(12,16,20),(15,8,17),(16,12,20)

• Example 2: n=7 --> 2

• Example 3: n=1 --> 0

• Example 4: n=15 --> 8

• Example 5: n=30 --> 22

Task Discussion

We notice from Example 1 that order matters: (3,4,5) is counted as distinct from (4,3,5).

We know from the geometry of right triangles that there are no integer solutions where a=b (an equilateral right triangle has hypotenuse sqrt(2)*a), so all valid triples will have a≠b≠c.

I'm going to start by using brute force, and then thinking about optimizing. For every c from 1 to n, there is a target hypotenuse c². Check every pair of a and b from 1 to n.

First optimization: the first possible triple is (3,4,5), so there's no need to check for c less than 5.

Second optimization: if (a,b,c) works, then so does (b,a,c). No need to check every combination of a and b, just the distinct pairs.

Third optimization: no need to iterate every value of a from 1 to n.

• The minimum value of a is 3, because we know that the first valid triple is (3,4,5).
• We know that as a increases, b must decrease, so that the maximum value of a implies the minimum value of b.
• b will iterate over values greater than a, so the minimum that b can ever be is 4.
• We know that a = sqrt(c² - b²), so the upper bound on a can be floor(sqrt(c² - 16)).

Fourth optimization: no need to iterate every value of b either. The values of b will start from a+1, and increment until the sum exceeds c². We know that b = sqrt(c² - a²), so that can be the bound for any given c and a.

Task Solution

sub task($n)
{
    my $count = 0;

    for my $c ( 5 .. $n )
    {
        for my $a ( 3 .. floor(sqrt( $c*$c - 16 )) )
        {
            for my $b ( $a+1 .. floor(sqrt($c*$c - $a*$a)) )
            {
                if ( $a*$a + $b*$b == $c*$c )
                {
                    # If a,b works, then so does b,a
                    $count += 2;
                }
            }
        }
    }
    return $count;
}

Task 2: Prime Step

Task Description

You are given a string with English alphabetic characters only. What is the absolute difference of the sum of the ASCII values of the characters in the string to the nearest prime number?

• Example 1: Input: $str = "hello" Output: 9

  • The ordinal values of "hello" are [104,101,108,108,111], summing up to 532. The nearest prime number to 532 is 523, resulting in an absolute difference of 9.

• Example 2: Input: $str = "football" Output: 2

  • Starting with the values [102,111,111,116,98,97,108,108] and the sum 841. We find 839 as the nearest prime number, so the difference is 2.

• Example 3: Input: $str = "a" Output: 0

  • The value of "a" is 97, which is a prime number.

• Example 4: Input: $str = "challenge" Output: 2

  • The ordinal values of "challenge" are [99, 104, 97, 108, 108, 101, 110, 103, 101], which sum up to 931. The nearest prime number to 931 is 929, so the difference is 2.

• Example 5: Input: $str = "perl" Output: 2

  • The ordinal values of "perl" are [112, 101, 114, 108], summing up to 435. Nearest prime is 433, so the difference is 2.

Task Discussion

There are several little sub-problems in this task, but all of them have solutions in Perl libraries. Notably, finding the nearest prime efficiently is probably an interesting problem in number theory and computation, but I'm not going to solve it as a side quest.

Task Solution

sub task($str)
{
    use List::Util qw/sum0 min/;
    use Math::Prime::Util qw/is_prime prev_prime next_prime/;

    my $s = sum0 map { ord($_) } split //, $str;

    if ( is_prime($s) )
    {
        return 0;
    }
    else
    {
        my $p = prev_prime($s);
        my $n = next_prime($s);
        return min( $s-$p, $n-$s );
    }
}

The Perl knowledge required is:

• An ord() function exists that gives the ASCII value of English letters.
• Library functions exist to sum a list and find the minimum of a list.
• A CPAN module exists for finding prime numbers.

The possibly confusing line that does most of the work evaluates from right to left

my $s = sum0 map { ord($_) } split //, $str;

• split //, $str -- change string into an array of individual characters
• map { ord($_) } -- transform each character into its ASCII value
• sum0 -- add the ordinal values, returning zero if the list is empty

The rest is calls to subroutines in Math::Prime::Util.