WIL's blog

Number of digits?
By WIL, 9 years ago, In English

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!!!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Maybe if you rewrite it, this will help you.
1*1! + 2*2! + ... + N*N! = 1*(1 + 2*(2 + 3*(3 + ... + N*(N)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

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 ⌈ lg(N + 1)!⌉ 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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice problem, i understand now. Thank everybody.

→ Reply