Collatz Conjecture: An Odd Number Of Steps

Computer Science Level 5

The Collatz Conjecture is a famous problem in number theory. It corresponds to the following function:

$f(n) = \begin{cases} \frac{n}{2} & \text{ if } n \equiv 0 \pmod{2} \\ 3n+1 & \text{ if } n \equiv 1 \pmod{2} \\ \end{cases}$

The conjecture states that for every $n>1$ there exists a $k$ such that $f^k(n)=1$ . In other words, given an $n$ to start with, after iterating this function over and over again we will eventually get $1$ , no matter the starting number.

How many $1<n<10^7$ are there such that $k$ is odd?

Note: We are looking for $k$ to be minimal. There are technically infinitely many $k$ because $f(1)=4$ , $f(4)=2$ and $f(2)=1$ .

Clarification : $f^k(n) = \underbrace{ f(f(f(\ldots (f(x))\ldots)}_{k \text{ number of times}}$ .

The answer is 5006434.

2 solutions

Daniel Branscombe
Aug 19, 2015

memorization is the key here, since in order to calculate the length for a given n you have to calculate the lengths for several other numbers along the way it is best to remember all of those intermediary lengths. This can be handled very easily in Mathematica

f[n_] := f[n] = If[n == 1, 0, If[Mod[n, 2] == 0, 1 + f[n/2], 1 + f[3 n + 1]]];

by defining a function f[x_]:=f[x]=....

this tells Mathematica to store in memory the value calculated anytime the function is calculated. Thus when revisiting an already calculated number it simply gets the value from memory.

As an explicit example, when calculating f[5] we get

f[5]=1+f[16]

f[16]=1+f[8]

f[8]=1+f[4]

f[4]=1+f[2]

f[2]=1+f[1]

f[1]=0

after calculating f[5], we now have in memory the values for f[16],f[8],f[4],f[2],f[1] and so if we were to calculate f[8] it would simply grab it from memory.

Very intuitive, I really admire your approach.

Garrett Clarke - 5 years, 9 months ago

Ah! Good use of dynamic programming! Upvoted! :)

Just for the sake of variety, let me add my brute-force and bashy C++ solution here:

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    long long collatz(long long),n,test,k,count=0;
    for(n=2;n<pow(10,7);n++)
        {
            k=1;
            test=n;
            while(collatz(test)!=1)
                {
                    test=collatz(test);
                    k++;
                }
            if(k%2==1)
                count++;
        }
    cout<<count;
    return 0;
}
long long collatz(long long x)
    {
        return (x%2==0) ? x/2 : 3*x+1;
    }

Runs for about 26 seconds. Here 's the full code in Ideone which cannot be executed in one run, so I run it twice by modifying the for loop in the code (one time for $2\leq n\lt \frac{10^7}{2}$ and the second time for $\frac{10^7}{2}\leq n\lt 10^7$ ).

Output:

1st run (13 secs) : 2497047
2nd run (13 secs) : 2509387

Hence, our answer is the sum $2497047+2509387=5006434$ .

Seeing your solution, I think I'll try to improve my original code later to reduce runtime and do the work in a single run.

Prasun Biswas - 5 years, 9 months ago

For some weird reasons, my python code slows down exponentially when I use memorization.

Arulx Z - 5 years, 9 months ago

While I can't see your code, I'm guessing that when your code is finished it has saved every variable from $1$ to $10^7$ exclusive, but note that it's not exactly necessary to have every variable on hand at all times. Save a few key ones and as you work your way up, find a way to intelligently save and delete the variables you need and don't need.

Garrett Clarke - 5 years, 9 months ago

Yes. You're right. I am using external library for memorization. I'll try to improve that. I'll post my code later (I'm in my school right now).

Arulx Z - 5 years, 9 months ago

@Arulx Z – Haha I think it's so funny that you're in school right now and I'm just about to go to bed!

Garrett Clarke - 5 years, 9 months ago

Abdelhamid Saadi
Aug 25, 2015

The same approche as Daniel Branscombe , in python 3.4

fn = {1: False}

def f(n):
    if not n in fn.keys():
        fn[n] =  not( f(n//2) if n%2 == 0 else f(3*n + 1))
    return fn[n]

def solve(m):
    "Collatz Conjecture: An Odd Number Of Steps"
    nbodds = 0
    for n in range(2,m):
        if f(n) :
            nbodds += 1 
    return nbodds

print(solve(10**7))

Collatz Conjecture: An Odd Number Of Steps

The answer is 5006434.

2 solutions

0 pending reports