How to Multiply with the 3n + 1 series (Collatz Conjecture)

How to Multiply with the 3n + 1 series (Collatz Conjecture)

Time to read: 3 minutes

Tags: math

Table of Contents

Introduction

I stumbled across an interesting paper, which shows that you can multiply two numbers by using the Collatz conjecture (and assuming it to be true for the numbers you are dealing with).

This post contains my summary and understanding of how this method works.

Background

Collatz conjecture

Definition

The Collatz conjecture, also known as the 3n+13n + 1 problem, is a simple to describe, yet unsolved, problem in discrete mathematics. The conjecture states that if you start with a positive integer nn and apply the following rule to it:

  • If the number (nn) is even, divide it by two: n2\frac{n}{2}
  • If the number (nn) is odd, multiply it by 3 and add one: 3n+13n + 1

The number will eventually land in the cycle 42144 \rightarrow 2 \rightarrow 1 \rightarrow 4. The conjecture states: this the only cycle. There is no proof to confirm this, however, we have tested up to a very large number and the conjecture seems to hold. Thus, for all practical purposes: the conjecture is true.

The rule can be mathematically written as:

f(n)={n2if n0 (mod 2)3n+1otherwise f(n) = \begin{cases} \frac{n}{2} &\text{if } n \equiv 0 \text{ (mod 2)} \\ 3n + 1 &\text{otherwise} \end{cases}

Examples

1010

  • 55
  • 1616
  • 88
  • 44
  • 22
  • 11 (cycle starts)

1818

  • 99
  • 2828
  • 1414
  • 77
  • 2222
  • 1111
  • 3434
  • 1717
  • 5252
  • 2626
  • 1313
  • 4040
  • 2020
  • 1010 (use above)

Method

Definitions

Collatz Function

Define the Collatz function, FF, as the Collatz conjecture with path of dividing by 2 compressed into one step, that is:

Given xx, a positive odd integer:

F(x)=3x+12ctz(3x+1) F(x) = \frac{3x + 1}{2^{\text{ctz}(3x + 1)}}
  • ctz(x)\text{ctz}(x) gives the number of factors of 2 in a number, i.e. count the trailing zeros of a number in binary

Collatz sequence and kk

  • The Collatz sequence, is the sequence of numbers produced by the Collatz function until it reaches the number 11 for the first time
  • Define kk as the number of steps until the Collatz series lands on 11

In other words, the Collatz sequence can be shown mathematically like so:

x,F1(x),F2(x),...,Fk1(x),1 x, F_1(x), F_2(x), ..., F_{k-1}(x), 1

How to Divide: ma\frac{m}{a}

Let's multiply the Collatz function series by aa, we get:

ax,aF1(x),aF2(x),...,aFk1(x),a ax, aF_1(x), aF_2(x), ..., aF_{k-1}(x), a

Let m=axm = ax, we get

aF(x)=a3x+12ctz(a(3x+1))=3ax+a2ctz(3ax+a)=3m+a2ctz(3m+a)=G(m) \begin{aligned} a F(x) & = a \frac{3x + 1}{2^{\text{ctz}{(a(3x + 1))}}} \\ & = \frac{3ax + a}{2^{\text{ctz}{(3ax + a)}}} \\ & = \frac{3m + a}{2^{\text{ctz}{(3m + a)}}} \\ & = G(m) \end{aligned}

NOTES: ctz(3m+a)=ctz(3m+1)ctz(3m+a) = ctz(3m+1) when aa is odd

Assuming ama \mid m (aa divides mm), we can:

  1. Start with mm
  2. Use G(m)G(m) until we get to aa
    • Record what we've done to get there
    • i.e. save the result of ctz(3x+1)\text{ctz}(3x + 1) along the way and kk (the number of steps)
  3. Backtrack using the same form of operations (in reverse) with F(x)F(x) whilst starting at 11

i.e. we have a division algorithm using the Collatz conjecture

How to Multiply: axax

Now, how do we multiply? Simple:

  • Start with xx and use F(x)F(x) until we get to 11
    • Record what we've done (save the kk steps)
  • Now, start with aa and backtrack with G(x)G(x) (with the saved kk steps), which will get us to axax