I am doing some research into the movement of robots executing a given algorithm, and I came up with a recursive formula to describe the coefficient of the movement for each step. Is it even possible to convert the recursive formula to a closed-form version? As far as I've tried, I haven't been able to find a solution, though I'm not a mathematician.

enter image description here

where 0 < M(0) $\le$ 1

  • $\begingroup$ You to know the starting value. $\endgroup$ – hamam_Abdallah Jul 12 '18 at 20:34
  • $\begingroup$ You can remove the third condition, I believe. If $\exists n$ such that $M(n)=0.5$, then the sequence becomes $0.5,1,0,0,0,...$. $\endgroup$ – MalayTheDynamo Jul 12 '18 at 20:35
  • $\begingroup$ Are you looking for a formula that will be valid for $0<=M(0)=x<=1?$ $\endgroup$ – saulspatz Jul 12 '18 at 20:43
  • $\begingroup$ @saulspatz yes, I'm wondering if its possible. $\endgroup$ – RoryHector Jul 12 '18 at 20:48
  • $\begingroup$ @saulspatz Use $\le$ for $\le$. $\endgroup$ – Shaun Jul 12 '18 at 21:32

Define the function $f: \Bbb R \to [0, 1]$ as the distance of $x$ to the nearest integer, multiplied with $2$: $$ f(x) = 2 \min \{ x - \lfloor x \rfloor, \lfloor x +1\rfloor - x \} \, . $$ The function is periodic with period $1$, and on the interval $[0, 1]$ it looks like this: enter image description here

This are the graphs of the iterates $f(f(x))$ and $f(f(f(x)))$:

enter image description here enter image description here

One “sees” that $f(f(x)) = f(2x)$, $f(f(f(x))) = f(4x)$, and generally for the $n$-th iterate: $$ f^{(n)} (x) = f(2^{n-1}x) $$

Therefore $$ M(n) = f^{(n)}(M(0)) = f(2^{n-1}M(0)) \\ = 2 \min \{ 2^{n-1}M(0) - \lfloor 2^{n-1}M(0) \rfloor, \lfloor 2^{n-1}M(0) + 1\rfloor - 2^{n-1}M(0) \} $$ is the distance of $M(0)$ to the nearest integral multiple of $\frac{1}{2^{n-1}}$, multiplied with $2^n$.


I really doubt that this is possible. It starts to oscillate madly. I wrote a python script to test this.enter image description here

Here's the script if you want to test it yourself

import matplotlib.pyplot as plt

n = 20
def M(x):
    return 2*(1-x) if x > .5 else 2*x

xs = [.01*n for n in range(100)]
ys = map(M, xs)
for _ in range(n):
    ys = map(M, ys)
plt.plot(xs, list(ys))
  • $\begingroup$ It oscillates, but not madly :) With n = 6 and xs = [n/128 for n in range(128)] you'll get a better picture. $\endgroup$ – Martin R Jul 13 '18 at 5:32
  • $\begingroup$ What you see is a fundamental (triangle wave) modulated by an envelope which is also a (shifted) triangle wave. But in fact, the envelope is a sampling artifact, i.e. a form of aliasing. With a correct sampling frequency, you get a pure triangular wave (See Martin R.'s answer). $\endgroup$ – Yves Daoust Jul 13 '18 at 9:07
  • $\begingroup$ @MartinR Well, I'm surprised. I purposely didn't use a power of $1/2$ as the sampling interval, because I thought the function was likely to behave nicely there and badly elsewhere. I thought the experiment confirmed my mistaken intuition, and didn't look any deeper. $\endgroup$ – saulspatz Jul 13 '18 at 12:20

The transformation can be seen as a "folding". It linearly stretches $[0,\frac12]$ to $[0,1]$, then $[\frac12,1]$ to $[1,0]$. You can represent this effect by drawing a diagonal on a rectangular sheet and folding it along the horizontal median. You repeat this as many times as you want.

You can stretch vertically by a factor $2^n$ to restore the initial height.

enter image description here


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.