# TASK #1 › GCD Sum

## Task

You are given a positive integer `$N`

. Write a script to sum GCD of all possible unique pairs between 1 and `$N`

.

## My solution

This is relatively straight forward. All possible unique pairs can be calculated with the first number from 1 to `$N`

- 2, and the second number one more than the first number to `$N`

.

It's then a matter of calculating the GCD for this combination. For this I have a subroutine `_gcd`

that takes the minimum of the two numbers and work backwards to one. It will return the first value that can be divided by both numbers with no remainder.

## Examples

```
» ./ch-1.pl 3
3
» ./ch-1.pl 4
7
```

# TASK #2 › Magical Matrix

## Task

Write a script to display matrix as below with numbers 1 - 9. Please make sure numbers are used once.

`[ a b c ]`

[ d e f ]

[ g h i ]

So that it satisfies the following:

`a + b + c = 15`

d + e + f = 15

g + h + i = 15

a + d + g = 15

b + e + h = 15

c + f + i = 15

a + e + i = 15

c + e + g = 15

## My solution

My first thought was to just brute force this. The possible permutation is 9! = 362880, and even a half decent computer could figure this out pretty quickly.

But I took a slight different approach to make it even faster.

- Work out all the possible ordered three digit combinations that sum to 15. It turns out there are only eight combinations: 1 5 9, 1 6 8, 2 4 9, 2 5 8, 2 6 7, 3 4 8, 3 5 7, 4 5 6
- Using these rows, work out all combinations of these rows such that all numbers are used. There are twelve rows returned.
- This now means the possible solutions are 6³ × 12 (2,592). We know that we won't need all of these. For example, the 1 will always be found in top left, top middle or centre position (all other places will be a mirror/flip of one of these).
- At this point, I just use a brute force approach until I find a solution.
- Each row can be ordered one of six ways (abc, acb, bac, bca, cab, cba).
- For each of the twelve solutions, we can cycle through the six numbers combinations in each row.
- If a solution is found that meets the requirements, we print the solution and exit.

I'm looking forward to seeing how other Team PWC members tackle this task.

## Examples

```
» ./ch-2.pl
[ 6 1 8 ]
[ 7 5 3 ]
[ 2 9 4 ]
```

## Top comments (1)

It seems I've overthought the second task, and not for the first time. James Smith's solution is a work of beauty. And much more efficient too.