Is this test efficient to calculate a particular class of primes?

[Davide Rotondo]

Hi to all, of the 498 numbers n ranging from 1 to 1,000,000 such that (2^((n-1)/2)+5^((n-1)/2)-n) is divisible by (n*(n+2)), none are composite numbers. Furthermore, of these 498 primes, a very high percentage are isolated primes—494 in total.

What do you think?

See you soon

Davide

[Gareth McCaughan]

On 21/11/2025 10:07, Davide Rotondo wrote:
> Hi to all, of the 498 numbers n ranging from 1 to 1,000,000 such that
> (2^((n-1)/2)+5^((n-1)/2)-n) is divisible by (n*(n+2)), none are
> composite numbers. Furthermore, of these 498 primes, a very high
> percentage are isolated primes—494 in total.

For any such n, clearly n is odd and therefore n,n+2 are coprime, so
your condition is equivalent to the conjunction of two others: 2^m+5^m =
0 mod n and 2^m+5^m = n mod n+2, where m=(n-1)/2.

The first condition is the same as (5/2)^m = -1 mod n, where by "5/2" I
mean "the unique x such that 2x=5 mod n", which exists because n is odd.

This condition is one of the two ways for the Miller-Rabin primality
test to succeed for the base 5/2; in other words, if it holds then n is
a strong pseudoprime to base 5/2.

The Miller-Rabin test, even with just a single round, doesn't make a lot
of mistakes, and in fact of the 39304 numbers up to 1000000 for which
your first condition holds only 31 are composite.

Maybe the second condition is doing something clever; if so, I don't
know what. But I think more likely it's just _usually false_ and so it's
selecting a kinda-random subset of those 39304 numbers. About 1/80 of
them, as it happens. And since only 31 of those numbers are composite,
it's not surprising that choosing 1/80 of them happens not to pick any
of the composite ones.

If you go up to 2000000 instead of 1000000 you'll find the number
1419607, for which your condition holds. But, alas, 1419607 - 7 x 139 x
1459.

--
g

[Davide Rotondo]

Thanks a lot Gareth!

Davide

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/63cab960-1f81-49ba-a3b6-e135c2aa8e56%40pobox.com.