The divisors of 12 are: 1,2,3,4,6 and 12.
The largest divisor of 12 that does not exceed the square root of 12 is 3.
We shall call the largest divisor of an integer n that does not exceed the square root of n the pseudo square root (PSR) of n.
It can be seen that PSR(3102)=47.

Let p be the product of the primes below 190.
Find PSR(p) mod 10^{16}.

I had something much more modest in mind, such as “all primes below 100”, since the way I figured it out this was to be solved treating it as a variation of the knapsack problem and then using dynamic programming on it. An approach that will see you die of old age if you try it for the proposed value…

But I then had the pleasure of witnessing how xan, hk and daniel.is.fischer started coming up with alternative, much more sophisticated and elegant methods, that pushed the question all the way up to were it is now. It is both a humbling and edifying experience to see these people at work, so if you have an idea for a problem, do propose it to them.

I won’t go into any more details as to how to solve this particular problem: the right place to ask questions is here.

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Monday, November 30th, 2009 at 19:12 and is filed under number theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

With all my respect: Sergeant Fdez, you´re a fucking looser.

Come back to the trenches and leave the comfort of home…