Project Euler 391

[rollie]

So I took a crack at the latest problem (http://projecteuler.net/problem=391), and feel like I'm getting somewhere with it, but I hit a roadblock. My current thinking is:

The last move played in a game is guaranteed to be the one that reaches the member of S preceding the first one containing n+1 1s (because, by definition, the next member will increase S by n+1). So if n = 5, the last number reached will be the one before 0x111111 (notice n+1 1s, or 6 1s), which is 0x111110. So the first person to 0x111110 wins...my original thinking was that the first person to that is the first person to 0x111110 - (n+1), since from (0x111110 - (n+1)), my opponent is guaranteed to push c to a point where I can get to 0x111110. Then the first to 0x111110 - (n+1) is the first to (0x111110 - (n+1) - (n+1))...which reduces to 0x111110 % (n+1). However, this always results in '0', because my real 'previous step' isn't 0x111110 - (n+1), it's the member of S that is equal to or less than (0x111110 - (n+1)). But for n=1000, the first 'winning number' to calculate is 1000 bits long. My computer isn't fast enough to iterate through S to find the first 'winning number' <= n by backtracking.

Anyone that's had a look at this have any suggestions on how an algorithm might be derived to get this? Note that I deduced an algo to quickly calculate very large values of S (so, calculating S where k = 2^1000 takes < 1s I believe), which I suspect is required in a final solution.

[Script Coder]

Please post question.
Sorry

[ResidentBiscuit]

He posted the link to the question.

[ne555]

I think that you could try
http://en.wikipedia.org/wiki/Nim#The_subtraction_game_S.281.2C2.2C....2Ck.29
normal and misère.

calculating S where k = 2^1000 takes < 1s I believe), which I suspect is required in a final solution.

I don't think that you need a bigger S_k than 1000.

[rollie]

@ne555, If I'm understanding that correctly, that will only work if S grows linearly, which in the Euler problem it does not.

[zycaxi]

removed

[rollie]

From the very beginning S isn't linear, its first few terms being:
1
2
4
5
7
9
12
13
15
17
20
22
25
28
32
33
35
37
40
42

[m4ster r0shi]

rollie wrote:

calculating S where k = 2^1000 takes < 1s I believe

2^1000 is a pretty big number. What algorithm did you use?

This here...

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    const int bigSize = 20000000;
    int curSize = 1;
    int curChunkSize = 1;

    deque<int> s(2 * bigSize); s[0] = 1;

    while (curSize < bigSize)
    {
        for (int i = 0; i < curChunkSize; ++ i)
        {
            s[curSize + i] = s[curSize + i - curChunkSize];
            s[curSize + i + curChunkSize] = s[curSize + i - curChunkSize] + 1;
        }

        curSize += 2 * curChunkSize;
        curChunkSize *= 2;
    }

    int sum = 0;

    for (int i = 0; i < s.size(); ++ i) s[i] = sum += s[i];
    for (int i = 0; i < 400; ++ i) cout << s[i] << " ";
}

...needs ~ 1200ms with speed optimizations enabled.

I hope I'm not approaching this in a terribly stupid way...

[zycaxi]

removed

[rollie]

@r0shi:

I realized an interesting property. If you want to know S(0x11111), which is 'the number of 1s in all the binary representations of the number 0x0 to 0x11111', you can break it into 2 groups:

G1) numbers that start with 0x0..., so 0x01111, 0x01001, etc
G2) numbers that start with 0x1..., so 0x11111, 0x11001, etc

So say I go ahead and compute G1, which would be S(2^4). Now I want to compute S(2^5). It's easy to see that there an equal number of elements in G1 and G2, and all of those elements have identical bits except for the most significant bit; so S(2^5) is going to be at least 2*S(2^4). However, we also need to account for the 1's that are present in all the elements of G2 (each element in G2 has exactly one more "1" than the corresponding element in G1). The number of additional 1s is the number of elements in G2, which also equals the number of elements in G1, or 16 (more generally, calculating for S(2^n), this number will be 2^(n-1)). Thus we have our formula: S(n+1) = 2*S(n) + 2^(n-1), which can be computed in O(logn) if I remember my notation correctly. The following is an implementation; you can assume the 'adjust' variable will always be 0 for powers of 2, but is required for numbers like 'S(0x1001011000)'. It computes S(2^500) in less than 1s; S(1000) causes stack overflow, easy to fix though. UInt32 can be whatever big-int style class you want to use; I have it typedef'd as:
typedef ttmath::UInt<32> UInt32;

UInt32 _S(UInt32 _powerOfTwo, UInt32 adjust)
{
	//cout << "_S - " << _powerOfTwo <<  endl;
	if (_powerOfTwo == 0)
	{
		return adjust;
	}

	UInt32 two = 2;
	two.Pow(_powerOfTwo - 1);

	if (_powerOfTwo == 1)
	{
		return (adjust * 2) + 1;
	}

	return (_S(_powerOfTwo - 1, adjust))*2 + (two) + (adjust * two * 2);
}

UInt32 S(UInt32 _num)
{
	UInt32 ret = 0;
	string str = _num.ToString(2);
	//cout << str << endl;
	UInt32 adjust = 0;
	for (int i = 0; i < str.length(); i++)
	{
		if (str.at(i) == '1')
		{
			ret += _S(str.length() - 1 - i, adjust) + 1;
			adjust++;
		}
	}

	cout << "S = " << ret << endl;
	return ret;
}

int main()
{
	UInt32 test = 2;
	test.Pow(500);
	cout << S(test) << endl;

	return 0;
}

[zycaxi]

removed

[ne555]

S = {1,2,4,5,7,9,12,13,15,17,20,22,25,28,32,33,35,37,40,42,...}
Take the difference
R = {1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2} (¿see a pattern?)
Now the amount of S_k that you can take out (suppose n=5)
P = {4,3,3,3,2,2,2,3,2,2,2,2,1,1,2,3,2,2,2,...}

That can be condensed in
P = {(4,1), (3,3), (2,3), (3,1), (2,4), (1,2), (2,1), (3,1), ...}
There you've got a Nim. Solve it by a dynamic approach (with how many sticks your turn need to start)

Of course, constructing R is not practical (it growths as exponentially).
So you need to construct the chunks in P, based on observation of the binary cyclic pattern.

By instance suppose n=1000
If you've got 501 "ones" you can only take 1 stick at the time. so P ends with (1, 2^499)


Again, just a suggestion, I did not tried to implement it.

[zycaxi]

"Now the amount of S_k that you can take out (suppose n=5)" what?

[ne555]

At every step you need to form an S_k
But if you put a big enough number you could bypass some.

That's when it relates to Nim.
The S form the heap. The number of sticks that you can remove is determined by the biggest number that you can add to the counter.

By instance going from 2 to 12 is equivalent to removing 5 sticks.

[zycaxi]

you can't go from 2 to 12 if n=5. you can go to 4, 5, or 7
n is the max raw number you can add to the current counter, but what you end up on must belong to S

[ne555]

Then suppose n=10.
And you could go from 2 to 12 removing 5 sticks

Or from 2 to 7 removing 3.

[zycaxi]

that approach likely has problems.

have large n, you get big numbers for S, is many turns to play game from counter 0 to counter maximum.

[BMeph]

m4ster r0shi wrote:

What algorithm did you use?

rollie wrote:

Thus we have our formula: S(n+1) = 2*S(n) + 2^(n-1), which can be computed in O(logn) if I remember my notation correctly.

Your formula's right, but it could be more general, specifically,
For n = 2*m+1, S(n) = 2*S(m)+m+1;
For n = 2*m, S(n) = S(m) + S(m-1) + m.
Those work for all n (and m), not just for n = 2^k-1 (and thus, m = 2^(k-1)-1).

You can, though, for certain values, which are the ones we need, do better.
You'd do better to just calculate it directly:

S((2^k)-1) = k*2^(k-1)
Example: S(7[2^3-1]) = 3*2^(3-1) = 3*2^2 = 3*4 = 12.
"It's super effective!" ;)

Also, because of the properties of ones, you also know:
S(2^k) = 1+k*2^(k-1)
S(2^k-2) = k*2^(k-1)-k or k*(2^(k-1)-1) [whichever way makes you feel better]