just digged up some of my thoughts on the subject:

http://tech.groups.yahoo.com/group/primenumbers/message/15715

http://tech.groups.yahoo.com/group/primenumbers/message/15721

They are somehow summarized in this bugfixed copy of my old message to Decio Luiz Gazzoni Filho:

* * * * * * *

Define w(p, y) for integer y > 0 and prime p this way (there d = gcd(y, p-1), f = (p-1)/d):

if p|y then w(p, y) = 1 else

if (-y)^f = 1 (mod p) then w(p, y) = d else w(p, y) = 0

Note that w(p, y) is periodic with period p*(p-1):

w(p, y) = w(p, y mod (p^2-p))

It's also clear from the definition (and from the sum over orders modulo p) that

sum[w(p, y), {y from 1 to p^2-p}] = p^2-p [*]

There are values of w(p,y) for p = 2, 3, 5, 7, where y runs from 0 to p^2-p-1:

(1 1)

(1 1 2 1 0 1)

(1 1 0 1 4 1 2 1 0 1 1 1 0 1 2 1 0 1 0 1)

(1 1 0 0 0 1 6 1 0 0 2 1 0 1 1 3 0 1 0 1 2 1 0 1 0 1 2 3 1 1 0 1 0 0 2 1 0 1 2 0 2 1)

Let's also define w'(p, y) in the same way as w(p, y), but use y^f instead of (-y)^f, so we'll obtain

w'(p, y mod (p^2-p)) = w(p, (-y) mod (p^2-p))

Conjecture A:

If, for a given y, we sieve out all x^y+y^x divisible by q|(p-1) for all such q's, then exactly w(p, y)/p of remaining numbers will be divisible by p.

Conjecture A':

If, for a given y, we sieve out all x^y-y^x divisible by q|(p-1) for all such q's , then exactly w'(p, y)/p of remaining numbers will be divisible by p.

Conjectures are equal each to other, so let's prove the latter.

1� It's clear that w'(p, y) = 1 when p | y.

2� It's also easy to show that w'(p, y) = 1 when p does not divide y and gcd(y, p-1) = 1. Indeed, there's only one solution of x^y = y^n (mod p) for every integer n from 1 to p-1, so we'll sieve out exactly 1/p of candidates with (x mod (p-1)) = n for every n where such candidates exist, yielding in 1/p of total.

3� Now let p does not divide y, and gcd(y, p-1) = d > 1. Let g is the order of y (mod p). We need to prove that

if g divides (p-1)/d, then w'(p, y) = d.

Once it's proven, we don't need to prove that in other cases w'(p, y) = 0, because of [*] and the fact that exactly 1/p of the numbers x^y-y^x, which are co-prime to p-1, are divisible by p. Indeed, if there were more than 1/p, the same situation would appear for x^y+y^x, giving too many y^x divisible by p.

Now let's show that (under conditions 3�) if w'(p, y) > 0, then w'(p, y) = d. The way is similar to 2�: if there are solutions of x^y = a (mod p) for some a <> 0 (mod p), then there are exactly d such solutions.

So, after all, the only thing to prove is Lemma 1:

if p does not divide y, gcd(y, p-1) = d > 1, g is the order of y (mod p) and g divides (p-1)/d, then w'(p, y) > 0.

It looked for me somewhat obvious in 2003, but now I come closer and feel myself having no idea how to prove it. :(

Maybe you have some?

* * * * * * *

The products

Weight(y) = Product[(p-w(p, y))/(p-1), {p is prime}],

Weight'(y) = Product[(p-w'(p, y))/(p-1), {p is prime}]

give us estimates of the "density" of primes of the form x^y+y^x or x^y-y^x respectively, where y is frozen, as well as Yves Gallot's estimators for Generalized Fermats: http://perso.wanadoo.fr/yves.gallot/papers/ccdgfpn.html

Note that, in practice, we need quite large ranges of x's to make these estimators working.

With best regards,

Andrey Kulsha

[Non-text portions of this message have been removed]