[RESOLVED] Bit manipulation

[TheBigB]

Hi,

Say I have an x number of bits and I'd like to know all possibilities for that number, but only half of the bits can be toggled at the time.
For 4 bits these would be:

0011
0110
1100
1010
0101
1001

What would be a methodical way of getting those for a bigger x?

Thanks

[ntg]

If I remember my math correctly:

In your specific example, n=4 and k=2. For 8 bits, you'd use n=8 and k=4 thus get a result of 70. Is this correct?

Look up combinations here.

[TheBigB]

OK, so this is the problem

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
How many routes are there through a 20×20 grid?

So basically the rules state that it can go 20 right and 20 down with a lot of different orders of that movement.
Hence toggling half of the bits.
I've worked out that with the values n=40 and k=20 the number should be 137846528800, but that appears to be incorrect.
(assuming n! = 8,15915283247898E+47 and k! = 2,43290200817664E+18)
So is my calculator rounding incorrectly? Have I miscalculated the factorials? Or am I completely missing the point here.

[ntg]

The 137846528800 number is correct. However, I can't really say that the problem is reduced to the same formula for combinatorics. How did you come to the conclusion that the 137846528800 is incorrect?

[TheBigB]

I submitted it, but I got a message saying it's not the correct answer.
The reason I think the formula is related is that you could see move down as 1 and move right as 0.
In the example with 2x2 grid, either path will always require 2 steps down and 2 steps right.

[ntg]

I see what you mean, your reasoning sounds right. I made a quick program that actually counted the possible combinations and I made the assumption that you're correct. The results confirm that both a 3x3 and a 4x4 grid are according to the formula (20 and 70).

[TheBigB]

Solved it, I was missing accuracy (missed 20 on the tail of the answer).
Thanks for your help

[ntg]

So the answer was the correct one?

[TheBigB]

It was 137846528820

[ntg]

I'd never expect Calc to give out a rounding error. How'd you find out about the error?

[TheBigB]

I asked for a hint on the Project Euler forum.
They said my accuracy was off and suggested something like Google calc. Used Wolfram to calculate the exact answer.
Weird thing is that my TI-84 plus gives the same rounding error.
I'll have to check if I have some accuracy setting I can modify...