Miscellaneous > Programming & Networking

3n + 1 Programming Challenge

(1/1)

TheQuirk:
There's a simple, but fairly interesting sequence which I'd like to discuss.

Here's the algorithm for finding the terms:

1) Begin with a natural number n.
2) If n is even, divide n by 2.
   If n is odd, multiply n by 3 and add 1.
3) If n does NOT equal 1, then return to step #1.

The sequence can be written down as a recursive formula:

--- Code: ---
         / n_(k-1) / 2    ,n_(k-1) an even number \
{n_k} = <                                          >
         \ 3*n_(k-1) + 1  ,n_(k-1) an odd number  /

If n_j = 1, then the domain is {1, 2, ... , j}.

--- End code ---

For example, if n equals 22, then the the formula defines the following sequence:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It's assumed that the sequence is limited for all values of n. This has not been proven, but has been tested to work with n <

1,000,000.

And now for the challenge!

We'll define "the length of cycle n" as the amount of terms the aforementioned sequence contains if n_1 = n. What is the

longest length of cycle that can be attained for j

Pathos:
Well iterating between j and k and finding the length of the cycle for number between is easy enough...but is there an easier way...




probably not otherwise the would have proved it by now....

TheQuirk:
I don't think so.

Pathos:
I'll do it now it javascript :)...

Pathos:
Meh, what a hack. Took far longer than it should but I'm using beaver on DSL on a laptop and I've forgotten the Dom and debugging javascript is a bitcch....



   3n+1 Solution



var count = 0;
   
function sp(n)
{
   document.getElementById("n").innerHTML+=""+n+", ";
   count += 1;
   if (n==1) return;
   if ((n%2) == 0)
      sp(n/2);
   else
      sp(3*n+1);
   return;
}   


function Solve(n)
{
   count += 1;
   if (n==1) return;
   if ((n%2) == 0)
      Solve(n/2);
   else
      Solve(3*n+1);
   return;
}   


function FindAnswer(j, k)
{
   var max = 0;
   var i = j;
   var N = j;
   while ( i max)
         { max = count; N = i; }
      i++;
   }
   count = 0;
   sp(N);
}


   



   J:

   K:

   

   N:

Navigation

[0] Message Index