[seqfan] Re: A092188
Max Alekseyev
maxale at gmail.com
Sat Jun 2 12:52:12 CEST 2012
I've just added a new sequence A213013 (which a variant of A092188)
with a sample PARI/GP code.
Regards,
Max
On Fri, Jun 1, 2012 at 1:59 PM, Max Alekseyev <maxale at gmail.com> wrote:
> I suggest the following approach:
> Split m into powers of primes, compute a^b modulo each such power of
> prime, and combine the results using CRT.
>
> If prime p does not divide a, then mod(a^b,p^k) is computed by the formula.
> To compute mod(a^b,p^k) when prime p divides a, represent a as p^m*c
> where p does not divide c, and
> if m*b >= k, then mod(a^b,p^k) = 0;
> if m*b < k, then mod(a^b,p^k) = p^(m*b) * mod(c^b,p^(k-mb)).
>
> Regards,
> Max
>
> On Fri, Jun 1, 2012 at 1:28 PM, Jean-François Alcover
> <jf.alcover at gmail.com> wrote:
>> 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/
>>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list