A000236

[David Wilson]

Let a(k) = A000236(k) as it now stands, and let b(k) be the true upper bound 
of the start of a run of either two consective kth-power residues or 
nonresidues modulo any prime.  You have found evidence that b(k) < 2^k, 
which would force us to conclude that our interpretation of A000236(k) = 
b(k) is in fact incorrect.  I too had realized the alternating nature of 
b(k) and concluded b(k) < 2^k independently, but you beat me to the punch in 
finding the disagreement with the published A000236.

I see the following possible explanations for the disagreement:

    (a) a(k) has the same definition as b(k), the paper gave correct values, 
and these were properly transcribed to A000236.  It is our argument that 
b(k) < 2^k that is incorrect.
    (b) a(k) has a different definition from b(k). That is, our assessment 
of the definition of a is incorrect.
    (c) a(k) has the same definition as b(k), the paper gave incorrect 
values for a which were properly transcribed to A000236.
    (d) a(k) has the same defintiion as b(k), the paper gave correct values 
for a which were improperly transcribed to A000236.

Since we both came up with the b(k) < 2^k independently, and the argument 
seems intuitively clear to me, I reject (a) as a possibility.  This means 
that (b), (c) or (d) are the case.

If (b) is the case, our proposed definition of A000236 is wrong.  If 
possible, we should find the correct definition and add it to A000236, at 
which point I can consider extending the sequence as I originally intended. 
Again if possible, we should compute sequence b and add it as a new OEIS 
sequence (since it is interesting and will differ from A000236).

If (c) or (d) are the case, the published values of A000236 are wrong. 
However, I highly recommend against correcting the values of A000236, given 
its age and its inclusion with existing values in the hardcopy versions of 
both the Handbook and Encyclopedia.  Instead A000236 should be declared 
dead.  If possible, we should compute sequence b and add it as a new OEIS 
sequence, and add a pointer from A000236 to the new sequence as the 
corrected version.


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


> [stuff elided]
> If prime p deliver the longest sequence of consecutive residues not 
> containing two adjacent n-powers or n-nonpowers (i.e., 1,2,...,A000236(n)) 
> then this sequence must alternate n-powers and n-nonpowers.
> Since 1 is a n-power modulo p (for any n,p), all odd numbers in the 
> sequence 1,2,...,A000236(n) must be n-powers and all even numbers must be 
> n-nonpowers modulo p.
> But the number 2^n  is obviously n-power implying that A000236(n) < 2^n 
> which is not the case.
>
> What's wrong?
>
> Max
>