Problem 48075. Play PRIMEGAME

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>Have you ever used the </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/45367\"><w:r><w:t>Sieve of Eratosthenes</w:t></w:r></w:hyperlink><w:r><w:t> and said, \"I wonder whether there’s a </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>less</w:t></w:r><w:r><w:t> efficient way to find prime numbers.\"? No? Neither have I. </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>Nevertheless, let’s consider PRIMEGAME, a creation of John Conway that is somewhat less well known than the </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/groups/2/problems/52\"><w:r><w:t>Game of Life</w:t></w:r></w:hyperlink><w:r><w:t>. PRIMEGAME uses the fractions</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1]]></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>You start with a number and choose the first fraction in the list that—when multiplied by the starting number—yields an integer. If the starting number is 2, then the first fraction fitting the rule is 15/2, and the product is 15. </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>In the third step, the next fraction is 55/1, and the product is 825. In the fourth, the fraction is 29/33, and the product is 725. The first twenty steps give</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4]]></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>Notice that the 20</w:t></w:r><w:r><w:t>th</w:t></w:r><w:r><w:t> number is </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=\"2^2\"/></w:customXmlPr><w:r><w:t>2^2</w:t></w:r></w:customXml><w:r><w:t>--that is, 2 raised to the first prime number. If you continue another 50 steps, you get 2 to the second prime number (3), or 8. Another 210 steps give 2 raised to the third prime number (5), or 32. In fact, all exponents in powers of 2 that appear in the sequence are prime numbers. So, PRIMEGAME generates the primes! Painfully slowly!</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 find the nth number generated by PRIMEGAME if the first number is 2.</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: 380.867px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407.5px 190.433px; transform-origin: 407.5px 190.433px; vertical-align: baseline; "><div style="block-size: 42px; 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: 384.5px 21px; text-align: left; transform-origin: 384.5px 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: 75.85px 7.66667px; transform-origin: 75.85px 7.66667px; unicode-bidi: normal; "><span style="">Have you ever used the </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/problems/45367"><span style=""><span style="">Sieve of Eratosthenes</span></span></a><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: 119.042px 7.66667px; transform-origin: 119.042px 7.66667px; unicode-bidi: normal; "><span style=""> and said, "I wonder whether there’s a </span></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: 12.45px 7.66667px; transform-origin: 12.45px 7.66667px; unicode-bidi: normal; "><span style="font-style: italic; ">less</span></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: 82.7167px 7.66667px; transform-origin: 82.7167px 7.66667px; unicode-bidi: normal; "><span style=""> efficient way to find prime numbers."? No? Neither have I. </span></span></div><div style="block-size: 42px; 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: 384.5px 21px; text-align: left; transform-origin: 384.5px 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: 351.1px 7.66667px; transform-origin: 351.1px 7.66667px; unicode-bidi: normal; "><span style="">Nevertheless, let’s consider PRIMEGAME, a creation of John Conway that is somewhat less well known than the </span></span><a target='_blank' href = "https://www.mathworks.com/matlabcentral/cody/groups/2/problems/52"><span style=""><span style="">Game of Life</span></span></a><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: 103.442px 7.66667px; transform-origin: 103.442px 7.66667px; unicode-bidi: normal; "><span style="">. PRIMEGAME uses the fractions</span></span></div><div style="background-color: rgb(247, 247, 247); block-size: 20.4333px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404.5px 10.2167px; transform-origin: 404.5px 10.2167px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; "><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; 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; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 350.35px 8px; tab-size: 4; transform-origin: 350.35px 8px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; ">17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1</span></span></div></div><div style="block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384.5px 21px; text-align: left; transform-origin: 384.5px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; 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: 367.708px 7.66667px; transform-origin: 367.708px 7.66667px; unicode-bidi: normal; "><span style="">You start with a number and choose the first fraction in the list that—when multiplied by the starting number—yields an integer. If the starting number is 2, then the first fraction fitting the rule is 15/2, and the product is 15. </span></span></div><div style="block-size: 42px; 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: 384.5px 21px; text-align: left; transform-origin: 384.5px 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: 380.75px 7.66667px; transform-origin: 380.75px 7.66667px; unicode-bidi: normal; "><span style="">In the third step, the next fraction is 55/1, and the product is 825. In the fourth, the fraction is 29/33, and the product is 725. The first twenty steps give</span></span></div><div style="background-color: rgb(247, 247, 247); block-size: 20.4333px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404.5px 10.2167px; transform-origin: 404.5px 10.2167px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; "><div style="background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 0.666667px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 0.666667px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 0.666667px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 0.666667px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; 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; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; white-space: nowrap; "><span style="block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 361.9px 8px; tab-size: 4; transform-origin: 361.9px 8px; unicode-bidi: normal; white-space: pre; margin-right: 45px; "><span style="margin-inline-end: 0px; margin-right: 0px; ">2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4</span></span></div></div><div style="block-size: 84px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384.5px 42px; text-align: left; transform-origin: 384.5px 42px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; 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: 54.8417px 7.66667px; transform-origin: 54.8417px 7.66667px; unicode-bidi: normal; "><span style="">Notice that the 20</span></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: 5.83333px 7.66667px; transform-origin: 5.83333px 7.66667px; unicode-bidi: normal; "><span style="">th</span></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: 34.6167px 7.66667px; transform-origin: 34.6167px 7.66667px; unicode-bidi: normal; "><span style=""> number is </span></span><span style="vertical-align:-5px"><img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAB8AAAAmCAYAAAA820BcAAACFklEQVRYR+1WOy9EQRTe/QvodOiJ0NEoEEoS/AKh02yC2vMHeFVKEi1BoyASoVEpPP6BV/wAvk9mZO65Z+6dnd2bLexNTmb3zJnznfnO495yqYFPuYHYpSZ4EewPGKcPWF81gCJoXwHQkgP2jt+LkCMZRL3BCdxpwD+xTkJ2TCAzWA9cBuoJ3grHj5AWQbFl4gz60WrAO0z0Q+bQB9YLjULouiHtkBMBztxfQu4g/aHgFRhuaIUC3TNkAnLv2XfVFnwbyvkQ8FmTK4LsmQO9WKecw9wbhrzkBGB9jUtWtJyTalLESJeFY+4dQvqMflWxkbGcGkUi39Rp4KSbOU4ZGyeWRv5N5VEgW9s26FO9roHfwnABcpVB5xP22FLsYVnd9hir/wbirQ0NnFWbV0ikcgTCvHd5gqTNPiTR265tbJ9b8FQFG+db5gK7IrDExWLBv43TQSU9BOaTaCv8JzAr/08fAz4GB8cQVv20uJmdDZxm8mGaetyUxoBbyllwbo/zZr6hxEBoGzRklMB/VfbWqYHhO5Clr+bmdvisw+FmDJg8EwrOniXd5xA59aLjCAEvBJgR54EXBhwCzun0JqtUaa9r6LLGsZqarJtzWPDln/gAEF44NNYgvvmeWQ8+cALPBVZSyGs1+ObVANOpHDaBMesFZ7+3Q5x8wSjvDej1k1ftIQFE2zTBo6mr5WCT9lrYiz77f2n/AQK+XSdneCf8AAAAAElFTkSuQmCC" alt="2^2" style="width: 15.5px; height: 19px;" width="15.5" height="19"></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: 275.35px 7.66667px; transform-origin: 275.35px 7.66667px; unicode-bidi: normal; "><span style="">--that is, 2 raised to the first prime number. If you continue another 50 steps, you get 2 to the second prime number (3), or 8. Another 210 steps give 2 raised to the third prime number (5), or 32. In fact, all exponents in powers of 2 that appear in the sequence are prime numbers. So, PRIMEGAME generates the primes! Painfully slowly!</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: 384.5px 10.5px; text-align: left; transform-origin: 384.5px 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: 276.783px 7.66667px; transform-origin: 276.783px 7.66667px; unicode-bidi: normal; "><span style="">Write a function to find the nth number generated by PRIMEGAME if the first number is 2.</span></span></div></div></div>

Have you ever used the Sieve of Eratosthenes and said, "I wonder whether there’s a less efficient way to find prime numbers."? No? Neither have I. 
Nevertheless, let’s consider PRIMEGAME, a creation of John Conway that is somewhat less well known than the Game of Life. PRIMEGAME uses the fractions
17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55/1
You start with a number and choose the first fraction in the list that—when multiplied by the starting number—yields an integer. If the starting number is 2, then the first fraction fitting the rule is 15/2, and the product is 15. 
In the third step, the next fraction is 55/1, and the product is 825. In the fourth, the fraction is 29/33, and the product is 725. The first twenty steps give
2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4
Notice that the 20th number is --that is, 2 raised to the first prime number. If you continue another 50 steps, you get 2 to the second prime number (3), or 8. Another 210 steps give 2 raised to the third prime number (5), or 32. In fact, all exponents in powers of 2 that appear in the sequence are prime numbers. So, PRIMEGAME generates the primes! Painfully slowly!
Write a function to find the nth number generated by PRIMEGAME if the first number is 2.

Solve

Solution Stats

55 Solutions
8 Solvers

Last Solution submitted on Aug 30, 2021

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Nikolaos Nikolaou on 7 May 2021

lol this one was something :)

Problem Recent Solvers8

Problem Tags

conway primes sequence

Community Treasure Hunt

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

Start Hunting!

Problem 48075. Play PRIMEGAME

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author156

Problem Tags

Community Treasure Hunt

Problem 48075. Play PRIMEGAME

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers8

Suggested Problems

More from this Author156

Problem Tags

Community Treasure Hunt

Players