Author Topic: 3n + 1 Programming Challenge  (Read 2094 times)

TheQuirk

  • VIP
  • Member
  • ***
  • Posts: 2,154
  • Kudos: 315
3n + 1 Programming Challenge
« on: 7 December 2005, 21:25 »
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: [Select]

         / 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}.

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 <= N <= k if both j and k are given and are natural numbers?

Input values: j, k
Output values: Maximum length of cycle
« Last Edit: 7 December 2005, 21:46 by TheQuirk »

Pathos

  • Member
  • **
  • Posts: 518
  • Kudos: 416
Re: 3n + 1 Programming Challenge
« Reply #1 on: 8 December 2005, 09:23 »
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

  • VIP
  • Member
  • ***
  • Posts: 2,154
  • Kudos: 315
Re: 3n + 1 Programming Challenge
« Reply #2 on: 9 December 2005, 20:45 »
I don't think so.

Pathos

  • Member
  • **
  • Posts: 518
  • Kudos: 416
Re: 3n + 1 Programming Challenge
« Reply #3 on: 17 December 2005, 01:19 »
I'll do it now it javascript :)...

Pathos

  • Member
  • **
  • Posts: 518
  • Kudos: 416
Re: 3n + 1 Programming Challenge
« Reply #4 on: 17 December 2005, 02:15 »
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



   



   J:

   K:

   

   N: