Factorials
-
Hi Peter, IMO this will behave much better; it gives 4 for 10000000, does not overflow, has no loops but uses a recursion (scaling down by a factor of 5).
private int rightmostNonzeroInFactorial(int n) {
int result = 1;
// factor ending on 1
// no change
// factor ending on 2
int count2 = (n+8) / 10;
// factor ending on 3
int count3 = (n + 7) / 10;
// factor ending on 4
int count4 = (n + 6) / 10;
// factor ending on 5
int count5 = (n + 5) / 10;
// factor ending on 6
int count6 = (n + 4) / 10;
// factor ending on 7
int count7 = (n + 3) / 10;
// factor ending on 8
int count8 = (n + 2) / 10;
// factor ending on 9
int count9 = (n + 1) / 10;
// factor ending on 0
int count10 = (n + 0) / 10;
count5 += count10;
if (count5 != 0) {
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 -= count5;
}
count2 += 2 * count4; // 4 = 2*2
count2 += 3 * count8; // 8 = 2*2*2
count2 += 4 * count6; // 16 = 2*2*2*2count3 += 2 \* count9; // 9 = 3\*3; count3 += 3 \* count7; // 27 = 3\*3\*3 int\[\] fact3 = new int\[\] { 1, 3, 9, 7 }; // 3^5 ends on 3 result = (result \* fact3\[count3 % fact3.Length\]) % 10; int\[\] fact2 = new int\[\] { 1, 2, 4, 8 }; // 2^5 ends on 2 int factor2=fact2\[count2 % fact2.Length\]; if (factor2 == 1 && count2 != 0) factor2 = 6; // 2^4 = 16 result = (result \* factor2) % 10; return result;}
Main principle is factors that are not multiples of 5 don't care about their digits except the lowest one (and also: there will be more powers of 2 than powers of 5). :)
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
Hi Luc, I haven't worked through your code (are you sure the countN's do the right thing?). There is a little known fact (don't ask me how I know it!) that if n = 5q+r with 0 <= r < 5 then n! has the same rightmost non-zero digit as 2^n x q! x r! Using this the problems reduce easily.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
Hi Luc, I haven't worked through your code (are you sure the countN's do the right thing?). There is a little known fact (don't ask me how I know it!) that if n = 5q+r with 0 <= r < 5 then n! has the same rightmost non-zero digit as 2^n x q! x r! Using this the problems reduce easily.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
Hi Peter, 1. countN tells me how many factors of n! end on digit N 2. the recursion takes care of your q! 3. I ran a check for all [1,500] and for 10000000 regards,
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
-
Is it possible to get the rightmost NON-ZERO digit of a factorial without calculating for it? Say 1000! = 2 Regards, Ian *NO, this is not a homework.
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
I believe this to be an ACM question from either 96' or 97'
bool nonzerodigit(const unsigned int& n, unsigned int& result)
{
if (n > 100000) return false;
unsigned int result = 1;
for (unsigned int i = 1; i <= n; ++i)
{
unsigned int f = i;
while (0 == (f % 5))
{
f /= 5;
result /= 2;
}
result = (result % 100000) * f;
}
result %= 10;
return true;
}100000 is an upper sanity bound and also a quantizer for the minimum required 6 "least significant" digits.
-
Hi Peter, 1. countN tells me how many factors of n! end on digit N 2. the recursion takes care of your q! 3. I ran a check for all [1,500] and for 10000000 regards,
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
Luc Pattyn wrote:
countN tells me how many factors of n! end on digit N
OK now I see what you are doing. I'm sure you have some very clever reason for this, but it is not clear to me why you do
count5 += count10;
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 -= count5;
}and not what I would expect:
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 -= count5;
}
if (count10 != 0)
{
result = (result * rightmostNonzeroInFactorial(count10)) % 10;
}Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
Luc Pattyn wrote:
countN tells me how many factors of n! end on digit N
OK now I see what you are doing. I'm sure you have some very clever reason for this, but it is not clear to me why you do
count5 += count10;
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 -= count5;
}and not what I would expect:
if (count5 != 0)
{
result = (result * rightmostNonzeroInFactorial(count5)) % 10;
count2 -= count5;
}
if (count10 != 0)
{
result = (result * rightmostNonzeroInFactorial(count10)) % 10;
}Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
Hi Peter, the way you propose the factors that end on 5 don't get represented by count5 factorial (they only need odd multiples of 5), hence the recursion would not be correct. I expect the theory that explains my code would be the same as the one that led to the formula you've mentioned before. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
-
Hi Peter, the way you propose the factors that end on 5 don't get represented by count5 factorial (they only need odd multiples of 5), hence the recursion would not be correct. I expect the theory that explains my code would be the same as the one that led to the formula you've mentioned before. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
-
I believe this to be an ACM question from either 96' or 97'
bool nonzerodigit(const unsigned int& n, unsigned int& result)
{
if (n > 100000) return false;
unsigned int result = 1;
for (unsigned int i = 1; i <= n; ++i)
{
unsigned int f = i;
while (0 == (f % 5))
{
f /= 5;
result /= 2;
}
result = (result % 100000) * f;
}
result %= 10;
return true;
}100000 is an upper sanity bound and also a quantizer for the minimum required 6 "least significant" digits.
Thank you! I am training for the next ACM ICPC Regionals. :)
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
-
I assume you mean without calculating the factorial but some simpler, faster calculation? :) You can rewrite a factorial as a polynomial in n but I'm not sure if that gives you an easy pattern for the last digit. And by definition, all factorials except 1! and 0! are even. Does this have a practical application or are you just curious?
If you don't have the data, you're just another asshole with an opinion.
Nope. This is part of the question set my adviser gave me to prepare for a certain competition. :)
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
-
Nope. This is part of the question set my adviser gave me to prepare for a certain competition. :)
It is said that the most complex structures built by mankind are software systems. This is not generally appreciated because most people cannot see them. Maybe that's a good thing because if we saw them as buildings, we'd deem many of them unsafe.
Ian Uy wrote:
It is said that the most complex structures built by mankind are software systems.
I've heard that bandied about but I think I'll disagree. They usually quote Vista at 50 million lines of code yet the latest generation of processor chips boast over 2 billion transistors. And you could argue that much of what gets counted in an operating system are simply utilities that are applications running on the base system so the core is smaller still.
If you don't have the data, you're just another asshole with an opinion.
-
Ian Uy wrote:
It is said that the most complex structures built by mankind are software systems.
I've heard that bandied about but I think I'll disagree. They usually quote Vista at 50 million lines of code yet the latest generation of processor chips boast over 2 billion transistors. And you could argue that much of what gets counted in an operating system are simply utilities that are applications running on the base system so the core is smaller still.
If you don't have the data, you're just another asshole with an opinion.
Hi, I tend to disagree. Hardware, especially CPU design, mainly consists of very repetitive structures, whereas software, all kinds of it, is very inhomogeneous. And a new CPU gets designed in a matter of months, a new OS takes several years. That helps explaining why you would find less than 10 bugs in your CPU having 2 billion transistors, and several thousands of bugs in just 50 million lines of Windows code. So if you want to compare complexity, I suggest you look at design effort, and number of bugs. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
-
Hi, I tend to disagree. Hardware, especially CPU design, mainly consists of very repetitive structures, whereas software, all kinds of it, is very inhomogeneous. And a new CPU gets designed in a matter of months, a new OS takes several years. That helps explaining why you would find less than 10 bugs in your CPU having 2 billion transistors, and several thousands of bugs in just 50 million lines of Windows code. So if you want to compare complexity, I suggest you look at design effort, and number of bugs. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Voting for dummies? No thanks. X|
I still will disagree. In programming we keep using the same structures over and over again but insist on lovingly hand coding them each time. The chip makers have better tools and love to reuse their building blocks. A large part of their reuse is automated which explains the smaller number of bugs. They prove their components and then build up. Programmers make the same mistakes at ever increasing scales. On another note, humans make machines with millions of parts. I will contend that one line of code is not equivalent to designing one mechanical part in complexity.
If you don't have the data, you're just another asshole with an opinion.
-
Hi Luc, I haven't worked through your code (are you sure the countN's do the right thing?). There is a little known fact (don't ask me how I know it!) that if n = 5q+r with 0 <= r < 5 then n! has the same rightmost non-zero digit as 2^n x q! x r! Using this the problems reduce easily.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
cp9876 wrote:
...
There is a little known fact (don't ask me how I know it!) that if n = 5q+r with 0 <= r < 5 then n! has the same rightmost non-zero digit as 2^n x q! x r!
That should be 2^q rather than 2^n, and then it's valid for all n > 4. Removing recursion, here's one way to write it (in Python):
def f(n):
result = 1
while n > 1:
n, r = divmod(n, 5)
result = result * (6, 2, 4, 8)[n & 3] * (1, 1, 2, 6, 4)[r] % 10
return resultand that can be simplified a bit by using a larger table:
FACTAB = 6, 6, 2, 6, 4, 2, 2, 4, 2, 8, 4, 4, 8, 4, 6, 8, 8, 6, 8, 2
def f(n):
result = 1
while n > 1:
result = result * FACTAB[n % 20] % 10
n //= 5
return result