Posts

Finding patterns in the Collatz 3n + 1 problem

avatar of @chasmic-cosm
25
@chasmic-cosm
·
·
0 views
·
1 min read

Consider a number n.

If n is even, divide it by two.

If n is odd, multiply it by 3 and add one.

The Collatz conjecture states that by continuing this process: starting with any n, applying this algorithm eventually will converge to 1. This is unproven but so far seems to be true.

The following code finds the number less than a given n which produces the longest chain before converging to one:

function [longest] = collatz (n) 
% find the number of steps taken for numbers up to n to converge to one  
% using the 3n + 1 algorithm 
% return the number whose chain is longest 
 
distances = zeros(1,n); 
 
for i = 2:n 
   
  a = i; 
  x = 0; 
  dist = 0; 
  while( a ~= 1) 
    if(a <= columns(distances)) 
      if(distances(1,a) ~= 0) 
        dist += distances(1,a); 
        break; 
      end 
    end 
    if(mod(a,2) == 0) 
      a = a / 2; 
    else 
      a = (3 * a) + 1; 
    end 
     
    dist++; 
  end 
  distances(1,i) = dist; 
end 
 
longest = 1; 
 
for i = 1:n 
  if(distances(1,i) > distances(longest)) 
    longest = i; 
  end 
end 
 
end 

Photo by Markus Spiske from Pexels

Posted Using LeoFinance Beta