Prev: Tomorrow, the 30-th of March, despite to our protests, CERN plans to perform the first collisions of protons with the energy 3.5 TeV per proton (7 TeV per collision).
Next: SIMPLIFIED FOR SOME MATHEMATICS -- PROOF THAT PRIME NUMBERS ARE IN SETS OF 36
From: Tim Little on 30 Mar 2010 21:11
On 2010-03-30, mukesh tiwari <mukeshtiwari.iiitm(a)gmail.com> wrote:
> I was trying a problem form project euler (http://projecteuler.net/
> index.php?section=problems&id=282) in which we have to find out A[4]
> [4], A[5][5] and A[6][6] mod 14^8. Could some one please tell me how
> to solve this problem or kindly post the link which is useful for
> solving the problem.

I presume you found that A(3,n) = 2^(n+3) - 3. Then
A(4,n) + 3 = 2^(A(4,n-1) + 3), so you get a tower of exponents:
A(4,n) + 3 = 2^(2^(2^...^A(4,0) )))).

Note that the value of A(4,n) mod k depends only on A(4,n-1) mod phi(k)
by Euler's Theorem (and some use of Chinese Remainder Theorem to
account for any factors of 2 in k).

Repeating the reduction of k to phi(k) means that the sequence of
values A(4,n) mod k becomes constant after some number of terms less
than k.

Now A(5,5) = A(4,n) for some very large n, far beyond the point where
the sequence of mod 14^8 values becomes constant. Likewise A(6,6) can
also be expressed as A(4,n) for some ridiculously larger n. Find that
constant.


- Tim
From: Timothy Murphy on 31 Mar 2010 08:13
mukesh tiwari wrote:

> On Mar 30, 11:17 pm, Timothy Murphy <gayle...(a)eircom.net> wrote:
>> mukesh tiwari wrote:
>> > I am getting the output 253 253 253. About non recursive i have a
>> > small problem. Suppose we are calculating A(4,4)=2||(7)-3 which is
>> > equal to 2^2^2^65356-3. Now in order to calculate a^b^c%M first i have
>> > to find out value of d=b^c and then i can calculate a^d%M. Am i
>> > correct or wrong ? In this way A(5,5) and A(6,6) are almost impossible
>> > to find out. kindly tell me what i am missing.
>>
>> You probably only need to know d mod phi(M).

> Kindly tell me if i interpreted you right or not. In order to compute
> a^a^a^a^a%M. First calculate last d=a^a mod phi(M). Now we have a^a^a^d
> %M . Again calculate e=a^d mod phi(M). The expression is a^a^e%M and
> continue like that till we have result. Is this your mean or something
> else. Sorry for being dumb but math is not major. i just studied
> Computers and solve project euler problems for learning mathematics.

The other way round, assuming a^a^a^a^a means a^{a^{a^{a^a}}}.
Then a^a^a^a^a mod M depends on a^a^a^a mod phi(M),
which depends on a^a^a mod phi(phi(M)), etc.

Nb You were talking about a^{b^c} mod M
and to compute this you need b^c mod phi(M),

--
Timothy Murphy
e-mail: gayleard /at/ eircom.net
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
First  |  Prev  | 
Pages: 1 2
Prev: Tomorrow, the 30-th of March, despite to our protests, CERN plans to perform the first collisions of protons with the energy 3.5 TeV per proton (7 TeV per collision).
Next: SIMPLIFIED FOR SOME MATHEMATICS -- PROOF THAT PRIME NUMBERS ARE IN SETS OF 36