View Single Post
Old 2011-03-04, 20:53   #21
R.D. Silverman
R.D. Silverman's Avatar
"Bob Silverman"
Nov 2003
North of Boston

23×937 Posts

Originally Posted by sascha77 View Post
Thanks !!!
Yes it could be that there exist a counterexample.
But nobody knows this until it is found. ;-)
A hint: You only need to test a and b to the size of p.
this means: test a for a<=p and b for b<=p
Because of the modulo-operation these values of 2^a repeat after p-steps.
You are looking at the intersection of two sparse sets (false witnesses
to 2^p-1 and integers with Hamming weight 2) and hoping that the
intersection isn't empty.

There are no analytic tools available to approach the problem because
[AFAIK] there is almost nothing known about how false witnesses
are distributed mod P. It is easy to get a sharp counting function for
weight-2 integers up to B , but their distribution is clearly not uniform.

Heuristics based on probabilistic methods are likely to fail, because
the sets involved are not uniformly distributed.

Even if the result is true, it has almost no applicability anyway. LL will
be faster.
R.D. Silverman is offline   Reply With Quote