Author |
Topic: Substract-a-Prime (Read 718 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Substract-a-Prime
« on: Jan 27th, 2006, 11:00am » |
 Quote  Modify
|
In the game "subtract-a-prime," a positive integer is written down and two players alternate moves. A move consists of subtracting a prime number from the current value, producing a new current value for the other player. A player may not subtract more than the current value. A player unable to move loses.
Would you be willing to play this game (for a small stake against a skilled opponent) under the condition that you have to start, but are given the freedom to choose the starting number provided this number is the square of an odd prime?
|
| « Last Edit: Jan 27th, 2006, 11:06am by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Substract-a-Prime
« Reply #1 on: Jan 27th, 2006, 12:02pm » |
Quote Modify
|
I would not.
I wish I could start at 2^2... giving us 4, then substract 3... and win.
Ok, so let's take a look at 3^2... giving us 9. Substracting 7 is no use, because I'll lose.
Substracting 5 will leave us with 4, him taking 3 and win..
Substracting 3 will leave us with 6, him taking 5 and win.
So, 2 and 3 are miss.
5?
25 - 23, is stupid, leaving 2
25 - 19, leaves 6. He takes 5.
25 - 17, leaves 8. He takes 7.
25 - 13, leaves 12. He takes 11.
25 - 11, leaves 14. He takes 13.
25 - 7, leaves 18. He takes 17.
25 - 5, leaves 20. He takes 19.
25 - 3, leaves 22. He takes... Further analizing required.
25 - 3, leaves 23. Stupid
22 left?
22 - 19 = 3. Loss for him, he won't choose 19.
22 - 17 = 5. Loss for him, he won't choose 17.
22 - 13 = 9. Whatever I answer, he'll win <~ His choice.
So, any odd prime < 6, will cause our loss. I'll just let you continue puzzling in theoretics.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Substract-a-Prime
« Reply #2 on: Jan 27th, 2006, 9:09pm » |
Quote Modify
|
Looks like 529 is the only one below 10000.
Edit: You can also substract 2 from
1672, 2292, 2412, 2692, or 2712.
Interestingly, given one more term than you can get here, the answer would have been obvious (assuming you've worked out the first few primes squared already).
|
| « Last Edit: Jan 28th, 2006, 1:15am by Eigenray » |
IP Logged |
|
|
|
ChunkTug
Full Member
Gender:
Posts: 166
|
|
Re: Substract-a-Prime
« Reply #3 on: Jan 27th, 2006, 9:26pm » |
Quote Modify
|
Start with 529 and subtract 2.
I believe this would win. (By "believe" I mean that I trust the correctness of my program).
|
| « Last Edit: Jan 27th, 2006, 9:29pm by ChunkTug » |
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Substract-a-Prime
« Reply #4 on: Jan 28th, 2006, 12:34am » |
Quote Modify
|
You guys are quick, Eigenray and Chunktug!
What about a further restriction:
The starting number has to be the square of an odd prime, and the very first move in the game is restricted to the substraction of an odd prime.
Would you still be willing to start?
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
ChunkTug
Full Member
Gender:
Posts: 166
|
|
Re: Substract-a-Prime
« Reply #5 on: Jan 28th, 2006, 11:11am » |
Quote Modify
|
Edit: Retracting "proof" based on an "Oops!" 
|
| « Last Edit: Jan 28th, 2006, 11:35am by ChunkTug » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Substract-a-Prime
« Reply #6 on: Jul 16th, 2008, 12:27pm » |
Quote Modify
|
on Jan 28th, 2006, 12:34am, JocK wrote:| Would you still be willing to start? |
|
No. But I have only heuristics to back that up:
Let L be the set of all losing numbers:
L = {0, 1, 9, 10, 25, 34, 35, 49, 55, 85, 91, 100, 115, 121, 125, 133, 145, 155, 169, 175, 187, ... }
Conjecture: The only even elements of L are E = {0, 10, 34, 100, 310}.
Assume the conjecture holds. Suppose p2 is a winning number, and e = p2 - q is losing, for odd primes p,q. Since e is even, e  E is either 0 (absurd) or congruent to 1 mod 3. But p>3, so we also have p2 = 1 mod 3, meaning q = p2-e is divisible by 3, forcing q=3. But e+3 is not of the form p2 for any e E, a contradiction.
Now, evidence for the conjecture: I have verified it up to 107 (edit: 109*). Suppose the conjecture is true below some large number M; let's restrict our attention now to the odd numbers below M. Any odd nuber is either losing, in which case it is in L, or it is winning, in which case it is in either L+2 or E+P = {e+p : e E, p prime}. That is, the sets L, L+2, and E+P contain every odd number below M, so
|L| + |L+2| + |E+P| > M/2.
Since |E+P| < |E|pi(M) ~ 5M/log M, if |L|=N, say, we have
N > M/4 ( 1 - 20/log M).
A better guess would be
N > M/4 ( log M - 10)/( log M - 5),
which is what we get if we assume that the elements of E+P are random, so the fraction N/(M/2) of them are already in L+2 (note that E+P and L are disjoint). For M=10^7, this guess gives N > 1375706, compared to the actual value N = 1741797. (For 'small' M, E+P will have lots of numbers counted twice; if we use the actual size of E+P, instead of |E|*pi(M), the guess gives N ~ 1725033, which is pretty accurate.)
But we can see that for M very large, L contains almost half the odd numbers below M. But this means that if e is the smallest even number greater than M, and the numbers e-p are randomly distributed, then the probability that none of them are in L is vanishingly small: less than (2/3)M/log M, say, and summing this over all M > 10^7 gives a very tiny chance of the conjecture failing.
Another argument is: there are probably > .6 M/(log M)2 twin primes {p,q} below M. If e-p isn't in E+P, then either e-p L, or e-p L+2, in which case e-q L. So the only way e L is if e-p E+P for every twin prime below M, and the probability of this is only (10/log M).6 M/(log M)^2, which also sums to negligible number for M > 10^7.
*Edit: Just rethought my program. Rather than compute L in its entirety, I just check each even number, computing L (recursively with memoization) only as necessary. This takes about 1 minute to verify there are no other evens below 109, and only requires checking 2638 odd numbers for membership in L. In fact, every other even below 109 is ruled out by an element of L below 8130, so it's very unlikely any more evens can slip in.
|
| « Last Edit: Jul 16th, 2008, 8:19pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print