CODEWITHSUNDEEP
pythonpython-2.7recursion
Rohit Jose
Rohit Jose

Reputation: 188

Series Length Calculation

I want to calculate the number of terms in the series given by the below algorithm:

if n=1 STOP:    
    if n is odd then n=3n+1 
    else n=n/2

For example, if n is 22 the series would be as below and the length of the series would be 16:

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

I came up with the below recursive function in python:

class CycleSizeCalculator(object):
    '''
    Class to calculate the cycle count of a number. Contains the following
    members:
    counter - holds the cycle count
    number  - input number value
    calculate_cycle_size() - calculates the cycle count of the number given
    get_cycle_length()     - returns the cycle count
    '''
    def calculate_cycle_size(self,number):
        """
        Calculates the cycle count for a number passed
        """
        self.counter+=1# count increments for each recursion
        if number!=1:
            if number%2==0:
                self.calculate_cycle_size((number/2))
            else:
                self.calculate_cycle_size((3*number)+1)

    def __init__(self,number):
        '''
        variable initialization
        '''
        self.counter = 0
        self.number = number
        self.calculate_cycle_size(number)

    def get_cycle_length(self):
        """
        Returns the current counter value
        """
        return self.counter

if __name__=='__main__':
    c = CycleSizeCalculator(22);
    print c.get_cycle_length()

This works in most cases but fails with the message Maximum Recursion depth reached for some values of n. Is there an alternate approach to it?

Upvotes: 0

Views: 428

Answers (3)

bcorso
bcorso

Reputation: 47078

If you want to do it recursively, this works:

def get_count(n):
    return 1 if n == 1 else 1 + get_count(3*n+1 if n%2 else n/2)

And an iterative version:

def get_count(n):
    i = 1
    while n != 1:
        (n, i) = (3*n+1 if n%2 else n/2, i + 1)
    return i

Upvotes: 1

Sufian Latif
Sufian Latif

Reputation: 13356

This sequence can be arbitrarily large for some numbers. So a recursive approach may not be enough. You can simply try the iterative approach:

def calculate_cycle_size(self,number):
    self.counter = 1
    while number != 1:
        if number%2 == 0:
            number = number / 2
        else:
            number = 3 * number + 1
        self.counter += 1

Upvotes: 3

pjs
pjs

Reputation: 19855

That's the Collatz Conjecture, and last I heard it remains unproven that it converges to 1 for all positive integer starting points. Unless you can prove convergence, it's going to be hard to determine what the sequence length will be.

Upvotes: 5

Related Questions