Puzzle
1 minute read

Ponder This Challenge - November 2010 - In honor of Benoit Mandelbrot

Ponder This Challenge:

November's challenge is dedicated to IBM Fellow Benoît Mandelbrot, who died on October 14, 2010, at the age of 85.

Let's define a function f on five variables (i, j, k, l, and m) as follows:

If (i-m)*(j-m) is zero then
    f(i,j,k,l,m) ← ((abs(j-(1-k+l)*m)-m+1)* (abs(i-(k+l)*m)-m+1))
else
    f(i,j,k,l,m) ← f(i mod m,
                           j mod m,
                          int(((i^j)&((m*l)^i))/m)^l^k^int(i/m),
                          int(((i^j)&((m*k)^i))/m)^l,
                          m/2)

Where
x^y      means bitwise xor (exclusive or)
x&y     means bitwise and (conjunction)
abs    is the absolute value
mod   is the modulo function
int       means truncating downwards to an integer

What should be the input to the function f, and how do you need to interpret its output to associate it with Professor Mandelbrot?

Update: November 5th: We are *not* looking for his age.

Update: December 1st: m is a power of 2.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

  • Fixing m to be a power of 2; setting k and l to be zero; and looping i and j over the range [1,m], we get an integer f(i,j,k,l,m) for each pair (i,j).

    Drawing a point on the j-th row of the i-th line when f(i,j,0,0,m) is zero and leaving it blank when it is not yields the Hilbert space-filling curve, which is a fractal.We received two interesting answers. The first was from John Tromp, who sent us a magnificent C program that generates this curve and has its shape:

    The second was from Tim Tran, who switched the order, fixed i and j, and looped with k and l, producing a fractal-like construct:

Solvers

  • Mark Mixer (11/02/2010 08:32 PM EDT)
  • John Tromp (11/02/2010 11:50 PM EDT)
  • John T. Robinson (11/11/2010 03:16 PM EDT)
  • Sylvain Becker (11/11/2010 08:22 PM EDT)
  • Piet Orye (11/15/2010 10:34 AM EDT)
  • Tim Tran (12/05/2010 04:31 AM EDT)
  • Luke Pebody (12/06/2010 04:00 PM EDT)

Related posts