Problem 44071. Smallest n, for n! to have m trailing zero digits

Created by Jihye Sofia Seo

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For given positive integer n, its factorial often has many trailing zeros, in other words many factors of 10s. In order for n! to have at least \"m\" trailing zeros, what is the smallest \"n\" ?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Example: factorial(10) = 3628800 factorial(9) = 362880 In order to have 2 trailing zeros on factorial, the smallest n is 10.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/><w:jc w:val=\"left\"/></w:pPr><w:r><w:t>Optional: Can you make an efficient algorithm for a very large m?</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

69 Solutions
46 Solvers

Last Solution submitted on Sep 18, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 1135219

1 Comment

1 Comment

yurenchu on 7 Mar 2017

I think this is (so far) the most efficient solution for large m. It requires at most log(4*m)/log(5) iterations; while the smaller sized solutions that have been suggested require at least 0.8*m iterations (or a very large array). For example, for m = 10^5, this solution takes at most 8 iterations while the other solutions of smaller size require at least 80,000 iterations.

Problem Recent Solvers46

Problem Tags

factorial factorisation integer power of primes

Problem 44071. Smallest n, for n! to have m trailing zero digits

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers46

Suggested Problems

More from this Author9

Problem Tags

Problem 44071. Smallest n, for n! to have m trailing zero digits

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers46

Suggested Problems

More from this Author9

Problem Tags

Players