Unit 3 Sections 9 and 11 Challenge and Homework
Homework
Create an algorithm that will start with any positive integer n and display the full sequence of numbers that result from the Collatz Conjecture. The COllatz Conjecture is as follows:
- start with any positive integer
- if the number is even, divide by 2
- if the number is odd, multiply by 3 and add 1
- repeat steps 2 and 3 until you reach 1
Example: if the starting number was 6, the output would be 6, 3, 10, 5, 16, 8, 4, 2, 1
def Sequence(x):
list = [x]
while x != 1:
if x % 2 == 0:
x = x/2
list.append(x)
else:
x = (x*3) + 1
list.append(x)
return list
x=Sequence(6)
y=Sequence(4)
print(x)
print(y)
Problem: Given a specific integer N, return the square root of N (R) if N is a perfect square, otherwise, return the square root of N rounded down to the nearest integer
Input: N (Integer)
Output: R (Integer)
Constraints: Do not use any built-in math operations such as sqrt(x) or x**(0.5), Try complete the problem in logarithmic time.
Hint 1: Maybe you can use Binary Search to try and reduce the number of checks you have to perform?
Hint 2: Is there a mathematical pattern amongst numbers and their square roots that could help you reduce the number of searches or iterations you must execute? Is there some value or rule you can set before applying binary search to narrow the range of possible values?
Run the very last code segment below to load test cases and submission function
def Sqrt(N):
if N ==1 or N ==0:
return N
x = 0
p = N
while True:
q = (p + x)//2
if q * q == N:
return q
elif q * q > N:
p = q - 1
else:
x = q + 1
from math import sqrt as sq
test_cases = [0,1,4,85248289,22297284,18939904,91107025,69122596,9721924,37810201,1893294144,8722812816,644398225]
answers = [int(sq(x)) for x in test_cases]
def checkValid():
for i in range(len(test_cases)):
if Sqrt(test_cases[i]) == answers[i]:
print("Check number {} passed".format(i+1))
else:
print("Check number {} failed".format(i+1))
checkValid()