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

59 Solutions
40 Solvers

Last Solution submitted on Jul 26, 2020

Last 200 Solutions

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 Solvers40

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

Solution Comments

Problem Recent Solvers40

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

Solution Comments

Problem Recent Solvers40

Suggested Problems

More from this Author9

Problem Tags

Players