A000236

[Max]

N. J. A. Sloane wrote:
> here is the Math Rev of J.'s 1964 paper:"
> 
>  
> MR0161824 (28 #5028) 
> Jordan, J. H. 
> Pairs of consecutive power residues or non-residues. 
> Canad. J. Math. 16 1964 310--314.
> 10.06
> 

Hmmm. This review is quite hard to understand.

> 
> 
> Let $k$ be a positive integer, $p=k+1$ a prime and $g$ a primitive root of $p$. Let $g^{\text{Ind}\,u}\equiv u (\text{mod}\,p)$. 
> 
> Recently various authors [the reviewer and E. Lehmer, Proc. Amer. Math. Soc. 13 (1962), 102--106; MR0138582 (25 \#2025); the reviewer, E. Lehmer and W. Mills, Canad. J. Math. 15
> (1963), 172--177; MR0146134 (26 \#3660)] have been concerned with the function $\Lambda(k,m)=\max\{r(k,m,p)\}$, 

First of all, k and p does not anymore related as p=k+1 as specified above. Otherwise it would be not possible to take maximum over p keeping k constant.

> where $r(k,m,p)$ denotes the least $r$ for which $$ \multline
> \text{Ind}\,(r)\equiv\text{Ind}\,(r+1)\equiv\cdots\equiv\\ \text{Ind}\,(r+m-1)\equiv 0\quad(\text{mod}\,p-1) \endmultline\tag1 $$ 

In the current form r(k,m,p) does not depend on k at all.
In congruence above it should be "... \equiv 0 (mod k)" instead of "... \equiv 0 (mod p-1)" but anyway that makes sense only for k dividing p-1.
It better to say that r=r(k,m,p) is the smallest positive integer such that r,r+1,...,r+m-1 are k-powers modulo p. Note that if k and p-1 are coprime then r(k,m,p)=1.

> and the maximum is taken over all primes $p$ for which $r$ exists.

In other words, L(k,m) is the smallest number t such that for every prime p admitting a run of consecutive k-powers modulo p of length m there exists such a run starting with some r<=t.

>  $\Lambda(k,2)$ increases rapidly with $k\colon\Lambda(2,2)=9$, $\Lambda(3,2)=77$, $\Lambda(4,2)=1224$, $\Lambda(5,2)=7888$, $\Lambda(6,2)=202124$,
> $\Lambda(7,2)=1649375$. 

This sequence is A000445 defined as "First occurrences of 2 consecutive n-th power residues".
The current definition is very misleading.
Please replace it with something like "A000445(n)=minimum t such that for every prime p admitting pairs of consecutive n-powers modulo p there exists such a pair (r,r+1) with r<=t".

btw, there exists a satellite sequence a(n)=minimum prime p for which the smallest pair of consecutive n-powers modulo p starts with A000445(n).
Could anybody please compute this sequence? It starts with 43.

> The author defines another function $\Lambda^*(k,m)$ obtained by deleting the condition of divisibility in (1)
> so that one asks only for the first appearance of $m$ consecutive integers whose
> $k$th power characters are identical.

As I understood, these m consecutive integers are all either k-powers or k-nonpowers modulo p.

> $\Lambda^*(k,2)$ turns out to be very much smaller. The author has established that $\Lambda^*(2,2)=3$, $\Lambda^*(3,2)=8$, $\Lambda^*(4,2)=20$,
> $\Lambda^*(5,2)=44$, $\Lambda^*(6,2)=80$, $\Lambda^*(7,2)=343$. The proofs are short enough to be done "by hand", although the last two proofs are omitted to save space. 

This is A000236 and its definition again is very cryptic.
I suggest to replace it with something like ``A000236(n)=minimum t such that for every prime p there exists a pair (r,r+1) of consecutive n-powers or n-nonpowers modulo p with r<=t''.

And again there exists a satellite sequence a(n)=minimum prime p for which the smallest pair of consecutive n-powers or n-nonpowers modulo p starts with A000236(n).
Could anybody please compute this sequence as well? It starts with 11.

Trivially, we observe that A000236(n) <= A000445(n).
Since the number of n-powers is much smaller (roughly 1/(n-1) times) than the number of n-nonpowers, it seems plausible that A000236 always deals with n-nonpowers meaning that A000236(n) < A000445(n) (i.e., *strictly* less) but that requires a proof.

> The further
> results $\Lambda^*(2k,3)=\Lambda^*(k,4)=\infty$ are also obtained in the same manner as for $\Lambda$.

Max