Loading web-font TeX/Main/Regular

Problem #240

Sieve of Pi-thagoras

Everybody knows the Sieve of Eratosthenes, but does anyone know the Sieve of Pi-thagoras? In the following pseudocode, assume that “real” represents a real number with infinite precision.

Bunty is a kid living in the year 3019. He has access to computation power so immense that he can run this code for as large an integer as possible. You challenge Bunty to find a finite integer input n so that it returns at least r. Deep down, based on your math skills, you know that this isn’t possible for any r \ge r_0. You are required to find [10^{18} \times r_0] modulo 10^9 + 7, where [x] denotes the integral part of x.

"^" in the code implies the power operator.

Contributed by Parth Kohli

Solved by 37 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.