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: mukesh tiwari on 30 Mar 2010 10:44
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.

Thank you
From: Chip Eastham on 30 Mar 2010 11:18
On Mar 30, 10:44 am, mukesh tiwari <mukeshtiwari.ii...(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.
>
> Thank you

Thanks for posting a link to this interesting
site. I was not aware of it.

Take a look at this Wikipedia article:

[Ackermann function -- Wikipedia]
http://en.wikipedia.org/wiki/Ackermann_function

and specifically at the section on representing
it non-recursively, e.g. using Knuth's up-arrow
notation.

I suspect the key is going to be computing mod
14^8, or perhaps both mod 2^8 and 7^8 and then
combining the results via Chinese Remainder Thm.

regards, chip
From: mukesh tiwari on 30 Mar 2010 13:56
On Mar 30, 8:18 pm, Chip Eastham <hardm...(a)gmail.com> wrote:
> On Mar 30, 10:44 am, mukesh tiwari <mukeshtiwari.ii...(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.
>
> > Thank you
>
> Thanks for posting a link to this interesting
> site.  I was not aware of it.
>
> Take a look at this Wikipedia article:
>
> [Ackermann function -- Wikipedia]http://en.wikipedia.org/wiki/Ackermann_function
>
> and specifically at the section on representing
> it non-recursively, e.g. using Knuth's up-arrow
> notation.
>
> I suspect the key is going to be computing mod
> 14^8, or perhaps both mod 2^8 and 7^8 and then
> combining the results via Chinese Remainder Thm.
>
> regards, chip
I found a paper https://files.oakland.edu/users/grossman/web/ackermod.pdf
which seems useful and i implement it but i am getting segmentation
fault when i am calculating about 7^8. Here is the source code
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MOD 256
using namespace std;
typedef long long ll;

int A[10][10000000];

int recur(int x,int y)
{
if(A[x][y]!=-1) return A[x][y];
if(x==0) return A[x][y]=(y+1)%MOD;
if(x>0 && y==0) return A[x][y]=recur(x-1,1)%MOD;
if(x>0 && y>0)
return A[x][y]=recur(x-1,recur(x,y-1)%MOD)%MOD;
}


int main()
{
memset(A,-1, sizeof A);

cout<<recur(4,4)<<" "<<recur(5,5)<<" "<<recur(6,6)<<endl;
}
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.
Thank you.
From: Timothy Murphy on 30 Mar 2010 14:17
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).


--
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
From: mukesh tiwari on 30 Mar 2010 15:07
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).
>
> --
> 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

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.
 |  Next  |  Last
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