COMP9021 Lab 3 Solution

1 Finding particular sequences of prime numbers
Write a program that finds all sequences of 6 consecutive prime 5-digit numbers, so of the form (a,b,c,d,e,f) with b = a + 2, c = b + 4, d = c + 6, e = d + 8, and f = e + 10. So a, b, c, d and e are all 5-digit prime numbers and no number between a and b, between b and c, between c and d, between d and e, and between e and f is prime.
The expected output is:
The solutions are:
13901 13903 13907 13913 13921 13931
21557 21559 21563 21569 21577 21587
28277 28279 28283 28289 28297 28307
55661 55663 55667 55673 55681 55691
68897 68899 68903 68909 68917 68927
2 R Decoding a multiplication
Write a program that decodes all multiplications of the form
* * *x * *
----------
* * * *
* * *
----------
* * * *
such that the sum of all digits in all 4 columns is constant.
The expected output is:
411 * 13 = 5343, all columns adding up to 10.
425 * 23 = 9775, all columns adding up to 18.
3 R Finding particular sequences of triples
Write a program that finds all triples of positive integers (i,j,k) such that i, j and k are two digit numbers, no digit occurs more than once in i, j and k, and the set of digits that occur in i, j or k is equal to the set of digits that occur in the product of i, j and k.
The expected output is:
20 x 79 x 81 = 127980
21 x 76 x 80 = 127680
28 x 71 x 90 = 178920
31 x 60 x 74 = 137640
40 x 72 x 86 = 247680
46 x 72 x 89 = 294768
49 x 50 x 81 = 198450
56 x 87 x 94 = 457968
Consider writing two versions: one that uses the builtin set operator, and one that uses bitwise operators. So for instance, with respect to the solution 20 × 79 × 81 = 127980,
• one version would build the sets {0,2}, {0,2,7,9}, {0,1,2,7,8,9}, verify that they are of respective sizes 2, 4 and 6, and verify that the latter is equal to the set of digits occurring in the product, 127980;
• another version would build the integers 20 +22, 20 +22 +27 +29, 20 +21 +22 +27 +28 +29, verify that the number of bits set to 1 in these integers is equal to 2, 4 and 6, respectively, and verify that the set of bits set to 1 in the third of these three integers is equal to the set of bits set to 1 in the product, 127980.
4 Decoding a sequence of operations
Write a program that finds all possible ways of inserting + and - signs in the sequence 123456789 (at most one sign before any digit) such that the resulting arithmetic expression evaluates to 100. Here are a few hints.
• 1 can either be preceded by -, or optionally be preceded by +; so 1 starts a negative or a positive number.
• All other digits can be preceded by - and start a new number to be subtracted to the running sum, or be preceded by + and start a new number to be added to the running sum, or not be preceded by any sign and be part of a number which it is not the leftmost digit of. That gives 38 possibilities for all digits from 2 to 9. We can generate a number N in [0,38 − 1]. Then we can:
– consider the remainder division of N by 3 to decide which of the three possibilities applies to 2;
– consider the remainder division of N3 by 3 to decide which of the three possibilities applies to 3;
– consider the remainder division of 3N2 by 3 to decide which of the three possibilities applies to 4; – ...
The expected output is (the ordering could be different):
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
123 + 45 - 67 + 8 - 9 = 100
123 + 4 - 5 + 67 - 89 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
123 - 45 - 67 + 89 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
-1 + 2 - 3 + 4 + 5 + 6 + 78 + 9 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
Consider writing two versions: one that generates and evaluates the expression on the left hand side of the equality “by hand”, and one that generates and evaluates the expression on the left hand side of the equality using the builtin eval() function.