The problem of the two sages. Computer program for solving
The problem of the two wise men has been appearing in various forums for many years and is constantly renewing interest. I recall the condition:
A ready-made computer program that allows solving such problems for any given maximum number could not be found. Therefore, I decided to write a similar program myself. The solution algorithm will be described on the example of the classical problem for the maximum number equal to 100.
From this it follows that this product cannot be uniquely represented as a product of two numbers. There are at least several ways to get this product with other pairs of numbers, and these numbers must satisfy the condition that they are both less than 100. In the future we will call a product that can be presented in only one way unique.
From this statement, we can conclude about some properties of these numbers. First, they cannot both be simple at the same time, otherwise their product is unique and is represented only as a product of these two prime numbers. This condition is a necessary, but not sufficient condition for the uniqueness of the work. In the future, we will discover other unique products that are not the product of two prime numbers.
The sum of two numbers S, can be represented by a pair of numbers in different ways: 2 + (S - 2), 3 + (S - 3), etc.
')
This statement tells us that none of these pairs of numbers, when multiplied by each other, provides a unique product. Let us try to determine which sums of two numbers have such properties, i.e. we will make the list of possible candidates for the sums of two numbers.
First, as we have already shown, two numbers cannot be both prime, therefore their sum cannot be the sum of two prime numbers. So, a computer program, first calculates a list of all primes that are less than the specified maximum number. Further, it finds all possible sums that can be obtained by these simple numbers and excludes them from further research. As a result, we get the first approximation - the possible amounts:
11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 103 105 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 174 175 177 179 181 182 183 184 185 187 188 189 190 191 192 193 195 196
In principle, we could immediately check all these possible amounts for uniqueness. Those. for each sum we compose all possible pairs of numbers and check the product of these numbers for uniqueness. If at least one pair of numbers, for the sum under study, gives a unique product, then this sum is deleted from possible candidates. This routine for checking the uniqueness of a work is the most difficult part of the entire program. Many who tried to create a similar program simply forgot about it and did not get the correct results.
At the beginning of this subprogram, the work under study is divided into simple factors, then a list of all possible products that can be obtained from these simple factors is compiled - this is the first factor. The second factor is obtained by dividing the product by the first factor and checking only the options when the first factor is less than the second. Then both factors are checked to see if they satisfy the condition of the problem (both are less than the maximum number 100, or their sum is less than Max). So we get the permissible decompositions of a work into two factors, and if there is only one such decomposition, then this product is unique.
But before we start checking for uniqueness, we will simplify the task in order not to load the computer with unnecessary calculations. We use a not very obvious property - what amount can be the maximum.
If the product under investigation has a prime number greater than 50 (more than half of Max, in our case, this prime number is 53), then this product is unique. Since when we try to get the second version of the decomposition, we must at least multiply 53 by 2 and we get a factor greater than 100.
For any sum S, greater than 53 + 2, we can find a pair of numbers 53 and S - 53 and the product of these numbers will be unique. From here we conclude that all amounts greater than 55 can be excluded from further calculations.
This narrows the search to 11 possible amounts:
11 17 23 27 29 35 37 41 47 51 53
Now we make a check for the uniqueness of the product of all possible pairs of numbers. The program displays unique works with a negative sign.
1: X + Y = 11, X * Y =: 18 24 28 30
2: X + Y = 17, X * Y =: 30 42 52 60 66 70 72
3: X + Y = 23, X * Y =: 42 60 76 90 102 112 120 126 130 132
4: X + Y = 27, X * Y =: 50 72 92 110 126 140 152 162 170 176 180 182
5: X + Y = 29, X * Y =: 54 78 100 120 138 154 168 180 190 198 204 208 210
6: X + Y = 35, X * Y =: 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306
7: X + Y = 37, X * Y =: 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342
8: X + Y = 41, X * Y =: 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420
9: X + Y = 47, X * Y =: 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552
10: X + Y = 51, X * Y =: 98 144 188 230 270 308 344 378 410 440 468 494 518 540 560 -578 594 608 620 630 638 644 648 650
11: X + Y = 53, X * Y =: 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702
One unique piece is found - 578 = 2 * 17 * 17. Indeed, this number can be represented only in one way - 17 * 34, the second method 2 * 289, does not satisfy the condition - both numbers are less than 100.
So the sum of 51 also removes their possible candidates, leaving only 10 allowable amounts.
By the way, thanks to the program, you can easily find the following simple rule how to detect unique pieces.
If the product has the form 2 * P * P, where P is a prime number whose square is greater than the maximum number (100), then this product is unique and it corresponds to the sum of two numbers P and 2 * P and this sum is equal to 3 * P.
So we can cross out all sums that are equal to 3 * P, where P is a prime number greater than 10. In our case, this sum is 51 = 3 * 17.
Further work with the program revealed other interesting rules for unique works ...
So, after the first two cues of the sages, the first sage knows that the sum of two numbers can only be one of 10 numbers:
11 17 23 27 29 35 37 41 47 53
In which case, Ali can uniquely determine which pair of numbers to decompose his work? On that pair of numbers, the sum of which is equal to one of these 10 sums, and only one pair of numbers has the sum of this set. From the point of view of a computer algorithm, those works that occur more than once should be deleted. For example, the product 30 occurs twice - for sum 11 and for sum 17. If Ali had said the number 30, he would have found that two pairs of numbers satisfy the conditions of the problem: 5, 6 (sum 11) and 2, 15 (sum 17 ) and he could not unequivocally say - I know these numbers. This means all duplicate works are deleted. As a result, we get the following picture - all admissible amounts and all admissible products for these amounts:
1: X + Y = 11, X * Y =: 18 24 28
2: X + Y = 17, X * Y =: 52
3: X + Y = 23, X * Y =: 76 112 130
4: X + Y = 27, X * Y =: 50 92 110 140 152 162 170 176 182
5: X + Y = 29, X * Y =: 54 100 138 154 168 190 198 204 208
6: X + Y = 35, X * Y =: 96 124 174 216 234 250 276 294 304 306
7: X + Y = 37, X * Y =: 160 186 232 252 270 336 340
8: X + Y = 41, X * Y =: 114 148 238 288 310 348 364 378 390 400 408 414 418
9: X + Y = 47, X * Y =: 172 246 280 370 442 480 496 510 522 532 540 550 552
10: X + Y = 53, X * Y =: 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702
After the third replica, Vali did all the computational work as we did and discarded all repetitive works. And he can uniquely identify numbers only when, for his sum, only one product remains valid. From the point of view of a computer, only one permissible work remains in one line. In our case, this is a product of 52 for the sum of 17, which corresponds to a pair of numbers 4, 13. This solution is the only one.
My computer program allows you to get the result of the problem for any value of the maximum number.
There are various variations of this task:
- both numbers are less than the specified;
- the sum of the numbers is less than the specified maximum number;
- numbers may be the same;
- numbers are necessarily different;
The program allows you to calculate the result for all these variations.
The program can display intermediate results for each stage of calculations.
It is also possible to calculate all the boundary points at which new solutions appear for the specified range of numbers. For example, if you scan all numbers up to 2000, we get the following result:
Result for Max = 10
No result
Result for max = 63
1: X = 4, Y = 13
Result for max = 867
1: X = 4, Y = 13
2: X = 4, Y = 61
Result for Max = 1503
1: X = 4, Y = 13
2: X = 4, Y = 61
3: X = 32, Y = 131
Result for Max = 1967
1: X = 4, Y = 13
2: X = 4, Y = 61
3: X = 16, Y = 73
4: X = 32, Y = 131
End of calculations. Calculation time: 0:00:29
It can be seen that solution 4, 13 is unique in the range from 63 to 866.
By the way, the task published in the journal “Science and Life” does not have a solution at all, since there was a condition that the numbers are less than 60. I can imagine how long readers have been trying to solve the problem, but it does not have the correct solution ...
Ready to put the program listings and the program itself (written in Delphi), if possible.
Some sultan had two wise men: Ali-ibn-Vali and Vali-ibn-Ali. Wanting to be convinced of their wisdom, the Sultan called the wise men to him and said: “I planned two numbers. Both are whole, each is greater than one, but less than a hundred. I multiplied these numbers and the result will tell Ali and at the same time Vali I will say the sum of these numbers. If you really are as wise as they say about you, you can find out the original numbers. ”
Sultan said Ali the work, and Vali - the amount. Wise men thought. The first to break the silence of Ali.
“I don’t know these numbers,” he said, lowering his head.
“I knew that,” said Vali.
“Then I know these numbers,” rejoiced Ali.
- Then I know! Exclaimed Vali.
And the wise men informed the amazed Sultan of the numbers that he had intended.
Call these numbers.
A ready-made computer program that allows solving such problems for any given maximum number could not be found. Therefore, I decided to write a similar program myself. The solution algorithm will be described on the example of the classical problem for the maximum number equal to 100.
1. I do not know these numbers, said the sage, who knows the product of two numbers
From this it follows that this product cannot be uniquely represented as a product of two numbers. There are at least several ways to get this product with other pairs of numbers, and these numbers must satisfy the condition that they are both less than 100. In the future we will call a product that can be presented in only one way unique.
From this statement, we can conclude about some properties of these numbers. First, they cannot both be simple at the same time, otherwise their product is unique and is represented only as a product of these two prime numbers. This condition is a necessary, but not sufficient condition for the uniqueness of the work. In the future, we will discover other unique products that are not the product of two prime numbers.
2. I knew this, said the sage, who knows the sum of two numbers
The sum of two numbers S, can be represented by a pair of numbers in different ways: 2 + (S - 2), 3 + (S - 3), etc.
')
This statement tells us that none of these pairs of numbers, when multiplied by each other, provides a unique product. Let us try to determine which sums of two numbers have such properties, i.e. we will make the list of possible candidates for the sums of two numbers.
First, as we have already shown, two numbers cannot be both prime, therefore their sum cannot be the sum of two prime numbers. So, a computer program, first calculates a list of all primes that are less than the specified maximum number. Further, it finds all possible sums that can be obtained by these simple numbers and excludes them from further research. As a result, we get the first approximation - the possible amounts:
11 17 23 27 29 35 37 41 47 51 53 57 59 65 67 71 77 79 83 87 89 93 95 97 103 105 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 174 175 177 179 181 182 183 184 185 187 188 189 190 191 192 193 195 196
In principle, we could immediately check all these possible amounts for uniqueness. Those. for each sum we compose all possible pairs of numbers and check the product of these numbers for uniqueness. If at least one pair of numbers, for the sum under study, gives a unique product, then this sum is deleted from possible candidates. This routine for checking the uniqueness of a work is the most difficult part of the entire program. Many who tried to create a similar program simply forgot about it and did not get the correct results.
At the beginning of this subprogram, the work under study is divided into simple factors, then a list of all possible products that can be obtained from these simple factors is compiled - this is the first factor. The second factor is obtained by dividing the product by the first factor and checking only the options when the first factor is less than the second. Then both factors are checked to see if they satisfy the condition of the problem (both are less than the maximum number 100, or their sum is less than Max). So we get the permissible decompositions of a work into two factors, and if there is only one such decomposition, then this product is unique.
But before we start checking for uniqueness, we will simplify the task in order not to load the computer with unnecessary calculations. We use a not very obvious property - what amount can be the maximum.
If the product under investigation has a prime number greater than 50 (more than half of Max, in our case, this prime number is 53), then this product is unique. Since when we try to get the second version of the decomposition, we must at least multiply 53 by 2 and we get a factor greater than 100.
For any sum S, greater than 53 + 2, we can find a pair of numbers 53 and S - 53 and the product of these numbers will be unique. From here we conclude that all amounts greater than 55 can be excluded from further calculations.
This narrows the search to 11 possible amounts:
11 17 23 27 29 35 37 41 47 51 53
Now we make a check for the uniqueness of the product of all possible pairs of numbers. The program displays unique works with a negative sign.
1: X + Y = 11, X * Y =: 18 24 28 30
2: X + Y = 17, X * Y =: 30 42 52 60 66 70 72
3: X + Y = 23, X * Y =: 42 60 76 90 102 112 120 126 130 132
4: X + Y = 27, X * Y =: 50 72 92 110 126 140 152 162 170 176 180 182
5: X + Y = 29, X * Y =: 54 78 100 120 138 154 168 180 190 198 204 208 210
6: X + Y = 35, X * Y =: 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306
7: X + Y = 37, X * Y =: 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340 342
8: X + Y = 41, X * Y =: 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408 414 418 420
9: X + Y = 47, X * Y =: 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510 522 532 540 546 550 552
10: X + Y = 51, X * Y =: 98 144 188 230 270 308 344 378 410 440 468 494 518 540 560 -578 594 608 620 630 638 644 648 650
11: X + Y = 53, X * Y =: 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612 630 646 660 672 682 690 696 700 702
One unique piece is found - 578 = 2 * 17 * 17. Indeed, this number can be represented only in one way - 17 * 34, the second method 2 * 289, does not satisfy the condition - both numbers are less than 100.
So the sum of 51 also removes their possible candidates, leaving only 10 allowable amounts.
By the way, thanks to the program, you can easily find the following simple rule how to detect unique pieces.
If the product has the form 2 * P * P, where P is a prime number whose square is greater than the maximum number (100), then this product is unique and it corresponds to the sum of two numbers P and 2 * P and this sum is equal to 3 * P.
So we can cross out all sums that are equal to 3 * P, where P is a prime number greater than 10. In our case, this sum is 51 = 3 * 17.
Further work with the program revealed other interesting rules for unique works ...
So, after the first two cues of the sages, the first sage knows that the sum of two numbers can only be one of 10 numbers:
11 17 23 27 29 35 37 41 47 53
3. Then I know these numbers, - Ali was delighted.
In which case, Ali can uniquely determine which pair of numbers to decompose his work? On that pair of numbers, the sum of which is equal to one of these 10 sums, and only one pair of numbers has the sum of this set. From the point of view of a computer algorithm, those works that occur more than once should be deleted. For example, the product 30 occurs twice - for sum 11 and for sum 17. If Ali had said the number 30, he would have found that two pairs of numbers satisfy the conditions of the problem: 5, 6 (sum 11) and 2, 15 (sum 17 ) and he could not unequivocally say - I know these numbers. This means all duplicate works are deleted. As a result, we get the following picture - all admissible amounts and all admissible products for these amounts:
1: X + Y = 11, X * Y =: 18 24 28
2: X + Y = 17, X * Y =: 52
3: X + Y = 23, X * Y =: 76 112 130
4: X + Y = 27, X * Y =: 50 92 110 140 152 162 170 176 182
5: X + Y = 29, X * Y =: 54 100 138 154 168 190 198 204 208
6: X + Y = 35, X * Y =: 96 124 174 216 234 250 276 294 304 306
7: X + Y = 37, X * Y =: 160 186 232 252 270 336 340
8: X + Y = 41, X * Y =: 114 148 238 288 310 348 364 378 390 400 408 414 418
9: X + Y = 47, X * Y =: 172 246 280 370 442 480 496 510 522 532 540 550 552
10: X + Y = 53, X * Y =: 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696 700 702
4. Then I know! - Vali exclaimed
After the third replica, Vali did all the computational work as we did and discarded all repetitive works. And he can uniquely identify numbers only when, for his sum, only one product remains valid. From the point of view of a computer, only one permissible work remains in one line. In our case, this is a product of 52 for the sum of 17, which corresponds to a pair of numbers 4, 13. This solution is the only one.
My computer program allows you to get the result of the problem for any value of the maximum number.
There are various variations of this task:
- both numbers are less than the specified;
- the sum of the numbers is less than the specified maximum number;
- numbers may be the same;
- numbers are necessarily different;
The program allows you to calculate the result for all these variations.
The program can display intermediate results for each stage of calculations.
It is also possible to calculate all the boundary points at which new solutions appear for the specified range of numbers. For example, if you scan all numbers up to 2000, we get the following result:
Result for Max = 10
No result
Result for max = 63
1: X = 4, Y = 13
Result for max = 867
1: X = 4, Y = 13
2: X = 4, Y = 61
Result for Max = 1503
1: X = 4, Y = 13
2: X = 4, Y = 61
3: X = 32, Y = 131
Result for Max = 1967
1: X = 4, Y = 13
2: X = 4, Y = 61
3: X = 16, Y = 73
4: X = 32, Y = 131
End of calculations. Calculation time: 0:00:29
It can be seen that solution 4, 13 is unique in the range from 63 to 866.
By the way, the task published in the journal “Science and Life” does not have a solution at all, since there was a condition that the numbers are less than 60. I can imagine how long readers have been trying to solve the problem, but it does not have the correct solution ...
Ready to put the program listings and the program itself (written in Delphi), if possible.
Source: https://habr.com/ru/post/257809/
All Articles