Last active
October 29, 2021 05:03
-
-
Save njamaleddine/dbc0d4f935cd5ff149099205e33c870e to your computer and use it in GitHub Desktop.
3x+1 problem
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| 3x + 1 problem | |
| https://en.wikipedia.org/wiki/Collatz_conjecture | |
| """ | |
| import argparse | |
| import sys | |
| parser = argparse.ArgumentParser( | |
| description="Calculate sequence for 3x+1 problem" | |
| ) | |
| parser.add_argument( | |
| "--number", | |
| help="the seed number" | |
| ) | |
| parser.add_argument( | |
| "--recursive", | |
| action=argparse.BooleanOptionalAction, | |
| help=( | |
| "Use the recursive function to calculate. Currently limited by " | |
| "maximum recursion depth." | |
| ) | |
| ) | |
| args = parser.parse_args() | |
| def convert_number(number_string): | |
| error = ( | |
| "Number must be an integer or a number to the power of an " | |
| "exponent, e.g. 2^68" | |
| ) | |
| if "^" in number_string: | |
| try: | |
| number, power = number_string.split("^") | |
| number = int(number) | |
| power = int(power) | |
| except (ValueError, TypeError): | |
| raise Exception(error) | |
| return number ** power | |
| try: | |
| return int(number_string) | |
| except (ValueError, TypeError): | |
| raise Exception(error) | |
| def calculate_recursive(number, sequence=[]): | |
| # TODO: memoize so we don't hit maximum recursion depth for some numbers | |
| sequence.append(number) | |
| if number == 1: | |
| return sequence | |
| if number % 2 == 1: | |
| return calculate_recursive((3 * number) + 1, sequence) | |
| return calculate_recursive(number // 2, sequence) | |
| def calculate_loop(number): | |
| sequence = [] | |
| while number > 1: | |
| sequence.append(number) | |
| if number % 2 == 1: | |
| number = (3 * number) + 1 | |
| else: | |
| number = number // 2 | |
| if number == 1: | |
| sequence.append(number) | |
| return sequence | |
| if __name__ == "__main__": | |
| number = convert_number(args.number) | |
| sys.stdout.write(f"Calculating the sequence for {args.number}\n") | |
| sys.stdout.write(f"The sequence is:\n") | |
| if args.recursive: | |
| sequence = calculate_recursive(number) | |
| else: | |
| sequence = calculate_loop(number) | |
| sys.stdout.write(f"{sequence}\n") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment