wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Substract-a-Prime
        
(Message started by: JocK on Jan 27^th, 2006, 11:00am)

Title: Substract-a-Prime
Post by JocK on Jan 27^th, 2006, 11:00am

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?

Title: Re: Substract-a-Prime
Post by Sjoerd Job Postmus on Jan 27^th, 2006, 12:02pm

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.

Title: Re: Substract-a-Prime
Post by Eigenray on Jan 27^th, 2006, 9:09pm

Looks like [hide]529 is the only one below 10000[/hide].

Edit: You can also substract 2 from
167², 229², 241², 269², or 271².

Interestingly, given one more term than you can get [link=http://www.research.att.com/~njas/sequences/A025043]here[/link], the answer would have been obvious (assuming you've worked out the first few primes squared already).

Title: Re: Substract-a-Prime
Post by ChunkTug on Jan 27^th, 2006, 9:26pm

[hide]Start with 529 and subtract 2.[/hide]

I believe this would win. (By "believe" I mean that I trust the correctness of my program).

Title: Re: Substract-a-Prime
Post by JocK on Jan 28^th, 2006, 12:34am

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?

Title: Re: Substract-a-Prime
Post by ChunkTug on Jan 28^th, 2006, 11:11am

Edit: Retracting "proof" based on an "Oops!" :P

Title: Re: Substract-a-Prime
Post by Eigenray on Jul 16^th, 2008, 12:27pm

on 01/28/06 at 00:34:49, 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 p² is a winning number, and e = p² - q is losing, for odd primes p,q. Since e is even, e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif E is either 0 (absurd) or congruent to 1 mod 3. But p>3, so we also have p² = 1 mod 3, meaning q = p²-e is divisible by 3, forcing q=3. But e+3 is not of the form p² for any e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif E, a contradiction.

Now, evidence for the conjecture: I have verified it up to 10⁷ (edit: 10⁹*). 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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif 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)² twin primes {p,q} below M. If e-p isn't in E+P, then either e-p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif L, or e-p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif L+2, in which case e-q http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif L. So the only way e http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif L is if e-p http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif 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 10⁹, and only requires checking 2638 odd numbers for membership in L. In fact, every other even below 10⁹ is ruled out by an element of L below 8130, so it's very unlikely any more evens can slip in.