Given that x is a square number and p is a prime number, and they satisfy the equation x = 1000000007p + 1. Find the sum of all possible values of p.Answer: 1000000009 Mathematical approach
Since x is a square number, we let x = n2, where n is a positive integer. Now we haven2 = 1000000007p + 1 ( n + 1 ) ( n - 1 ) = 1000000007p It is easy to check that 1000000007 is a prime number either by writing a program or using some online tools. Therefore there are only two possibilities: We have p = 1000000005 or 1000000009, but only 1000000009 is a prime, so our answer is 1000000009. Programming approach
It is not quite possible to solve this problem directly by brute force programming, as the question gives a very large number 1000000007, and also asked for the sum of possible values (though there is actually only one possible value :p). However even if you are not able to think of the mathematical solution as shown above, you may still have a chance to find out the answer. Let me show you how:-You may think that there must be something special with the number 1000000007. Just use some online tools to analyze this number and you will find that it is a prime. However the number is too large! Let's try to replace the number by some smaller primes, such as 23, 29, 31, ... Write a program to search for possible values of p that fits our equation. There is no upper bound for the value of p so you can let the program run for several minutes for each case and then stops it. You should observe that the number of possible values of p in each case is either p - 2 or p + 2. Now we have found out the key without the use of mathematical skills! Winners
Among 24 participants, there are 15 people who got the correct answers. Thank you for you...