I have a whimsical challenge for you: come up with problems with numerical solutions that are hard to estimate.

This, like surprisingly many things, originates from a Richard Feynman story:

One day I was feeling my oats. It was lunch time in the technical area, and I don't
know how I got the idea, but I announced, "I can work out in sixty seconds the answer to
any problem that anybody can state in ten seconds, to 10 percent!"
People started giving me problems they thought were difficult, such as integrating
a function like 1/(1 + x 4 ), which hardly changed over the range they gave me. The hardest
one somebody gave me was the binomial coefficient of x 10 in (1 + x) 20 ; I got that just in
time.
They were all giving me problems and I was feeling great, when Paul Olum
walked by in the hall. Paul had worked with me for a while at Princeton before coming
out to Los Alamos, and he was always cleverer than I was.

..

So Paul is walking past the lunch place and these guys are all excited. "Hey,
Paul!" they call out. "Feynman's terrific! We give him a problem that can be stated in ten
seconds, and in a minute he gets the answer to 10 percent. Why don't you give him one?"
Without hardly stopping, he says, "The tangent of 10 to the 100th."
I was sunk: you have to divide by pi to 100 decimal places! It was hopeless.

(From Surely You're Joking Mr. Feynman section "Lucky Numbers")

So what would you ask Richard Feynman to solve? Think of this as the reverse of Fermi Problems.

Number theory may be a rich source of possibilities here; many functions there are wildly fluctuating, require prime factorization and depend upon the exact value of the number rather than it's order of magnitude. For example, I challenge you to compute the largest prime factor of 650238.

(My original example was: "For example, I challenge you to compute the greatest common denominator of 10643 and 15047 without a computer. This problem has the nice advantage of being trivial to make harder to compute - just throw in some extra primes." It has been pointed out that I forgot Euclid's algorithm and have managed to choose about the only number theoretic question that does have an efficient solution.)