You are given a positive integer
$N. Write a script to sum GCD of all possible unique pairs between 1 and
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
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.
» ./ch-1.pl 3 3 » ./ch-1.pl 4 7
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 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.
» ./ch-2.pl [ 6 1 8 ] [ 7 5 3 ] [ 2 9 4 ]