MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a function that permutes a string of symbols according to a rule that we define recursively

$f(s_1s_2s_3s_4s_5...)$ = $f(s_1s_3s_5...)+f(s_2s_4s_6...)$ with $f(s_1)=s_1$ (plus denotes string concatenation)

How many times must the function be applied on a string with length of $n$, to get back to the original string?

I have made some mechanical calculations and the numbers are very peculiar (from string length of 1 on : 1, 1, 2, 2, 3, 4, 2, 2, 8, 9, 12, 28, 8, 42, ...) and I would like to know how to solve this problem in general.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.