Problem 50811. Compute the nth term from the Sieve of Flavius Josephus

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>To apply the Sieve of Eratosthenes, start with the natural numbers (skipping 1), keep the first number (i.e., 2), and delete all multiples (4, 6, 8, 10, etc.). Then repeat: keep the first remaining number (3) and delete all multiples (9, 15, 21, etc.). The remaining numbers are the primes. </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>To apply the Sieve of Flavius Josephus, start with the natural numbers. On the </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=\"k\"/></w:customXmlPr><w:r><w:t>k</w:t></w:r></w:customXml><w:r><w:t>th step, remove every </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=\"(k+1)\"/></w:customXmlPr><w:r><w:t>(k+1)</w:t></w:r></w:customXml><w:r><w:t>st term remaining after the </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=\"(k-1)\"/></w:customXmlPr><w:r><w:t>(k-1)</w:t></w:r></w:customXml><w:r><w:t>st step. So, on the first step, remove every second number (2, 4, 6, 8, etc.) to leave 1, 3, 5, 7, 9, 11, 13, 15, 17…On the second step, remove every third number (5, 11, 17, etc.) to leave 1, 3, 7, 9, 13, 15, 19,… </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>Write a function to compute the </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>th term in the sequence remaining after the Sieve of Flavius Josephus is applied.</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: 165px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 82.5px; transform-origin: 407px 82.5px; vertical-align: baseline; "><div style="block-size: 63px; 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 31.5px; text-align: left; transform-origin: 384px 31.5px; 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: 381.5px 8px; transform-origin: 381.5px 8px; unicode-bidi: normal; "><span style="">To apply the Sieve of Eratosthenes, start with the natural numbers (skipping 1), keep the first number (i.e., 2), and delete all multiples (4, 6, 8, 10, etc.). Then repeat: keep the first remaining number (3) and delete all multiples (9, 15, 21, etc.). The remaining numbers are the primes. </span></span></div><div style="block-size: 63px; 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 31.5px; text-align: left; transform-origin: 384px 31.5px; 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: 247.5px 8px; transform-origin: 247.5px 8px; unicode-bidi: normal; "><span style="">To apply the Sieve of Flavius Josephus, start with the natural numbers. On the </span></span><span style="font-family: &quot;STIXGeneral&quot;, &quot;STIXGeneral-webfont&quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);">k</span><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.5px 8px; transform-origin: 70.5px 8px; unicode-bidi: normal; "><span style="">th step, remove every </span></span><span style="vertical-align:-5px"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFwAAAAlCAYAAADPwo5RAAACbElEQVRoge2ZbZHCMBCGHw91gAEMVEEV4AAHdYAFNCChHrCAhlrgfqRLcz2gu/ng0rs8Mx1mICWbN9vdzRYqlUql8l9ogONvG1EQB5wmWWiAAdjnmmCD7MmkSQNcFX/cAC3uKbiQcfc/hEbIPXBTjlUzAP2b3xvgjNuU+3RdUxrwYQ44ES/K8S1uvUkcrJ8m17BjFvyUYvIP0+HWKmvQCs40NnrNDTDidlxDy2xsGzv5hznhQuGRMMHF2aLWbfFuGS/G5kLmsIhhJURwcKE3yq4R22My4AwdYiZdoWTBD9N9u5BJu+nmznCPGPouwcZSsuASVoLOKqfpZm3mlQ3KHb9LFhxcVAiyTcKDFtmg0fvuME3ue35svVq64AO2vPdgxBaLpQZfGimJNyiuPWELggcVDZbk1zAb6ccv8fCUlC642Gd2MIvgkp3vzCHjSFjylPbAq+vs2fZuXMwTlUJwcx6zCC4ijMzH/NBKxT88xVwxXc3iBZfj8IU5locuWDpwry6Za1wZZylnl8QIbq3uHtzQCb7nu2eN0+ctZFIFpcfw4KSpvdHvPbTMO2w9NGnZguBBnVJttpU6W2pPv2OY44hfuuB3XA4zI6FizUslhPiT+IcdqVoaAg1ZULLgopm2u/qDG+9F8iuK7sX3A07sS4whHiUL3jNXakGs/YHfjl2O8WO55e2Jxqacgvtrsp6Q1xx0lbUXECecB79q4fasv56zkktwORU/KzE1PaAWp1V0C6Mj8jFJTIsTIEV4SsmVhI51Jk3C+6vIk5yUgfK8qgSSvrFfcqaK7iNtiKzhNsfpcatULSqVSqVSycUXm/MeGpHoq6sAAAAASUVORK5CYII=" alt="(k+1)" style="width: 46px; height: 18.5px;" width="46" height="18.5"></span><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: 23.5px 8px; transform-origin: 23.5px 8px; unicode-bidi: normal; "><span style="">st term remaining after the </span></span><span style="vertical-align:-5px"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAFwAAAAlCAYAAADPwo5RAAACUUlEQVRoge2aa5HCMBRGj4c6WAM1UAVVgAMc1AEW0ICEesACGmqB/ZFcGtiFJvf2lSFnprMzbEKSL8l9FSgUCoXCt1ABx60nsSMOOE0WoQJ6oF5qgAypWUiTCrhGfHEFNLhbcGHB3V+JGCFr4BbZNpoe6D78vwLOuE25++c65wRW5oAT8RLZvsGtd5YD1vnBY/hhFPw0x+Ar0+LWKmuIFRzf1rzmChhwOx5DwzjZxjr4ypxwpvCITnA5bKZ1p5xuaS+TzRmN4OBMb2qfJwbSrkmPm2hvGXQHaAU/+H4/mkFb37lN6CMT/eRgc0AruJgVVa5y8p1jPa9sUI72+xWt4OCsgsqsiHmIRTZoCD47+MHDk59D4mQRvCfN7z0YSLPFEoO/TlIcr8qubYRVcFXQkOL8KsZJhvZLTnhuWASXSC35gKUILt75zmgyjuidZ43zA5bHkvXNIXiyH0sR/MxovyXNt0Qqci0tj8VX7F5wSYcvjLbcUsY9+bEtj8VnWARPje4e3IgTvOb5ZA3+700z6E7YxGnGdgxrDw3jDqcmTXvCKriqUhrrbSXOltgzrBjmmuJbBL/jfFgyYiqmTqmYkHCQMNkR51WhnMgGaAUXzWKrq3+48VmksBzbvvm8x4l9sUxkZbSCd4yRmoqpLwjLsa9tQlue8vZka8I1pWbIUwd0kqkXEBK+vSvhdky/ntsLkhX/F2LG1IAanFbmEkaL8Zp8CVdmPFhn8nF4WyA3eVZ68nF6azLrG/tXzhTRQ+SHQIua21yzxyUoWhQKhUKhsBS/IqD7vWB5nPkAAAAASUVORK5CYII=" alt="(k-1)" style="width: 46px; height: 18.5px;" width="46" height="18.5"></span><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: 296px 8px; transform-origin: 296px 8px; unicode-bidi: normal; "><span style="">st step. So, on the first step, remove every second number (2, 4, 6, 8, etc.) to leave 1, 3, 5, 7, 9, 11, 13, 15, 17…On the second step, remove every third number (5, 11, 17, etc.) to leave 1, 3, 7, 9, 13, 15, 19,… </span></span></div><div style="block-size: 21px; 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 10.5px; text-align: left; transform-origin: 384px 10.5px; 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: 100.5px 8px; transform-origin: 100.5px 8px; unicode-bidi: normal; "><span style="">Write a function to compute the </span></span><span style="font-family: &quot;STIXGeneral&quot;, &quot;STIXGeneral-webfont&quot;, serif; font-style: italic; font-weight: 400; color: rgb(0, 0, 0);">n</span><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: 254px 8px; transform-origin: 254px 8px; unicode-bidi: normal; "><span style="">th term in the sequence remaining after the Sieve of Flavius Josephus is applied.</span></span></div></div></div>

Solve

Solution Stats

15 Solutions
5 Solvers

Last Solution submitted on May 25, 2021

Last 200 Solutions

Problem Recent Solvers5

Problem Tags

sequence sieve

Community Treasure Hunt

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

Start Hunting!

Problem 50811. Compute the nth term from the Sieve of Flavius Josephus

Solution Stats

Last 200 Solutions

Problem Recent Solvers5

Suggested Problems

More from this Author113

Problem Tags

Community Treasure Hunt

Problem 50811. Compute the nth term from the Sieve of Flavius Josephus

Solution Stats

Last 200 Solutions

Problem Recent Solvers5

Suggested Problems

More from this Author113

Problem Tags

Community Treasure Hunt

Players