A000236

[David Wilson]

So, how does one effectively compute these values?

----- Original Message ----- 
From: "Max" <relf at unn.ac.ru>
To: <njas at research.att.com>
Cc: "Sequence Fans" <seqfan at ext.jussieu.fr>; "David Wilson" 
<davidwwilson at comcast.net>
Sent: Friday, August 05, 2005 5:31 PM
Subject: Re: A000236


> 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
>