Problem 48075. Play PRIMEGAME
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.
Solution Stats
Problem Comments
-
1 Comment
Nikolaos Nikolaou
on 7 May 2021
lol this one was something :)
Solution Comments
Show commentsProblem Recent Solvers14
Suggested Problems
-
Project Euler: Problem 2, Sum of even Fibonacci
2292 Solvers
-
319 Solvers
-
148 Solvers
-
It's going down. We're finding simbers!
71 Solvers
-
Number of Even Elements in Fibonacci Sequence
1272 Solvers
More from this Author278
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!