At this year's state mental math competition, contestants will be given a prime number p<10,000 of the form 4k+1 and will be asked to find an integer x such that x²+1 is divisible by p, in less than 10 minutes. Each contestant will also be given access to two oracles:

Oracle 1: When given any integer n, outputs n².

Oracle 2: When given any integers m,n not divisible by p, outputs a number k such that kn-m is divisible by p. (In math-speak, this outputs m/n (mod p).)

Each oracle takes 1 second to respond.

You are going to enter this competition, but unfortunately, you are not great at mental math. In fact, all you know how to do in your head is add and subtract numbers. Furthermore, it takes you one second to perform such an operation.

Of course, you can also perform the most basic comparison operations in your head (m<n?, m>n?, m=n?). These also take you one second to perform.

Fortunately, you have a good short term memory, so you can keep track of and instantly access as many numbers in your head as you would like. Trying to fill your memory before the competition will be problematic, however, as your long term memory is bad.

How can you ensure success at this competition?

(In reply to Possible solution, maybe? by Alexis)

First I see that I wrote several mistakes.  The maximum n you can reach is 146, not 145.  Also, since p is prime, it is also divisible by p (well, duh).  Therefore the maximum n value the program would need is 99.859901862559428413569288712076 (square root of 9972).  So 100 iterations are needed.

OK, it also seems as though I did not take into consideration the time it takes to add and substract to the value of n.  No biggie.  Since the program only goes up to n=101 (100 iterations) maximum, then possibly moving down a step, the total amount of iterations are 102, at 5 secs each.

The answer is actually 510 seconds.

I told ya to bear with me ;)

I don't think this is a correct answer, though, since using this method most X values are decimal values, and the program only runs with whole numbers.  Hmm...  Can anyone clarify the actual solution for me?  I read it and can't understand it...

Posted by Alexis on 2005-10-30 10:31:13