nwerneck
LTI
São Paulo, SP, Brazil
Registered: Jan 2008
Posts: 7 
Nice hint, thanks!
I also saw something like this too. I'm not quite sure, but I think you can just make:
"F**" > "F" (push "Foo")
(where the * means any possible character, not two of the same)
Our simplifications (or perhaps "complifications"?) stack a lot of "oFo"s or "Foo"s, and that explains why the strings grow like "...ooFooFooFooFooFooF...". But as you said, this takes three steps. We are defining a sort of "internal state" here, and I want to predict this too.
The problem is to find a formula that says the next string size and what will be the next pattern each time we "come full circle", finishing to process the string and starting over again. In other words, given the start of the string (each "necklace" pattern) and the size of the "Foo" sequence, tell the next. I couldn't find it...
I believe it's some kind of mapping like: for each possible start (the 4 possible patterns), and depending on the value of the modulo of the number of "Foo"s for some base, calculate the number of "Foo"s somehow, and select the next pattern according to some rule.
The modulo thing is because I can't see a simple rule that maps the current pattern to the next one. If we label them 4, 3, 2 and 1, the sequence of patterns is:
1,4,3,3,2,1,4,2,4,3,2,1,4,2,4,2,4,3...
What I want to find out is a relation between this pattern change and the size of the "Foo" part. The hard part is not just understanding why it grows like this, but finding out exactly the size and pattern of the next necklace!... The point of the three steps that we stop at each iteration is also relevant.
PS: I like the "F**" simplification better (instead of the G one) because some times the necklace reaches a pattern (that I labeled 1) composed only by "Foo"s, with no "G"s, and starting at the "F". I tried to predict when those happen, but I still could not. First few cases are 1, 6 and 12, with sizes 3, 21 and 237...
And notice we always could "compute" whatever I want, but not however. The problem is the type of computation. I did compute the first 18 necklaces, but applying the rules directly. I want to find out whether there is a closedform expression. The simple and classical pseudorandom generator I mentioned can be "computed", but not "predicted easily with a closed expression". Its recursion formula, tough, is quite simple. I couldn't even find a recursion formula to my problem yet...
__________________
Nicolau Werneck <nwerneck@gmail.com>
http://www.lti.pcs.usp.br/~nwerneck
9F99 25AB E47E 8724 2F71 EA40 DC23 42CE 6B76 B07F
"The purpose of computing is insight, not numbers."  R. W. Hamming
Last edited by nwerneck on 01292008 at 04:11 AM
Report this post to a moderator  IP: Logged
