2
$\begingroup$

Given $0\le x_0<1$, let $$x_n=\begin{cases} 2x_{n-1}, & \text{if $2x_{n-1}<1$}\\ 2x_{n-1}-1, & \text{if $2x_{n-1}\ge 1$} \end{cases}$$ for all integers $n>0$. For how many $x_0$ is it true that $x_0=x_5$?

The answer is supposedly 31.

Does anyone have any suggestions for how I might explore this solution using Mathematica?

Update #1: I want to put a number that is less than 1/2 in binary form. So I tried:

x0 = BaseForm[1./3, 2]

Which gave:

$$0.010101010101010101011\ _2$$

Now I want to show what happens when I multiply by 2. I tried:

x1 = 2 x0; BaseForm[x1, 2]

But I got:

$$10_2\ 0.010101010101010101011\ _2$$

But what I really wanted it to show is that it moved the decimal point 1 place to the right, that is:

$$0.10101010101010101011\ _2$$

Then I am going to want to show that the same thing happens when I start with a number larger than 1/2 and multiply it by 2 and subtract 1.

Improve this question
$\endgroup$
2
  • $\begingroup$ What is the domain for $x_0$? (in terms of, rationals or reals?) $\endgroup$ Commented Dec 5, 2015 at 19:28
  • $\begingroup$ @Kagaratsch Any real number. $\endgroup$ Commented Dec 5, 2015 at 19:39

3 Answers 3

Reset to default
5
$\begingroup$

I would do:

f[n_] := Nest[Piecewise[{{2 #, 2 # < 1}, {2 # - 1, 2 # >= 1}}] &, n, 5]; Solve[{0<=n<1,f[n]==n},n][[All,1,-1]] (* {0, 1/31, 2/31, 3/31, 4/31, 5/31, 6/31, 7/31, 8/31, 9/31, 10/31, 11/31, 12/31, 13/31, 14/31, 15/31, 16/31, 17/31, 18/31, 19/31, 20/31, 21/31, 22/31, 23/31, 24/31, 25/31, 26/31, 27/31, 28/31, 29/31, 30/31} *)

We get 31 solutions.

You cannot multiply a BaseForm with other numbers:

FullForm[2 BaseForm[1./3, 10]] (* Times[2, BaseForm[0.3333333333333333`, 2] *)

The head BaseForm does not get ignored.

You would need to do:

x0 = 1./3; BaseForm[x0, 2]

which gives $0.010101010101010101011_2$, and

x1 = 2 x0; BaseForm[x1, 2]

which gives $0.101010101010101011_2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice explanation. Thanks. $\endgroup$ Commented Dec 5, 2015 at 23:30
3
$\begingroup$

Here is how I do it

myTup = Tuples[{1, 2}, 5]; f[1,y_] := 2 y; f[2,y_] := 2 y - 1; Do[ h = x0; Do[h = f[myTup[[j, i]],h];, {i, 1, 5}]; x5[j] = h; , {j, 1, myTup // Length}] myRes = Table[ x0 /. Solve[x0 == x5[j], x0][[1]], {j, 1, myTup // Length}]

{0, 1/31, 2/31, 3/31, 4/31, 5/31, 6/31, 7/31, 8/31, 9/31, 10/31, \ 11/31, 12/31, 13/31, 14/31, 15/31, 16/31, 17/31, 18/31, 19/31, 20/31, \ 21/31, 22/31, 23/31, 24/31, 25/31, 26/31, 27/31, 28/31, 29/31, 30/31, 1}

Which are 32 results. But $x_0<1$ so the last entry is to be removed. Properly 31, as predicted. Conceptually, since we are testing all possible paths the evolution may take and are then solving a linear equation in each case, we are guaranteed to get only one solution from each path and therefore find all possible solutions.

We can also explicitly test that the result is indeed correct (even though it is clear that it must be)

fun[x_] := Block[{h}, h = x; Do[h = If[2 h < 1, 2 h, 2 h - 1];, {i, 1, 5}]; h ]; Table[fun[myRes[[j]]], {j, 1, Length@myRes - 1}]

{0, 1/31, 2/31, 3/31, 4/31, 5/31, 6/31, 7/31, 8/31, 9/31, 10/31, \ 11/31, 12/31, 13/31, 14/31, 15/31, 16/31, 17/31, 18/31, 19/31, 20/31, \ 21/31, 22/31, 23/31, 24/31, 25/31, 26/31, 27/31, 28/31, 29/31, 30/31}

Improve this answer
$\endgroup$
4
  • $\begingroup$ I was able to figure out the Tuples command. Very cool. But I had trouble with the Subscript[f,1][y_]:2y command. I entered it incorrectly as Subscript[f, 1] := 2 y and it would not work properly. I tried the usual ?f and I tried ?$f_1$ to find and possibly clear it to start over, but I could not find it so I had to quit the kernel. Advice on how to find and clear the mistake? $\endgroup$ Commented Dec 5, 2015 at 22:07
  • $\begingroup$ @David You would need to do ClearAll[Subscipt]. $\endgroup$ Commented Dec 5, 2015 at 23:01
  • $\begingroup$ @Kagaratsch OK, but how can I view the global variables? I am used to doing things like ?f. What would I type to see the definition of Subscript[f, 1][y_] := 2 y;? Also, I've tried things like x5[1] and got 32 x0. Again, how would you use ? to view these in the Global workspace? $\endgroup$ Commented Dec 6, 2015 at 6:03
  • $\begingroup$ @David the ? functionality indeed seems to misbehave when applied to quantities with subscripts. This never occurred to me, since I usually remember the functions I define and never use ?. Anyway, I have rewritten the code above so that it avoids use of subscript and all quantities behave properly under ? now. $\endgroup$ Commented Dec 6, 2015 at 7:57
1
$\begingroup$ 
f[x_] := 2 x - 1 + Boole[x < 1/2] a[x_, n_] := Nest[f, x, n] x /. {ToRules@Reduce[a[x, 5] == x, x]}

yields:

{0, 1/31, 2/31, 3/31, 4/31, 5/31, 6/31, 7/31, 8/31, 9/31, 10/31, \ 11/31, 12/31, 13/31, 14/31, 15/31, 16/31, 17/31, 18/31, 19/31, 20/31, \ 21/31, 22/31, 23/31, 24/31, 25/31, 26/31, 27/31, 28/31, 29/31, 30/31, 1}

The 1 cannot be omitted if desired.

Just for fun:

Note that the constraint $0\le x<1$ was not necessary as outside the unit interval the function balloons and for visualization:

Show[Plot[{Nest[f, x, 5], x}, {x, 0, 1}, Exclusions -> Range[1/32, 1, 1/32], Frame -> True], Graphics[{Red, PointSize[0.01], Point[Table[{j, j}, {j, Range[0, 30/31, 1/31]}]]}]]

enter image description here

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.