Base 3
This should be easy, but let's see if it is.
Ok, let's see you count from 101 to 110.
Just ten numbers.... but do it in base 3.
Ok, let's see you count from 101 to 110.
Just ten numbers.... but do it in base 3.
Labels: lateral thinking
posted by Ragknot at
6:32 PM
9 Comments:
101...102...110 in base 3. Just two steps.
Or do you mean convert decimal 101 and decimal 110 to base 3 and then count? This would be 10202 to 11002, i.e. ten steps (or 101 in base 3).
Can't see anything tricky about this problem. Am I missing something?
Hi Ragknot. I should have seen this coming :)
As 101 to 110 is ten numbers, those numbers are unambiguously in base 10. In base 3, 101 is 10202. So the next 9 numbers are: 10210, 10211, 10212, 10220, 10221, 10222, 11000, 11001, 11002.
I'll concede that if you really had an ordered collection of items that were naturally tri-state, then it would be appropriate to encode the collective state in base 3 arithmetic.
Right, it is easy. I've always thought why would you want to use this. It seems kind of useless.
101 10202
102 10210
103 10211
104 10212
105 10220
106 10221
107 10222
108 11000
109 11001
110 11002
We have had so many problems using combinations, I want to demonstrate something I found useful. Like, what are the combinations of U R and D?
The symbols 0, 1 and 2 are just symbols that we assign a values to, and they are international.
But what if the symbols were U, R and D? Then we have an easy way to generate the combinations from 101 to 110 (base 10) or whatever range you desire.
101 RUDUD
102 RUDRU
103 RUDRR
104 RUDRD
105 RUDDU
106 RUDDR
107 RUDDD
108 RRUUU
109 RRUUR
110 RRUUD
Hi Rgaknot, I could understand assigning say 0 to U, 1 to R and 2 to D say. Then RUDUD = 10202 (base 3) = 299 (base 10). But can't see why you would want to do that. It just turns a string of letters into a number in a reversible manner. But I know you well enough to suspect that you might have a cunning plan ^^
To go into more detail using the chess board as an example.
I generated what I thought was a complete set of the 14 place URD combinations. From these set, any string with more that 7 Us, 7 Rs, or 7 Ds or tossed. Then I added the places of the strings, where U was worth 8, R's were worth 1 and D's were worth 9. This gives the square numbers along the path. Somewhere between the 7th and 14th place the added numbers would equal 64 if the path ended at square 64. Those that didn't were discarded. Finally the remainder was the 48,639 paths that were the solution set.
My error was that I did have the full set of combinations before I started discarding. If I had used the base 3 with 14 places, I would have had the full set to start from.
Hi Ragknot. I think you mentioned that 1,8,9 code before, but thanks for (re)posting it. That code was clever, I salute you. For the more general problem you'd have L = -1, R = 1, L' = 7, U = 8 and R' = 9.
Did you end up storing 3^14 strings and the filter out the illegal ones?
For the more general problem you'd need 5^64 strings of maxlength 64. That's about 3.5*10^34 Terabytes. So don't try that at home.
No, I did not generate all 3^14 strings to begin with. I thought that I had the possible combinations but I did not think about 3^14. I generate random combinations till I stopped finding more. and it was about 3 million. I suspect the problem was that a random number is not genually true, After 3 million it could find no more. I was testing and discarding them as I was computing them, and after an hour, there was no more to be found.
After you made made your solution, I began to look for at least one path that was true and that I did not have. After finding a few, I reasoned the total unique combinations was 4+ million, almost 5 million.
That's when I began to generate base 3 numbers. With the code I have for base numbers, I just subsituted URD in place of the 012, then I had the whole set, and quickly added them to my existing set and tested the new ones. After discarding ones that did not work, I checked the good ones. Of course, they totalled your solution.
I did offer myself one trophy for having all the paths to list.
I am sure no one else could do that.
Thanks for the summary. What a swizz the random number generator have such a small cycle. I can't find out how good the best one (there are 6 apparently) in Mathematica is, but assume that it's vastly larger than 3 million. I now understand (in principle) exactly what you did and why you had discrepancies at first. I expect that you're right about being the sole owner of such a list.
... and thanks for the run time info. I was curious about the run time. Tweak it for an 11*11 board and take a weekend break while it works it out. Once I knew what to do, I calculated the table in 10 minutes (I guess). Going to 9 or 10 would only take a couple of minutes (by hand), and a negligible time using the g(n,r) formuula.
Post a Comment
Links to this post:
Create a Link
<< Home