$0.22654 4.28%
STEEM · 196w

[Answer and Winners] Mathematics × Programming Competition #6 [答案及得獎名單] 數學 × 程式編寫比賽 (第六回)

Mathematics × Programming Competition #6Announcement of Answer and Winners Designed by @nicolemoker For Chinese version please scroll to the bottom. 中文版請見文末。 Question

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 have

n2 = 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...

Continue on
Recent news
No posts found