[seqfan] Re: A092188
Jean-François Alcover
jf.alcover at gmail.com
Fri Jun 1 11:28:23 CEST 2012
Thanks Max, for a quick and luminiferous response.
[ I have to say I'm almost an ignoramus in higher arithmetic ]
Is there a way (other than the given algorithm) you could suggest
for me to fix the program in case gcd(a,m) > 1 ?
2012/6/1 Max Alekseyev <maxale at gmail.com>
> The equality mod(a^b,m) = mod(a^(mod(b,phi(m)), m) works only when a
> is coprime to m.
> E.g., take a=2, b=2, m=4:
> mod(a^b,m) = mod(2^2,4) = 0
> mod(a^(mod(b,phi(m)), m) = mod(2^(mod(2,2), 4) = mod(2^0, 4) = 1
>
> Regards,
> Max
>
> On Fri, Jun 1, 2012 at 11:28 AM, Jean-François Alcover
> <jf.alcover at gmail.com> wrote:
> > Hello Seqfans,
> >
> > My trouble is about sequence A092188.
> > a(n) = smallest positive integer m such that 2^3^4^5^...^n == m mod n.
> >
> > I wanted to generate it sans using the algorithm given by Robert Munafo,
> > and using the equality mod(a^b,m) = mod(a^(mod(b,phi(m)), m)
> > This way with this Mathematica one-liner:
> >
> > a[n_] := Fold[ PowerMod[#2, #1, Nest[EulerPhi, n, #2-2]] &, n, Range[n-1,
> > 2, -1]];
> >
> > Unfortunately it goes wrong for about 10% of the cases
> > such as a(10)=8 instead of 2
> > Any help or hint is welcome.
> >
> > jfa
> >
> > _______________________________________________
> >
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list