Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Math Puzzles > Fractal Function > Fractal Function

Fractal Function

Let F(x) be a non-decreasing function for all x in [0 1], such that

2F(x/3)=F(x) and F(x)+F(1-x)=1

1. Find F(173/1993) and F(1/13).

2. If possible give a general algorithm to find F(x) for any x.

Other questions:

3. Is F(x) uniquely determined(in [0,1])?

4. Is F(x) continuous(in [0,1])?

Source: unknown

Solution

1. F(173/1993) = 3/16, and F(1/13) = 1/7.

2. Here's the algorithm to find F(x) given x:

1. Express x in base 3.
2. Searching from the left, if any trigit is 1, increase it to 2, and then truncate the base-3 representation after that trigit.
    (The result after step 2 is a base-3 number between 0 and 1, inclusive, containing only 0's and 2's.)
3. Replace all the "2" trigits with "1".
4. Re-evaluate the number as a base 2 number.  This is F(x).

3 and 4. Yes.  Starting with the interval [0,1], and repeatedly dividing it into thirds, we get a dense set of x-values (the endpoints of the successively smaller intervals) for which F(x) is uniquely determined.  Since F is nondecreasing, the values of F between those endpoints must be between the values of F at the endpoints.  So F is continuous.

Here's a graph of F:

More about this puzzle

Proof that F(0)=0: From the definition of F, it follows that if F(x)=y, then F(x/3)=y/2, and F(1/2)=1/2,
so for any positive integer, k, F(3-k/2)=2-k/2.  Suppose F(0)=ε, where ε>0.  Then an integer, k, exists such that 2-k/2>ε, and so F(3-k/2)<F(0), a contradiction.

Corollary: F(1)=1. 

Repeatedly dividing the interval into thirds: From facts presented thus far, it follows that F(1/3)=F(2/3)=1/2, dividing the unit interval into thirds.  F is constant on the middle third, so there's no need to divide it further, but each of the two other thirds can be divided further into thirds, giving us

F(1/9)=F(2/9)=1/4, and
F(7/9)=F(8/9)=3/4

So you can see that the middle third is a "plateau" after each successive division of an interval.  That is, F(x) is constant for all values of x that fall into a middle interval.

Expressing x in base 3 and F(x) in base 2, we see:

F(0.13)=F(0.23)=0.12,
F(0.013)=F(0.023)=0.012,
F(0.213)=F(0.223)=0.112,
F(0.0013)=F(0.0023)=0.0012,
F(0.0213)=F(0.0223)=0.0112,
F(0.2013)=F(0.2023)=0.1012,
F(0.2213)=F(0.2223)=0.1112,

Each digit of the base-3 representation of a number, x, identifies which third of each of the successive divisions the number falls into.  If the n'th digit of x (in base 3) is 1, then x falls in the middle third of the unit interval after it has been divided n times.  For example, if x=0.202211202...3, the fifth digit is 1, and so x falls in the middle third of an interval that is the fifth successive division of the unit interval into thirds.  All the numbers between 0.202213 and 0.202223 fall in this interval, so F(x)=F(0.202213)=F(0.202223).  From this, it is clear that upon encountering the first 1 in the base-3 representation of x, the number can be truncated after that trigit, and then the trigit can be changed to 2 without affecting the value of F(x).  Then, the value of F(x) is obtained by changing each "2" in x's base-3 representation to "1", and re-interpreting the number as a binary number.

173/1993 is between 0.00213 and 0.00223, so F(173/1993) = F(0.00223) = 0.00112 = 3/16

Repeating Fractions in Base 3: 1/13 is a bit trickier, because in base 3 it's a repeating "decimal" (using the term loosely) that has no 1's.  To explore repeating decimals in base 3, I would like to start with a review of an infinite geometric series.  Why?  If you think about it, you will realize that a repeating decimal in any base is a geometric series.  Perhaps you recall that

x-1 + x-2 + x-3 + ... = 1/(x-1)

If not, then refresh your memory this way:

Let S = x-1 + x-2 + x-3 + ...
Then xS = 1 + x-1 + x-2 + ...
And xS-S = 1, and then by dividing both sides by x-1,
we see that S = 1/(x-1)

Now, if x is a power of 3 then the sum, S, which equals 1/(x-1), can be expressed very neatly as a repeating fraction.  For example, when x=3, 1/(3-1) = 1/2 = 0.111...3.  When x=9, 1/(9-1) = 1/8 =  0.010101...3.  And when x=27, 1/(27-1) = 1/26 = 0.001001001...3

What does this have to do with 1/13?  Well, 1/13 = 2/26 = 2/(27-1) = 0.002002002...3.
So F(1/13) = 0.001001001...2 = 8-1 + 8-2 + 8-3 + ... = 1/(8-1) = 1/7.

More questions to think about

Can F be extended in a sensible way so that it is defined over the domain of all nonnegative real numbers?

Can F be extended to negative reals?  Complex numbers?

What features or characteristics of F do you try to preserve when extending the function?

What are some of the problems you encounter when you try to extend F?  How do you overcome these problems?

Internet references

Wikipedia: Cantor function 

Cut-the-knot: Cantor Set and Function -- A continuous function may grow considerably virtually without changing.

Related pages in this website

(none)

 


The webmaster and author of this Math Help site is Graeme McRae.