Miscellaneous => Programming & Networking => Topic started by: TheQuirk on 7 December 2005, 21:25
Title: 3n + 1 Programming Challenge
Post by: TheQuirk 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:
/ 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
Title: Re: 3n + 1 Programming Challenge
Post by: Pathos 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....
Title: Re: 3n + 1 Programming Challenge
Post by: TheQuirk on 9 December 2005, 20:45
I don't think so.
Title: Re: 3n + 1 Programming Challenge
Post by: Pathos on 17 December 2005, 01:19
I'll do it now it javascript :)...
Title: Re: 3n + 1 Programming Challenge
Post by: Pathos 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....