[algogeeks] Re: program for evaluation of remainders
Are all of you talking about getting the result in closed form, so that no loop is involved? Other than mine, I haven't seen an implementation of a working algorithm. Let's see your code! My algorithm avoids calculating the factorials, which overflow 32-bit integers for N > 12, and is O(min(N,n)). When you beat that, let me know. Dave On Dec 11, 10:15 am, "Shiv Shankar" wrote: > Hi, > I agree with ankit sablok. And if we get the factorial of n in 1!, 2!, 3! > Etc. Then we can find the number easily. In its complexity will be O(N) > > > > -Original Message- > From: algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] On > > Behalf Of Dave > Sent: Friday, December 10, 2010 8:10 PM > To: Algorithm Geeks > Subject: [algogeeks] Re: program for evaluation of remainders > > @Ankit: Why not just use the algorithm I proposed > inhttp://groups.google.com/group/algogeeks/msg/2941ab071a39517c: > > x = 0; > for( i = (n < N ? n : N) ; i > 0 ; --i ) > x = (i * x + i) % n; > > Dave > > On Dec 10, 4:23 am, ankit sablok wrote: > > @Dave > > we will use residues then i think the property of modulus > > > 1!mod997 + 2!mod997 + 3!mod997 .. + 997!mod997 > > > i just proposed the solution using congruences for the case > > n > > can u generalize the problem using congruences if so then please post > > it > > thnanx in advance > > > On Dec 9, 2:13 am, Dave wrote: > > > > @Ankit: So how does that work with, e.g., N = n = 997? I.e., what is > > > the calculation? > > > > Dave > > > > On Dec 8, 11:33 am, ankit sablok wrote: > > > > > @ all the authors thanx for the suggestions actually wt i know about > > > > the problem is i think we can solve the problem mathematically if we > > > > know about congruences > > > > > for instance > > > > if N=100 > > > > 1! + 2! + . + 100! > > > > and n=12 > > > > > we find that > > > > 4!mod24=0 > > > > > hence the above equation reduces to the > > > > (1!+2!+3!)mod 12 =9 > > > > hence the answer is 9 > > > > > so can anyone write a program for this logic > > > > > On Dec 8, 6:19 pm, ankit sablok wrote: > > > > > > Q) can anyboy find me the solution to this problem > > > > > > Given an integer N and an another integer n we have to write a > program > > > > > to find the remainder of the following problems > > > > > (1! + 2! + 3! + 4! + . + N!)mod(n) > > > > > > N<=100 > > > > > n<=1000; > > > > > > please help me write a program for this problem > > > > > thanx in advance- Hide quoted text - > > > > > - Show quoted text -- Hide quoted text - > > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group > athttp://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
RE: [algogeeks] Re: program for evaluation of remainders
Hi, I agree with ankit sablok. And if we get the factorial of n in 1!, 2!, 3! Etc. Then we can find the number easily. In its complexity will be O(N) -Original Message- From: algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] On Behalf Of Dave Sent: Friday, December 10, 2010 8:10 PM To: Algorithm Geeks Subject: [algogeeks] Re: program for evaluation of remainders @Ankit: Why not just use the algorithm I proposed in http://groups.google.com/group/algogeeks/msg/2941ab071a39517c: x = 0; for( i = (n < N ? n : N) ; i > 0 ; --i ) x = (i * x + i) % n; Dave On Dec 10, 4:23 am, ankit sablok wrote: > @Dave > we will use residues then i think the property of modulus > > 1!mod997 + 2!mod997 + 3!mod997 .. + 997!mod997 > > i just proposed the solution using congruences for the case > n > can u generalize the problem using congruences if so then please post > it > thnanx in advance > > On Dec 9, 2:13 am, Dave wrote: > > > > > @Ankit: So how does that work with, e.g., N = n = 997? I.e., what is > > the calculation? > > > Dave > > > On Dec 8, 11:33 am, ankit sablok wrote: > > > > @ all the authors thanx for the suggestions actually wt i know about > > > the problem is i think we can solve the problem mathematically if we > > > know about congruences > > > > for instance > > > if N=100 > > > 1! + 2! + . + 100! > > > and n=12 > > > > we find that > > > 4!mod24=0 > > > > hence the above equation reduces to the > > > (1!+2!+3!)mod 12 =9 > > > hence the answer is 9 > > > > so can anyone write a program for this logic > > > > On Dec 8, 6:19 pm, ankit sablok wrote: > > > > > Q) can anyboy find me the solution to this problem > > > > > Given an integer N and an another integer n we have to write a program > > > > to find the remainder of the following problems > > > > (1! + 2! + 3! + 4! + . + N!)mod(n) > > > > > N<=100 > > > > n<=1000; > > > > > please help me write a program for this problem > > > > thanx in advance- Hide quoted text - > > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Dave Because he wants to optimize it if we can get the boundary of running time, we'll get the faster algorithm haxxpop -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Ankit: Why not just use the algorithm I proposed in http://groups.google.com/group/algogeeks/msg/2941ab071a39517c: x = 0; for( i = (n < N ? n : N) ; i > 0 ; --i ) x = (i * x + i) % n; Dave On Dec 10, 4:23 am, ankit sablok wrote: > @Dave > we will use residues then i think the property of modulus > > 1!mod997 + 2!mod997 + 3!mod997 .. + 997!mod997 > > i just proposed the solution using congruences for the case > n > can u generalize the problem using congruences if so then please post > it > thnanx in advance > > On Dec 9, 2:13 am, Dave wrote: > > > > > @Ankit: So how does that work with, e.g., N = n = 997? I.e., what is > > the calculation? > > > Dave > > > On Dec 8, 11:33 am, ankit sablok wrote: > > > > @ all the authors thanx for the suggestions actually wt i know about > > > the problem is i think we can solve the problem mathematically if we > > > know about congruences > > > > for instance > > > if N=100 > > > 1! + 2! + . + 100! > > > and n=12 > > > > we find that > > > 4!mod24=0 > > > > hence the above equation reduces to the > > > (1!+2!+3!)mod 12 =9 > > > hence the answer is 9 > > > > so can anyone write a program for this logic > > > > On Dec 8, 6:19 pm, ankit sablok wrote: > > > > > Q) can anyboy find me the solution to this problem > > > > > Given an integer N and an another integer n we have to write a program > > > > to find the remainder of the following problems > > > > (1! + 2! + 3! + 4! + . + N!)mod(n) > > > > > N<=100 > > > > n<=1000; > > > > > please help me write a program for this problem > > > > thanx in advance- Hide quoted text - > > > > - Show quoted text -- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Dave we will use residues then i think the property of modulus 1!mod997 + 2!mod997 + 3!mod997 .. + 997!mod997 i just proposed the solution using congruences for the case n wrote: > @Ankit: So how does that work with, e.g., N = n = 997? I.e., what is > the calculation? > > Dave > > On Dec 8, 11:33 am, ankit sablok wrote: > > > > > @ all the authors thanx for the suggestions actually wt i know about > > the problem is i think we can solve the problem mathematically if we > > know about congruences > > > for instance > > if N=100 > > 1! + 2! + . + 100! > > and n=12 > > > we find that > > 4!mod24=0 > > > hence the above equation reduces to the > > (1!+2!+3!)mod 12 =9 > > hence the answer is 9 > > > so can anyone write a program for this logic > > > On Dec 8, 6:19 pm, ankit sablok wrote: > > > > Q) can anyboy find me the solution to this problem > > > > Given an integer N and an another integer n we have to write a program > > > to find the remainder of the following problems > > > (1! + 2! + 3! + 4! + . + N!)mod(n) > > > > N<=100 > > > n<=1000; > > > > please help me write a program for this problem > > > thanx in advance- Hide quoted text - > > > - Show quoted text -- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: program for evaluation of remainders
@jai gupta why is this work?? I think it just calculates (N+1)! %n haxxpop -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Dave I like this. use mem just O(1) , my algo use O(N). Thxx haxxpop -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
997 is a prime number, so the calculation must be (1!+2!+...+996!) mod 997 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Ankit: So how does that work with, e.g., N = n = 997? I.e., what is the calculation? Dave On Dec 8, 11:33 am, ankit sablok wrote: > @ all the authors thanx for the suggestions actually wt i know about > the problem is i think we can solve the problem mathematically if we > know about congruences > > for instance > if N=100 > 1! + 2! + . + 100! > and n=12 > > we find that > 4!mod24=0 > > hence the above equation reduces to the > (1!+2!+3!)mod 12 =9 > hence the answer is 9 > > so can anyone write a program for this logic > > On Dec 8, 6:19 pm, ankit sablok wrote: > > > > > Q) can anyboy find me the solution to this problem > > > Given an integer N and an another integer n we have to write a program > > to find the remainder of the following problems > > (1! + 2! + 3! + 4! + . + N!)mod(n) > > > N<=100 > > n<=1000; > > > please help me write a program for this problem > > thanx in advance- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@ all the authors thanx for the suggestions actually wt i know about the problem is i think we can solve the problem mathematically if we know about congruences for instance if N=100 1! + 2! + . + 100! and n=12 we find that 4!mod24=0 hence the above equation reduces to the (1!+2!+3!)mod 12 =9 hence the answer is 9 so can anyone write a program for this logic On Dec 8, 6:19 pm, ankit sablok wrote: > Q) can anyboy find me the solution to this problem > > Given an integer N and an another integer n we have to write a program > to find the remainder of the following problems > (1! + 2! + 3! + 4! + . + N!)mod(n) > > N<=100 > n<=1000; > > please help me write a program for this problem > thanx in advance -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
Using this idea makes my solution into x = 0; for( i = (n < N ? n : N) ; i > 0 ; --i ) x = (i * x + i) % n; Dave On Dec 8, 7:27 am, Ashim Kapoor wrote: > Let me try. Any thing involving n would leave no remainder. > > so (1 + 2 ! + ... + n ! + + N !) mod n = (1 + 2 ! + ... + (n-1)! ) mod > n > > This should be computed from a loop. I don't know how to reduce it further. > > Ashim. > > > > On Wed, Dec 8, 2010 at 6:49 PM, ankit sablok wrote: > > Q) can anyboy find me the solution to this problem > > > Given an integer N and an another integer n we have to write a program > > to find the remainder of the following problems > > (1! + 2! + 3! + 4! + . + N!)mod(n) > > > N<=100 > > n<=1000; > > > please help me write a program for this problem > > thanx in advance > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: program for evaluation of remainders
rem=1; for(j=3;j<=N+1;j++) rem=(rem*j)%n; return rem; -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: program for evaluation of remainders
@Ankit: Try this: x = 0; for( i = N ; i > 0 ; --i ) x = (i * x + i) % n; Dave On Dec 8, 7:19 am, ankit sablok wrote: > Q) can anyboy find me the solution to this problem > > Given an integer N and an another integer n we have to write a program > to find the remainder of the following problems > (1! + 2! + 3! + 4! + . + N!)mod(n) > > N<=100 > n<=1000; > > please help me write a program for this problem > thanx in advance -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
