Finding longest number chain with hailstone algorithm

Question

Yoink 0 Newbie Poster

12 Years Ago

I have to write a program that will print the chain of a number using a hailstone function, as well as with a range of numbers. That part of my program works perfectly but I cant figure out how to write a function that will find and hold the number that gives the longest chain of numbers, along with the length of that chain.

Here is my 95% working program, the only thing that wont work is the length of the longest chain section at the bottom of my main.

MIN = 1
MAX = 10000
MAXNUM = 0
MAXLEN = 0

# isOdd() checks to see if a number is odd
# Inputs: num
# Output: True if odd, False if even
def isOdd(num):
    if num % 2 != 0:
        return True
    if num % 2 == 0:
        return False
    
# hailstone(0 runs the hailstone algoritm and
# runs while the number is not equal to 1
# multiplying the number by 3 and adding 1 if odd
# and dividing number by 2 if even till end is reached
# Inputs: num
# Outputs: num "->"
#          count
def hailstone(num):
    length = 1
    print num, "->",
    while num != 1:
    
        if isOdd(num) == True:
            length = length + 1
            num = (num * 3) + 1  
        else:
            length = length + 1
            num = num / 2
        if num != 1:
            print num, "->",
        else:
            print num,
            

        
    print ("; length = %d") % length

def maxLength(num):
    length = 1

    while num != 1:
    
        if isOdd(num) == True:
            length = length + 1
            num = (num * 3) + 1  
        else:
            length = length + 1
            
            num = num / 2
        
        return num



def printGreeting():
    print "This program finds hailstone sequences of numbers you choose.\
The next number in the hailstone sequence is found by dividing\
the number in half if it's even and multiplying by 3 and adding\
one if it is odd."
    
def enterNumbers():
    firstNum = getValidInt("Enter the starting Number between ", MIN, MAX)
    secondNum = getValidInt("Enter the ending number between ", firstNum + 1, MAX)

    return firstNum, secondNum


# used from notes
def getValidInt(question, min, max):
    value = max + 1
    prompt = question + " (" + str(min) + "-" + str(max) + "): "
    while value == "" or value < MIN or value > MAX:
        value = raw_input(prompt)
        if len(value) != 0:
            value = int(value)

    return value
    
def printMenu():
    print "\n\tI - View sequence for an Individual value\n"
    print "\n\tR - View sequence for a Range of values\n"
    print "\n\tL - Find the Longest chain\n"
    print "\n\tQ - Quit\n\n"

def main():
    MAXNUM = 0
    MAXLEN = 0
    choice = ''
    printGreeting()

    while choice != 'Q' and choice != 'q':
        printMenu()
        
        choice = raw_input ("Enter your choice: ")
        
        if choice == "i" or choice == "I":
            num = input("Enter in a number between 1 and 100000: ")
            while num == '' or num < MIN or num > MAX:
                print "Invalid number"
                num = input("Enter in a number between 1 and 100000: ")
            hailstone(num)
            
        elif choice == "r" or choice == "R":
            firstNum, secondNum = enterNumbers()
            for num in range(firstNum, secondNum + 1):
                hailstone(num)
                
        elif choice == "l" or choice == "L":
            firstNum, secondNum = enterNumbers()
            for num in range(firstNum, secondNum + 1):
                if maxLength(num) > MAXLEN:
                    MAXLEN = maxLength(num)
                    MAXNUM = num
            print ("\n%d has the longest chain of %d\n") % (MAXNUM, MAXLEN)
                
              
    
main()

python

3 Contributors
7 Replies
590 Views
1 Day Discussion Span
Latest Post 12 Years Ago Latest Post by TrustyTony

All 7 Replies

woooee 814 Nearly a Posting Maven

12 Years Ago

if maxLength(num) > MAXLEN:
                    MAXLEN = maxLength(num)
                    MAXNUM = num
            print ("\n%d has the longest chain of %d\n") % (MAXNUM, MAXLEN)

The maxLenth function does not process the number more that once because of the "return num" statement, so the largest number will always be at the end of the range. Is the return statement indented properly, and do you want to return num or length?

Edited 12 Years Ago by woooee because: n/a

TrustyTony 888 pyMod

12 Years Ago

Compare with:
http://rosettacode.org/wiki/Hailstone_sequence#Python

Edited 12 Years Ago by TrustyTony because: n/a

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Yoink 0 Newbie Poster · Answer 1 · 2012-03-16T05:10:18+00:00

I want to find both the longest chain, and the number that produces that longest chain in any given range of numbers.

Yoink 0 Newbie Poster · Answer 2 · 2012-03-16T07:04:44+00:00

Sorry but im somewhat new to python and have a hard time following exactly what that example code is doing.

Yoink 0 Newbie Poster · Answer 3 · 2012-03-16T21:27:46+00:00

I believe I solved it by messing around with some indentation, seems to work from what I tested.

MAX = 10000
MAXNUM = 0
MAXLEN = 0

# isOdd() checks to see if a number is odd
# Inputs: num
# Output: True if odd, False if even
def isOdd(num):
    if num % 2 != 0:
        return True
    if num % 2 == 0:
        return False
    
# hailstone(0 runs the hailstone algoritm and
# runs while the number is not equal to 1
# multiplying the number by 3 and adding 1 if odd
# and dividing number by 2 if even till end is reached
# Inputs: num
# Outputs: num "->"
#          count
def hailstone(num):
    length = 1
    print num, "->",
    while num != 1:
    
        if isOdd(num) == True:
            length = length + 1
            num = (num * 3) + 1  
        else:
            length = length + 1
            num = num / 2
        if num != 1:
            print num, "->",
        else:
            print num,
            

        
    print ("; length = %d") % length

def maxLength(num):
    length = 1

    while num != 1:
    
        if isOdd(num) == True:
            length = length + 1
            num = (num * 3) + 1  
        else:
            length = length + 1
            
            num = num / 2
    return length
        



def printGreeting():
    print "This program finds hailstone sequences of numbers you choose.\
The next number in the hailstone sequence is found by dividing\
the number in half if it's even and multiplying by 3 and adding\
one if it is odd."
    
def enterNumbers():
    firstNum = getValidInt("Enter the starting Number between ", MIN, MAX)
    secondNum = getValidInt("Enter the ending number between ", firstNum + 1, MAX)

    return firstNum, secondNum


# used from notes
def getValidInt(question, min, max):
    value = max + 1
    prompt = question + " (" + str(min) + "-" + str(max) + "): "
    while value == "" or value < MIN or value > MAX:
        value = raw_input(prompt)
        if len(value) != 0:
            value = int(value)

    return value
    
def printMenu():
    print "\n\tI - View sequence for an Individual value\n"
    print "\n\tR - View sequence for a Range of values\n"
    print "\n\tL - Find the Longest chain\n"
    print "\n\tQ - Quit\n\n"

def main():
    MAXNUM = 0
    MAXLEN = 0
    choice = ''
    printGreeting()

    while choice != 'Q' and choice != 'q':
        printMenu()
        
        choice = raw_input ("Enter your choice: ")
        
        if choice == "i" or choice == "I":
            num = input("Enter in a number between 1 and 100000: ")
            while num == '' or num < MIN or num > MAX:
                print "Invalid number"
                num = input("Enter in a number between 1 and 100000: ")
            hailstone(num)
            
        elif choice == "r" or choice == "R":
            firstNum, secondNum = enterNumbers()
            for num in range(firstNum, secondNum + 1):
                hailstone(num)
                
        elif choice == "l" or choice == "L":
            firstNum, secondNum = enterNumbers()
            for num in range(firstNum, secondNum + 1):
                if maxLength(num) > MAXLEN:
                    MAXLEN = maxLength(num)
                    MAXNUM = num
            print ("\n%d has the longest chain of %d\n") % (MAXNUM, MAXLEN)
                
              
    
main()

woooee 814 Nearly a Posting Maven · Answer 4 · 2012-03-17T01:20:31+00:00

Looks good to me. hailstone() and maxLength() do the same thing so you should be able to use one function for both. Also, IsOdd would usually be formated like this

def isOdd(num):
    if num % 2 != 0:
        return True
    else:
        return False
#
#  or
 def isOdd(num):
    if num % 2 != 0:
        return True
 
   return False

TrustyTony 888 pyMod Team Colleague Featured Poster · Answer 5 · 2012-03-17T02:45:24+00:00

or

def is_odd(num):
     return num & 1

if you insist on boolean:

def is_odd(num):
     return bool(num & 1)

Finding longest number chain with hailstone algorithm

Recommended Answers Collapse Answers

All 7 Replies

Recommended Answers