[seqfan] Re: Range of the least witness function W(n)

Charles Greathouse charles.greathouse at case.edu
Fri Sep 24 08:13:15 CEST 2010

Let W(N) be the least witness function, which for odd composite N
gives the smallest b such that N is not a strong pseudoprime to base
b.  Following Crandall & Pomerance, if for some N, W(N) = k, let n_k =

I find that n_12 = 1502401849747176241, n_15 = 3034679039109989281,
n_22 = 16043083915816662841, and n_37 = 3825123056546413051.  This
suggests a revision to A089105: 15 and 22, at the least, should be
added.  As far as I know, it is still an open question if the sequence
is equal to A007916.

This, in turn, requires a modification to A089825 which is indexed by
A089105.  Perhaps the sequence should not be indexed, but values that
do not exist should be coded as 0 instead?

I do not know the values (or whether they exist) for of n_k for k in
{14, 18, 20, 21, 24, 26, 28, 29, 30, 31, 33, 34, 35}.  Is there any
way to show that n_k exists, save for finding n with W(n) = k?

Charles Greathouse
Case Western Reserve University

On Wed, Sep 22, 2010 at 3:40 PM, Charles Greathouse
<charles.greathouse at case.edu> wrote:
> How hard would it be to extend A089105?  If there is a good method,
> more terms plus an explanation would be much appreciated.  If not, a
> comment to that effect plus keyword:hard would be appropriate.
> I found that 37 is a member of the sequence, but I can't determine
> what other members may exist before that.  If A089105(n) = 37, then
> A089825(n) = 3825123056546413051.
> PN:ACP doesn't have much to say on the subject.
> Charles Greathouse
> Analyst/Programmer
> Case Western Reserve University

More information about the SeqFan mailing list