Were these the droids you were looking for?
[SPOILER]216^16384+109^16384[/SPOILER]

[QUOTE=Batalov;482504]Were these the droids you were looking for?
[SPOILER]216^16384+109^16384[/SPOILER][/QUOTE]

Yes! And is it certain that 216^16384+109^16384 is minimal?

Did you search and find this now, or was it something that was known (to you) in advance?

Of course, now I want then minimal odd prime a^(2^m)+b^(2^m) for all the next m values :smile:

/JeppeSN

[QUOTE=Batalov;482504]Were these the droids you were looking for?
[SPOILER]216^16384+109^16384[/SPOILER][/QUOTE]

For added confidence in Serge's result:

[CODE]time ./pfgw64 -k -f0 -od -q"[SPOILER]216^16384+109^16384[/SPOILER]" | ../../coding/gwnum/hybrid -

Testing (x + 1)^(n + 1) == 2 + 3 (mod n, x^2 - 3*x + 1)...
Likely prime!

real 1m45.793s
user 2m36.120s
sys 0m55.244s
[/CODE]

If one wanted to check exponents 2^m for several values of m, one might want to compile a table of pairs (a,b) with a < b, b <= N (given upper bound), gcd(a, b) = 1, [i]and[/i] a + b odd. This isn't entirely trivial. And I'm quite poor at this sort of thing.

Without the condition that a + b be odd, it would be equivalent to calculating the Farey sequence of order N. Perhaps the way to go is to calculate the Farey sequence, and then skip pairs where a and b are both odd.

One idea I considered by rejected was, for [i]even[/i] b, find the positive integers r < b with gcd(r, b) = 1, then fill in the entries (b, r + k*b) with r + k*b not exceeding N. Alas, you would have to make sure, for each r, that the multiplier k was relatively prime to r...

Of course, viewing table computation as a preliminary calculation, it probably makes little difference [i]how[/i] clumsily it is compiled, if N isn't very big. For large exponents, the value of b will be a good indicator of the size of a^(2^m) + b^(2^m)

The idea of sieving out multiples of "small" primes p congruent to 1 (mod 2^(m+1)) makes sense. Each pair (a, b) sieved out as giving a multiple of p means you can skip a PRP test. I looked at the primes p congruent to 1 (mod 2^15) up to the limit 50 million. There are 174 such primes. Grasping at straws(*), I computed the product (1 - 2^14/p) over these primes, and got .507+ which would be great if it meant eliminating almost half the pairs (a, b) actually under consideration.

(*) I reckoned that the relevant thing here was the 2^14 solutions to Mod(r,p)^(2^14) + 1 = Mod(0,p). Each pair (Mod(a,p), Mod(r, p)*Mod(a,p)) gives a multiple of p. This ignores the question of which such pairs might reduce to pairs of small coprime integers (a, b) of different parity. But hey -- any PRP test you can skip cheaply is to the good, right?

I did a quick check of the idea with the exponent 16. I looked at the smallest prime (p = 97) congruent to 1 (mod 32), and easily found from the root Mod(19,97) to

x^16 + 1 = Mod(0,97)

that 5^16 + 2^16 is a multiple of 97.

[QUOTE=JeppeSN;482508]Yes! And is it certain that 216^16384+109^16384 is minimal?

Did you search and find this now, or was it something that was known (to you) in advance?

Of course, now I want then minimal odd prime a^(2^m)+b^(2^m) for all the next m values :smile:

/JeppeSN[/QUOTE]
It is minimal.
What puzzles me is why is this taking others so long to find the same? It only took overnight on 8 cores. The workflow is very simple: generate (a,b)s in 1 second with a trivial Pari script (opposite parity, gcd > 1, say, up to a<=400), then split into a few workfiles (hawever many cores you have) and run [c]pfgw -f"{65536}" -N -k -l input[/c] on each chunk, periodically check, ..., done!

For m=15, it is perhaps best to sieve, but for m=14, this -f parameter takes care of the small factors just well enough.

It is just a question of resources. For this random question I only used 1 core for sieving and 1 core for pfgw, I had no need to use more, rest is running Prime95 on this machine, it is not like we had to find the answer within a certain time limit.

I only tried briefly using pfgw for trial factoring long ago, and my impression was it was horribly slow at it, so I have not tried again, I might try next time I need it.


Edit: and yes I should have sorted the list so it ran pfgw on candidates by size, but I made this quick program last night before I went to bed, and I only got 4-5 hours of sleep before work.

[QUOTE=Batalov;482516]run [c]pfgw -f"{65536}" -N -k -l input[/c] on each chunk, periodically check, ..., done![/QUOTE]
The should be f{32768}. You will miss a prolific factor 10*16384+1

A typo, this command-line is already prepared for m=15. :-)

Technically if a and b are squares you find one for the next level up as well.

[QUOTE=science_man_88;482533]Technically if a and b are squares you find one for the next level up as well.[/QUOTE]

Yes, but 216 and 109 aren't (though the former is a cube).

Another droid crossed my path. [SPOILER]260^32768+179^32768[/SPOILER]
Not proven minimal yet, though.