Matsuzaki Number
Time limit8sMemory limit512 MB
For each query N and P, list all sums of two primes greater than N (with repetition, duplicates counted separately) in increasing order and report the P-th sum, where P is at most 100.
- Level
Medium6 of 10
- Topics
- Number theory, Math, Sorting, Brute force
- Solved
- No attempts yet
Problem
Professor Matsuzaki is a scientist who studies the truth of the universe. People say the answer to life, the universe, and everything is 42, but Professor Matsuzaki thinks that is not enough to explain the truth of the universe. He believes the truth of the universe is expressed by a function of two parameters, and that 42 is only one of them.
The function M(N, P) defined by Professor Matsuzaki gives the number that appears in the P-th position when all numbers obtainable as the sum of two primes greater than N (the two primes may be equal) are listed in increasing order. Some numbers can be written as such a sum in more than one way, and each way is listed separately.
Take N = 0 as an example. Here the two primes are chosen from all primes. Since the same prime may be chosen twice, the smallest such sum is 2 + 2 = 4, so M(0, 1) = 4. The next smallest is 2 + 3 = 5, so M(0, 2) = 5. Continuing this way, the sums listed in order are 4, 5, 6, 7, 8, 9, 10, 10, 12, 13, 14, 14, 16, ... . For instance, M(0, 9) = 12.
Similarly, for N = 10 the two primes are chosen from the primes greater than 10, {11, 13, 17, 19, ...}, and the resulting sums in increasing order are 22, 24, 26, 28, 30, 30, 32, ... .
Your task is to write a program that computes M(N, P) given N and P.
Input
The input consists of multiple data sets. Each data set is one line containing two integers N (0 ≤ N ≤ 100,000) and P (1 ≤ P ≤ 100) separated by a single space.
The end of the input is indicated by a line containing two -1s separated by a space.
Output
For each data set, output the value of M(N, P) on one line. Do not include extra spaces or line breaks in the output.