**EDIT 2011.05.09**
Thanks to Junkie and Tapio Rajala for checking on me. While most of the candidates
referred to below have small factors, the "large" small factors I list below are incorrect. Also, that $2^{2557} - 2^{1278} + 1$ does not have a small factor supports my "feeling" that the candidate set should have not so many small factors as I was seeming to find. I apologize for submitting such false suggestions to MathOverflow. (This post will teach me to double check my work before posting, cautious language notwithstandng.) Further updates (if any) will be near the end of this post.
**END EDIT 2011.05.09**

Following this answer to a question of Luis Gallardo, I set my computer to look for small factors. After looking through a lot of primes, my computer suggests that $223381441$ divides $2^{2557} - 2^{1278} + 1$ and that $234355951$ divides $2^{121} - 2^{60} + 1$. The remaining exponent to be cracked is $132049$ (find a nontrivial factor or establish primality of $2^{264097} - 2^{132048} + 1$). Given that the initial candidate set was based on the $47$ known perfect numbers and that the largest of the smallest factors of all but one of them is $2^{37} - 2^{18} + 1$ (meaning that the perfect number with Mersenne exponent $19$ precedes a prime), how can I use this information to determine how likely it is that the remaining candidate has a small ($< 2^{32}$) prime factor?

(If you have a bignum package and want to do a few primality tests, I would receive that information. I would also appreciate independent verification that $42$ of the $47$ candidates are composite with small prime factors. Currently I am using 32-bit arithmetic and the moral equivalent of trial factorization to determine primality of these candidates. In spite of my initial observations that $7$ or $11$ divide most of the candidates, I am surprised at my success so far in finding small prime factors. Or should I be? That is the point of this question.)

(Also, to answer Luis's question, at this point I'd say about four or five.)

**EDIT 2011.07.14**
After running for several weeks, the program I had to find small prime factors finished. The major bug it had involved
roundoff error, and so reported several
factors which turned out not to be factors, including the two reported above and challenged
(and correctly so) by Junkie.

I am independently attempting to check the factorization using the Elliptic Curve Method of $2^{2557} - 2^{1278} + 1$; that's on its 17th day currently after several restarts of the computer doing the calculations.

In addition to Charles's answer below, one can look at Hans Riesel's book *Prime Numbers and Computer Methods for Factorization*. The book has sections on Dickman's Theorem and on the work of Knuth and Trabb-Pardo on how prime factors are distributed according to size.
**END EDIT 2011.07.14**

Gerhard "Ask Me About System Design" Paseman, 2011.05.06

7more comments