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

90 Solutions
35 Solvers

Last Solution submitted on Dec 30, 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 Solvers35

Problem Tags

factorial factorisation integer power of primes

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers35

Suggested Problems

More from this Author9

Problem Tags

Community Treasure Hunt

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers35

Suggested Problems

More from this Author9

Problem Tags

Community Treasure Hunt

Players