Tags

, ,

This is a companion post to the Math Games #1 post on my main blog.

Here I present some code (Python, of course) for exploring the first two games, multiplicative persistence and the Collatz conjecture.

I’ll assume you’ve read the main post and jump right in.

§

For the first routine, calculating the multiplicative persistence, we have the following design parameters:

  1. Take a number as input.
  2. Multiply all its digits together.
  3. If the result is a single digit, we’re done.
  4. Otherwise, repeat these steps with the result.
  5. Return the number of iterations.

There are whistles and bells we can add, but these are the requirements that must be met.

Here’s an implementation (complete with some whistles and bells):

def multi_persist (n, step=0, verbose=False):
    s = str(n)
    if verbose:
        print('%2d: %s' % (step,s))
    if len(s) == 1:
        return step
    result = 1
    for d in list(s):
        result *= int(d)
    return multi_persist(result, step+1, verbose=verbose)

The algorithm takes a number, n (requirement #1), which it immediately converts to a string, s (line 2). It also takes a step number and a “verbose” flag, both of which have default values.

We convert n to a string because we want to process its digits individually. The variable itself is a binary value. (There is an algorithm, of course, for generating the digits of a value (in any given base). That algorithm is exactly what the str() function uses, so we’ll just use that.)

Next (lines 3 & 4), we print the input (and step) number, if we’re being verbose. Otherwise we keep our mouth shut.

The first processing step (lines 5 & 6) checks to see if the number already has just one digit. If it does (per requirement #3), we’re done and we return the step number (requirement #5).

If the number is longer, we set result to 1 (line 7) and, for each digit, we multiply it to result (lines 8 & 9). After the loop, result is the product of the digits (requirement #2).

Finally (line 10), we recurse, passing result and adding one to the step number (requirement #4).

That’s all there is to it. Calling is as simple as:

steps = multi_persist(277777788888899, verbose=True)

Which generates:

 0: 277777788888899
 1: 4996238671872
 2: 438939648
 3: 4478976
 4: 338688
 5: 27648
 6: 2688
 7: 768
 8: 336
 9: 54
10: 20
11: 0

As the main post discusses, eleven steps is thought to be the maximum possible, and 277777788888899 is the lowest value with eleven steps.

§

The other routine, the Collatz conjecture, naturally has its own set of requirements:

  1. Take a number as input.
  2. If the number is even, divide it by two.
  3. Otherwise, multiply it by three and add one.
  4. If the result is one, we’re done.
  5. Otherwise keep going with the new value.
  6. When we’re done, return the entire sequence.

Here’s an implementation (we could have done this one recursively, too, but it’s simpler as an iteration):

def collatz_path (n):
    steps = [n]
    while 1 < n:
        n = collatz(n)
        steps.append(n)
    return steps

This algorithm is pretty simple (but mighty)!

Per requirement #1, it takes a number. Per requirement #6, it returns a list (line 7), the sequence of numbers it took to reach one.

The first thing (line 2) is to create the list, steps, that we’ll eventually return. We initialize the list with the input number, n, to make it the first number in the list.

Then (line 3) we enter a while-loop that continues so long as n stays above 1.

In line 4, we get the next value in the sequence from the collatz() function and assign it to n. We’ll look at that function in a moment.

In line 5, we add the new value to the list, and then (requirement #5) the loop repeats (assuming n is still above 1).

Once we hit 1, we’re done (requirement #4), and the Collatz conjecture says we will hit 1. At that point, we drop out of the loop and return the list (line 6).

This leaves requirements #2 and #3, which are the rules of the Collatz sequence.

Calculating the next number in the sequence is a useful stand-alone function, so I implemented it separately. In Python, it can be implemented as a lambda function:

collatz = lambda n: ((n*3)+1) if (n % 2) else (n//2)

Which just says that if n is even (division by 2 has no remainder) then return n//2, otherwise return (n*3)+1.

§

Given these building pieces, you can explore the behavior behind multiplicative persistence and the Collatz conjecture.

I used the Collatz stuff to explore the binary tree that forms as you add sequences.

All sequences end at 1, so that’s the tree’s root. The two rules mean there’s potentially two paths to a number, and the deterministic Collatz function means there’s only one path from a number. (Hence the binary tree.)

The tree turns out to be extremely sparse, because the rules don’t always generate integers when played “in reverse” (which you do when building the tree from the root).

Fun with Python! It makes all this so easy!