3 ms·

Prime Run: a game about adding and subtracting prime numbers

13 points by sohkamyung 4y ago

MauranKilom 4y ago
(Disclaimer: Didn't read the article, just played the game straight away.) Played until level 20 using a fairly basic heuristic ("click largest prime number that gets you closer, until you can find a clear solution path"). Without a limit or goal on number of steps to the target, it loses replay value relatively fast. You can always reach divisibility by two in at most one step and divisibility by three in at most two steps * (etc.), so any target with small prime factors is trivially reached once you land in the vicinity by just repeatedly adding its smallest prime factor. If there's no small prime factors in your target, apply the above rule backwards from the target and you're in easy territory again. There's often shortcuts (e.g. you're 18 away from the target - you can replace 5x -2 with 2x -5 at some point along that route, and/or 3x -2 with 2x -3). Finding optimal routes seems arduous by hand (even if I had memorized primes above 100, finding the remainders of your target and the possible steps remains intractable to me), but it might be an interesting programming exercise. I wonder if there is an even better solution than the obvious graph traversal one. * Well, assuming you want to go a certain direction. Divisibility by three is technically also always just one step away.
randlet 4y ago
Tangentially related, but my family (kids are 7-10) enjoys the "Prime Climb" [1] board game which deals with prime numbers. [1] https://boardgamegeek.com/boardgame/159375/prime-climb https://boardgamegeek.com/boardgame/159375/prime-climb
rrobukef 4y ago
For any number up to 4x10^18, the solution is less than 4 steps. Use Goldbach's conjecture to split both numbers in a sum of two primes. Go from the source to 0, go from 0 to the target. EDIT: Use goldbach's theorem on the difference between both numbers.
- jameshart 4y ago
  Sadly, you are only allowed to use prime factors of the current number, not arbitrary primes.

13 points by sohkamyung 4y ago

(Disclaimer: Didn't read the article, just played the game straight away.) Played until level 20 using a fairly basic heuristic ("click largest prime number that gets you closer, until you can find a clear solution path"). Without a limit or goal on number of steps to the target, it loses replay value relatively fast. You can always reach divisibility by two in at most one step and divisibility by three in at most two steps * (etc.), so any target with small prime factors is trivially reached once you land in the vicinity by just repeatedly adding its smallest prime factor. If there's no small prime factors in your target, apply the above rule backwards from the target and you're in easy territory again. There's often shortcuts (e.g. you're 18 away from the target - you can replace 5x -2 with 2x -5 at some point along that route, and/or 3x -2 with 2x -3). Finding optimal routes seems arduous by hand (even if I had memorized primes above 100, finding the remainders of your target and the possible steps remains intractable to me), but it might be an interesting programming exercise. I wonder if there is an even better solution than the obvious graph traversal one. * Well, assuming you want to go a certain direction. Divisibility by three is technically also always just one step away.

randlet 4y ago

Tangentially related, but my family (kids are 7-10) enjoys the "Prime Climb" [1] board game which deals with prime numbers. [1] https://boardgamegeek.com/boardgame/159375/prime-climb https://boardgamegeek.com/boardgame/159375/prime-climb

rrobukef 4y ago

For any number up to 4x10^18, the solution is less than 4 steps. Use Goldbach's conjecture to split both numbers in a sum of two primes. Go from the source to 0, go from 0 to the target. EDIT: Use goldbach's theorem on the difference between both numbers.

jameshart 4y ago
Sadly, you are only allowed to use prime factors of the current number, not arbitrary primes.