Archive

Posts Tagged ‘ProjectEuler’

Python: Collatz Sequence

April 24, 2019 Leave a comment



Python: Longest Collatz Sequence


Problem No.14 in ProjectEuler

Definition Wikipedia: Start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.

So the formula is: Starting with n, the next n will be:

n/2 (if n is even)

3n + 1 (if n is odd)


If we start with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

A walk through:

n=13, 13 is odd, then n = 13 * 3 + 1 , n= 40

n=40, 40 is even, then n= 40/2, n=20

n=20, 20 is even, then n=20/2, n=10

n=10, 10 is even, then n=10/2, n=5

n=5, 5 is odd, then n=5*3+1 , n=16

n=16, 16 is even, then n=16/2, n=8

n=8, 8 is even, then n=8/2, n=4

n=4, 4 is even, then n=4/2, n=2

n=2, 2 is even, then n=2/2, n=1
n=1 then end of sequence

The Task: The task in ProjectEuler is to searching for a the Number N, under one million, that produces the longest chain.


Overview to my python cases: In my company, we are not allowed to download any software, so i don’t have any Python platform. To solve this i am using an online python interpreter, some time it’s become slow. So in this code (and others) i am spiting the range in 10 each with 100,000 then running the code to get the longest chain in each range. So the Number N, under one million, that produces the longest chain is:


The Answer: In my previous codes or math solving challenges in pybites or ProjectEuler I am solving the problems, writing the code, but not posting my answer to ProjectEuler platform. Today, and with Problem No.14 i decide to post the answer in the ProjectEuler platform for the first time just to see what will happen. The answer was 837799, and I get this page.


















In the code bellow, i set the range from 1 to 50000.
The Code:


chain2=[]
longest=[0,0]
def collatz_Seq(num):

t= num

chain=[num]

while t !=1 :

if t%2==0:

t=t/2

chain.append(int(t))

else:

t=3*t+1

chain.append(int(t))

return chain

for num in range (1,50000):

chain2 = collatz_Seq(num)

if len(chain2) > longest[0]:

longest[0] = len(chain2)

longest[1] = num

chain2=[]

print(‘num:’,longest[1],’ has a longest chain: ‘,longest[0])









Follow me on Twitter..


Categories: Problem, Projects/Experiments, Python Tags: , , , , , , , , ,

Python: Amicable Numbers

April 18, 2019 Leave a comment



Python: Amicable Numbers


Problem No.21 on projectEuler

In this task we need to calculate the SUM of all divisors of N, from 1 to N.
Then we calculate the Sum of (sum of N divisors ) let’s say M .
Now if

For example, the proper divisors of A=220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore F(220) = 284. And the proper divisors of B=284 are 1, 2, 4, 71 and 142; so F(284) = 220. So F(A) =B and F(B)=A then A and B are amicable.

Definition:

If f(a) = b and f(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.


In this task we will ask the user to enter a Range of numbers and we will search for all Amicable Numbers pairs in that range(from – to) if we fond one we will print out the number and the divisors list. The main function here is the one that get the sum of divisors, we will call it get_divisors_sum and we will examine Amicable with If statement.

Hint ..
To check if the sum of divisors from both said are equal we use (t2==x )
AND that this sum are not same we use (t1!=t2)
AND that we did not print the pair before we use: (t2 not in ami_pair)



The Code:



#Python: Amicable Numbers
#Problem No.21 on projectEuler

num1=int(input(‘The range Start from:’))
num2=int(input(‘The range Ends at:’))

t1=0
t2=0
l=[]
l1=[]
l2=[]
ami_pair=[]

def get_divisors_sum (num):

t=0

l=[]

for a in range (1,num):

if num%a==0 :

l.append(a)

t=t+a

return t,l

for x in range(num1,num2):

l1=[]

t1,l1=get_divisors_sum(x)

l2=[]

t2,l2=get_divisors_sum(t1)

if (t2==x) and (t1!=t2) and (t2 not in ami_pair):

print(‘\nget_divisors_sum({}) is {} divisors={}’.format(x,t1,l1))

print(‘\nget_divisors_sum({}) is {} divisors={}’.format(t1,t2,l2))

print(‘\nSo {} and {} are Amicable Numbers .’.format(t1,t2))

ami_pair.extend((t1,t2))







Follow me on Twitter..


Categories: Problem, Projects/Experiments, Python Tags: , , , , , , , ,