For quite some time, I had the doubt about how many digits had an mathematical operation like this: A*B
or A!
, and searching in internet, i found how to do this using log, but i found the problem Python Brute Force, that ask for the number of digit to the following operation: 1*1!+2*2!+....+N*N!
. I don't know how to count the number of digit to the sum of terms, like A+B
. Maybe this problem is just transform the operations, but i don't see how to do that. thank for the help!!!
You can show that 1 * 1! + 2 * 2! + ... + N * N! = (N + 1)! — 1. Now, the number of digits of (N + 1)! — 1 is the same that (N+1)!, because (N + 1)! is never a power of ten.
Maybe if you rewrite it, this will help you.
1*1! + 2*2! + ... + N*N!
=1*(1 + 2*(2 + 3*(3 + ... + N*(N)
Because k * k! can be rewritten as (k + 1 - 1) * k! = (k + 1)! - k! your sum telescopes to (N + 1)! - 1. Now the number of digits in (N + 1)! - 1 is equal to the number of digits of (N + 1)! because N! is not a power of ten for any N > 1. Now you need to find the smallest k such that (N + 1)! < 10k then the number of digits will be k. The inequality can be rewritten as lg(N + 1)! < k, so the smallest solution is
Unable to parse markup [type=CF_TEX]
but lg(N + 1)! = lg(1 * 2 * 3 * ... * (N + 1)) = lg1 + lg2 + lg3 + lg4 + ... + lg(N + 1). Floating point numbers can be a bit imprecise(maybe there is another method for solving that inequality), but if you precompute the values sequentialy for all N, you'll be able to answer in O(1) for a query. Also if you work in other base than base 10, then instead you should solve the inequality (N + 1)! < basek.Very nice problem, i understand now. Thank everybody.