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.

$\endgroup$
  • $\begingroup$ What is the domain for $x_0$? (in terms of, rationals or reals?) $\endgroup$ – Kagaratsch Dec 5 '15 at 19:28
  • $\begingroup$ @Kagaratsch Any real number. $\endgroup$ – David Dec 5 '15 at 19:39
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$.

$\endgroup$
  • $\begingroup$ Nice explanation. Thanks. $\endgroup$ – David Dec 5 '15 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}

$\endgroup$
  • $\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$ – David Dec 5 '15 at 22:07
  • $\begingroup$ @David You would need to do ClearAll[Subscipt]. $\endgroup$ – JungHwan Min Dec 5 '15 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$ – David Dec 6 '15 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$ – Kagaratsch Dec 6 '15 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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.