Finding longest number chain with hailstone algorithm

Question

Yoink 0 Newbie Poster

14 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()

algorithm-pseudocode python

3 Contributors
7 Replies
616 Views
1 Day Discussion Span
Latest Post 14 Years Ago Latest Post by TrustyTony

Dani AI

Generated 10 Months Ago

A few quick, practical notes that build on what and pointed out and what fixed.

The hard bug was the early return in maxLength that stopped the loop; called that out and corrected the indentation. Beyond that, two improvements make the program far more useful for arbitrary ranges: (1) separate “compute length” from “print sequence” (don’t print while computing lengths — it slows things and mixes concerns), and (2) memoize previously computed lengths so you don’t recompute long sub-sequences repeatedly when scanning a range.
Use integer division explicitly so code works on modern Python (use //), and keep a shared cache/dictionary across calls. The pattern below is concise, efficient, and easy to drop into your menu-driven program.

Example (Python 3 compatible):

def hailstone_sequence(n):
    while True:
        yield n
        if n == 1:
            break
        n = n//2 if n % 2 == 0 else 3*n + 1

def hailstone_length(n, cache):
    seq = []
    while n not in cache:
        seq.append(n)
        n = n//2 if n % 2 == 0 else 3*n + 1
    length = cache[n]
    for x in reversed(seq):
        length += 1
        cache[x] = length
    return cache[seq[0]] if seq else cache[n]

def longest_in_range(a, b):
    cache = {1: 1}
    best_n, best_len = a, 0
    for num in range(a, b+1):
        l = hailstone_length(num, cache)
        if l > best_len:
            best_n, best_len = num, l
    return best_n, best_len

Tips and gotchas

This uses a shared cache so repeated work is avoided — essential for ranges up to tens or hundreds of thousands.
For printing a chain, use hailstone_sequence(n) so the length logic remains fast and testable.
Watch Python 2 vs 3: // is required for integer division in Py3; input() vs raw_input() differs across versions.
Keep MAXNUM/MAXLEN as local variables (return the result from a function) rather than relying on globals.

All 7 Replies

woooee 814 Nearly a Posting Maven

14 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 14 Years Ago by woooee because: n/a

TrustyTony 888 ex-Moderator

14 Years Ago

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

Edited 14 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 ex-Moderator 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

Dani AI

Recommended Answers Collapse Answers

All 7 Replies

Recommended Answers