How do you go about solving #2 on pen and paper? Well, calculating the Fibonacci sequence, ok. The sum of prime divisors of X+1, I guess... though it gets slightly harder for me after dividing by 2, 3 and 5. But how do you know for sure that X is prime?
Based on bd's link, I'll just assume that you have super powers. (or I'm approaching the problem the wrong way)
edit: I was starting to think about what to write for #1, but ended finding the answer by looking at it as well.
You can use the Sieve of Eratosthenes to generate primes with pen and paper very easily. Or, you could find a roll of paper and evaluate any computable function (assuming unbounded paper). ;)
It doesn't seem to make it especially easy: you still have the same problem of having to eliminate the multiples of 61, 79, 89, etc. which are not obvious. Yes, you can count, but it looks very time-consuming.
The problem still stands that one needs to go in the 500,000s for that problem (thus 700s for the square root). That's still a long way to go…
I'm really curious about how cperciva did it. You're supposed to find the first Fibonacci prime over 227,000. The first Fibonacci number over that is obviously not prime (multiple of 3), but the one after that is not obvious even if you have the list of primes obtained with that method.
You have less than 30 Fibbonacci numbers to compute.
That 317811 is divisible by 3 is obvious upon adding its digits together.
Once you've verified that 514229 isn't divisible by a handful of small primes, you don't try to prove primality. Instead factor 514230 and stick it in. After dividing by 2, 3, and 5, you've got 17141. It doesn't take that long to run through 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 and 61. At which point you have an answer you can try plugging in to discover it is correct. Which is a sequence cperciva pretty definitely has memorized. (I do.) Or alternately cperciva may have better factorization techniques memorized.
If you already have a routine around for factoring (I do), then this takes longer than coding it. But I could do it with paper and pencil pretty easily.
Fair enough. Though I'd argue on "entirely solvable by pencil and paper", since the answer is an educated guess in that case and the proof that it's correct resides in checking with the webpage. ;-)
To be honest, in the same amount of time, one could also estimate the range where the answer should be and plug it one by one in the form until it validates. (which we'll call a less educated guess :))
Based on bd's link, I'll just assume that you have super powers. (or I'm approaching the problem the wrong way)
edit: I was starting to think about what to write for #1, but ended finding the answer by looking at it as well.