Visiting primes on a line

Recently I have been playing a great mobile game called Dicast: Rules of Chaos and it has inspired me to make this puzzle.

This puzzle proceeds on an infinite number line, where each integer is represented as a cell. You start on the cell marked 0. You have the following ten cards available:

• One: moves you 1 cell to the right
• Two: moves you 2 cells to the right
• Three: moves you 3 cells to the right
• Four: moves you 4 cells to the right
• Five: moves you 5 cells to the right
• Six: moves you 6 cells to the right
• Minus: moves you 1 cell to the left
• Odd: moves you 1, 3 or 5 cells to the right. The number is chosen uniformly at random
• Even: moves you 2, 4 or 6 cells to the right. The number is chosen uniformly at random
• Random: moves you 1, 2, 3, 4, 5 or 6 cells to the right. The number is chosen uniformly at random

The cards take you straight to the final destination, so you do not visit any other cells in between. You can use each card once and play them in any order. How can you play the cards to guarantee that you land on the most number of distinct primes? In other words, what is the most number of distinct primes can you land on, no matter which random numbers are chosen? Good luck!

• If I visit the same prime cell twice (e.g. by using +1 then -1), does it count as two visits? – Bubbler Oct 26 '20 at 3:18
• Ah good question. It will count as one visit. I will correct the text now. – Dmitry Kamenetsky Oct 26 '20 at 4:08

I think the best we can get is

6 primes

in total.

One possible strategy

Start by trying to generate as many primes as possible using only the non-random cards. Since all primes except 2 are odd, and we start at 0 (which is even), we can only step over at most five odd primes (odd, even, even, even, odd+odd). But if we step over 2, we can make the best use of odd cards by going this way: odd, odd (2), odd, even, even, even, which is indeed possible: $$0 \to 3 \to 2 \to 7 \to 11 \to 13 \to 19$$, by using cards $$3, -1, 5, 4, 2, 6$$ in order. Since we have seven cards (which would give 7 primes if every single step gives a prime) and the sum of 7 cards is 20 (composite), 6 primes is optimal at this point.

After stepping on the 6 primes (where the current number is either 17 or 19), you have four cards: a 1 or 3, Odd, Even, and Random. If your remaining constant is 1, the random cards can force you to get either $$6k+2$$ or $$6k+3$$ so that the result as well as its $$+1$$ is composite; if you have 3, the randoms can force you to a multiple of 3. Therefore, you can't guarantee any more primes at this point, so the best you can get is 6 primes.

Why other strategies won't get further

Not a rigorous argument, but a possible reason is this:

Using the seven number cards, we can get at most 6 primes because the sum of all of them is composite. If we insert any of the random cards in between, it is very likely that the "devil" can pick a number from the random pool so that the turn is composite AND the overall sum remains composite (therefore it adds zero primes however we try). The only exceptions I can think of are 2+Odd and 1+Even, but 1 is not a prime (losing a prime in the way) and 2+Odd loses maximum utility if we stepped over 3 before the Odd (just like the 6-primes solution already presented).

Computer verification

I could verify that the optimal result is indeed

6 primes, using a naive Python 3 program. The linked version uses only 9 cards (excluding the Random card), and it took ~20 minutes to run the full code on my local machine.

If you remove the history check, you get 7 primes. (Unfortunately the program doesn't show the optimal moves.) Apparently the optimal move makes use of both Odd and Even; without either of them the optimal score is 6.

• Well done you got it! This is the same as my solution. Note rot13(Vagrerfgvatyl lbh pna npghnyyl znxr hfr bs gur enaqbz pneqf, ohg vg fgvyy bayl tvirf 6 cevzrf. Lbh pna qb guerr, zvahf, svir, sbhe, fvk, juvpu tvirf lbh 5 cevzrf. Abj lbh pna qb bqq juvpu yrnqf lbh gb bar bs (18, 20, 22). Sebz urer qb bar naq gjb. Lbh jvyy rvgure trg (19->21), (21->23) be (23->25). Rnpu bs gurfr guerr cbffvovyvgvrf pbagnvaf bar zber cevzr.) – Dmitry Kamenetsky Oct 26 '20 at 6:18
• That's a very nice program! – Dmitry Kamenetsky Oct 26 '20 at 7:23