Problem 51950. Find the smallest integer m such that n divides m!

Created by ChrisR

Solve Later

{"parts":[{"partUri":"/matlab/document.xml","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:jc w:val=\"left\"/></w:pPr><w:r><w:t>Write a function that takes an integer </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t> and finds the smallest integer </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"m\"/></w:customXmlPr><w:r><w:t>m</w:t></w:r></w:customXml><w:r><w:t> whose factorial is divisible by </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t>. For example, if </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n = 10\"/></w:customXmlPr><w:r><w:t>n = 10</w:t></w:r></w:customXml><w:r><w:t>, then the smallest factorial that is a multiple of </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"n\"/></w:customXmlPr><w:r><w:t>n</w:t></w:r></w:customXml><w:r><w:t> is 5! = 120; therefore, </w:t></w:r><w:customXml w:element=\"equation\"><w:customXmlPr><w:attr w:name=\"displayStyle\" w:val=\"false\"/><w:attr w:name=\"altTextString\" w:val=\"m = 5\"/></w:customXmlPr><w:r><w:t>m = 5</w:t></w:r></w:customXml><w:r><w:t>. </w:t></w:r></w:p></w:body></w:document>","relationship":null}],"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","target":"/matlab/document.xml","relationshipId":"rId1"}]}

<div style = "text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; "><div style="block-size: 42px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 21px; transform-origin: 407px 21px; vertical-align: baseline; "><div style="font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; "><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 115.775px 7.79167px; transform-origin: 115.775px 7.79167px; unicode-bidi: normal; ">Write a function that takes an integer n<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 94.9083px 7.79167px; transform-origin: 94.9083px 7.79167px; unicode-bidi: normal; "> and finds the smallest integer m<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 93.75px 7.79167px; transform-origin: 93.75px 7.79167px; unicode-bidi: normal; "> whose factorial is divisible by n<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 52.1083px 7.79167px; transform-origin: 52.1083px 7.79167px; unicode-bidi: normal; ">. For example, if <img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFgAAAAkCAYAAAANdf2OAAAB/ElEQVRoge2Z/Y2DMAzF3w5skAW6ABMwARt0AzboCszQEdiBFZiBFXp/YCtWLqR2Sz9y558UVWpMGl6M80gBx3Ecx3Ecx05LTUsDoAMwUOteMam/QAtgAnADcFZeMwBYAYx0fQdgpuZCEwFRWG4agUeKHZPvG2yi3+AiI2ATkz+1Ancitsn099S37PT/S1roBV4obtrpb8RYl6MmWDtagWX2DoW4GTGLHegFHkVcqcbKuJNlIicaWA7eYKs7NdsUrcByQywJNyjHAygg3Wl76usQd03NyqYERA/5TLN41xxageV9agVOncYuXFdWxKxdED3gI4Vd3tgzTetdNfPQChwKcdKVXLWT4N3zShOSNkRO0JJNR2Wwqc5lsAq8GsZTCRySCXDmMvxIcHbXxiMClzK4h1FgecGSmcTVMtgXohVY7jeH1mAWcM9gH1ULP8VHXQQQV27NDCwnV3psctTmIi4irvSb2rhfP55Ldx7skbeW2lxEp4zjTFftSXI1co8F2ze2Z5Ysrs1FAC84iyi9V0t30dLgE56/4XdjEZizeM9J9DBkr1yN3OGGNNQB22L0mbhvR/voM6XzYM5w1RuttGe5Yi37a3UR/E8E38MM3abJpTP9R2OF4bigRaxze5yp3+ogvoF7tf3eIx4QD7qOcDOO4ziO4ziO4zh2fgDfYDRyWq4WoQAAAABJRU5ErkJggg==" alt="n = 10" style="width: 44px; height: 18px;" width="44" height="18"><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 145.458px 7.79167px; transform-origin: 145.458px 7.79167px; unicode-bidi: normal; ">, then the smallest factorial that is a multiple of n<span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 70.2px 7.79167px; transform-origin: 70.2px 7.79167px; unicode-bidi: normal; "> is 5! = 120; therefore, <img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFAAAAAkCAYAAAAeor16AAAB50lEQVRoge2YXbGDMBCFjwccYCAGUFAFdYADHNRCNVQCHmoBDbFw70OywyE3UJJLJ8nMfjN5aM8Ay2b/CKAoiqIoytfpSxvQAtPBmgva1QR3AD8H617OtDZY/Joj6wmgK2da/Uj0qZMyeQN4lTaiVQa46JvhmsVQ1pz2mPG3YVgAD1wwuhgAN2w7UOd/T14LEa2Fnezh0nev81rE3/GQAc77fKPRawauU7FmSGNjLGlnn3s0h51duVHTw21+LCKzgoGdaLA67+aXaDfSpoh2lilieM5K2bQ9BmwDZUFGh5adWLA6SHaCh87+g5Zi9BUReNUo0mGbUcmpbP2FL38jDmOJzjeco7lGPrE6vnUMVgc+ci+U9s7IzixwDmMk9JMeWDHyrklz4ojVge9A60iz2KZMj3+EfKVIbU5yIHeisChzjRsPtNRaVLoL7yEOPJ1RHGGxIxypcfZAyzn6qakLM/JOpzOKoyh2hCM1Lqx9rEnNbLkLw9/LInGM4QgLL+LmEg6XfaDJYF3zCcenrybJiqSzQB5f9m4Ycy4P0AYujWv+nJNDBFnhmZ800rDOH8IRFvO6tPRYjeMaZlG384Tws836/xa4d02up1yHYogWc07ntRF1p22IwbaGyqepoiiKoiiKoijf4heEDAgKEaRAeAAAAABJRU5ErkJggg==" alt="m = 5" style="width: 40px; height: 18px;" width="40" height="18"><span style="block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 3.88333px 7.79167px; transform-origin: 3.88333px 7.79167px; unicode-bidi: normal; ">. </div></div></div>

Solve

Solution Stats

33 Solutions
10 Solvers

Last Solution submitted on Nov 25, 2022

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

David Hill on 3 Jun 2021

Chris, please check test 21. The factors of 1535238 include two 67's, therefore it seems to me the solution should be 134.

Are Mjaavatten on 3 Jun 2021

David: Take another look. ChrisR's anti-lookup trick lets correct solutions pass the test!

ChrisR on 3 Jun 2021

David, you are correct for Kempner(1535238), but that test asks for Kempner(Kempner(Kempner(1535238))).

Rafael S.T. Vieira on 25 Nov 2022 at 22:00

Unfortunately, it does not stop lookup tables since 134 factors to 2 and 67, which means it obtains the same result as a lookup table. Kempner(Kempner(Kempner(1535238))) will do 134 -> 67 -> 67 and a lookup table 67->67->67.

Rafael S.T. Vieira on 25 Nov 2022 at 22:04

May I suggest using Kempner(Kempner(Kempner(123456787654321))+10) as a test against lookup tables?

Problem Recent Solvers10

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 51950. Find the smallest integer m such that n divides m!

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers10

Suggested Problems

More from this Author172

Problem Tags

Community Treasure Hunt

Problem 51950. Find the smallest integer m such that n divides m!

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers10

Suggested Problems

More from this Author172

Problem Tags

Community Treasure Hunt

Players