A051453

[Don Reble]

> %I A051453
> %S A051453 1,2,3,4,5,7,9,19,25,31,47,89,127,139
> %N A051453 Prime powers such that LCM[1,...,p^w] is prime.
> %e A051453 89 is the 34th prime power;
>     LCM[1,..,89]=718766754945489455304472257065075294401 is also prime.
> %Y A051453 A000961, A003418, A049536, A049537.
> %A A051453 Labos E. (labos at ana1.sote.hu)

As Wouter noted, that should be LCM[1,2,3,...,p^w]+1.
(And, without the "2,3,", it could be misinterpreted as
 LCM[1,p,p^2,...,p^w]+1. Even though that would be silly.)

Wouter says,
> the reason for the occurrence of 'runs' in A049537 is not fully clear to me.
It's because LCM[1,2,3,...n] changes only when N is a prime power.
So A051453 is a subset of A049537, showing the start of each run.
(But beware: such runs can run together.)

---

Testing further terms of A051453 is straightforward but slow, since the
numbers get big quickly.

Once one suspects that an LCM[]+1 is prime (say, by doing strong-
pseudoprime tests), one should then prove it's prime. It's tempting to
try the "N-1" method, of Lehmer and Selfridge.

    If, for each prime factor P_k of N-1, there is a number A_k such that
        (A_k)^[(N-1)/P_k] /= 1 mod N
    and
        (A_k)^[N-1] = 1 mod N
    then N is prime.

Essentially, one finds a (P_k)-power non-residue, for each P_k factor.
One must first factor N-1: but that's easy for those LCM[]+1 numbers.

Each small prime divides the LCM, so one needs to find a quadratic
non-residue, a cubic non-residue, a pentic non-residue, etc. One way is
just to check each small number (2,3,...) in turn to see whether it's a
non-residue; but the least non-residue must be a prime, so one checks
only those. The process is expected to be quick, since 1/2 of the
numbers are quadratic non-residues, 2/3rds are cubic non-residues,
4/5ths are pentic....

If one does it that way, one finds the least non-residue of each kind,
modulo LCM[1,2,3,...,p^w]+1. Here are the quadratic ones:

    A051453:          2 3 4 5 7  9 19 25 31 47  89 127 139 1369 2251
    least QuadNonRes: 2 3 2 2 2 11 37 29 37 59 103 131 149 1399 2267

    A051453:          3271 4253 4373 4549 5449 13331
    least QuadNonRes: 3301 4289 4409 4567 5471 13337

Except at the start, the least QNR is greater than p^w. It's a
consequence of quadratic reciprosity; the relevant theorem starts to
apply at multiples of 8. Unless one tells the prime-prover, it will take
a long time to find that first QNR!

(See also A000229, A025020-A025029; Guy's UPINT, F5 and F6).

--
Don Reble       djr at nk.ca