Блог пользователя WIL

Number of digits?
Автор WIL, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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.
→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very nice problem, i understand now. Thank everybody.

→ Ответить