# Search father (x) of the number D(x) and measure time and memory consumed

We define function D(x) as following:

D(x) = x + sum of digits of x + sum of prime factors of x then call x the father of D(x)

Write a program that gets input t at the first line and then gets an input in the next t lines. If that input had father, print YES otherwise NO

For example 12 is the father of 20
20 = 12 + (1 + 2) + (2 + 3)

preferably write a separate function for each of these tasks:

1. Getting sum of the digits of a number
2. Getting prime factors of a number
3. Calculating D(x)

Notice that if you do lots of operations, you may get time limit error.

Time limit: 0.5 seconds
Memory limit: 128 MB

Input:
You get an input number t at the first line and then in the next t lines, you get number n for which you should solve the problem

Output:
Print the answer to each input in t lines.

Example:
Sample input:

2
4
20

Sample output:

NO
YES

I've written the code with python:

# function that returns the unique prime factors of number n as a list
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
factors = list(set(factors))
return factors

# function that returns the sum of digits of number n
def sum_digits(n):
r = 0
while n:
r, n = r + n % 10, n // 10
return r

# function to calculate the offspring of number X {D(X)}
def Offspring(X):
DX = X + sum(prime_factors(X)) + sum_digits(X)
return DX

ChildFather = {i: Offspring(i) for i in range(4, 1001)}
ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()
Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()
t = eval(input())
for i in range(0, t):
n = eval(input())
if n in Fathers:
print('YES')
else:
print('NO')


I guess this part of code

ChildFather = {i: Offspring(i) for i in range(4, 1001)}
ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()
Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()


is the bottle-neck for time limit. since I don't know how to find x by having D(x), I've solved the problem this way:

ChildFather = {i: Offspring(i) for i in range(4, 1001)}


for numbers 4<= n<= 1000, I've created a dictionary {n:D(n)}

ChildFatherValues = list(set(list(ChildFather.values())))
ChildFather.clear()


created a list of unique values of the dictionary and deallocated the memory used for the dictionary

Fathers = [i for i in ChildFatherValues if i <= 1000]
ChildFatherValues.clear()


create a list of values smaller than 1000 and deallocated memory used for the original list

t = eval(input())
for i in range(0, t):
n = eval(input())
if n in Fathers:
print('YES')
else:
print('NO')


If a given number exists n in the final provided list, I understand that n can be written as D(m)=m+sum of digits of m + sum of prime factors of m so n has the father m and I'll print Yes otherwise NO
But seems that the program is not efficient.

1. How can I measure the time consumed by this python program at run-time?
2. How can I measure the memory consumed by this python program at run-time?
(I'm new to python and am coding with sublime text 3 in Linux Ubuntu)
3. Is there any more efficient way of writing the code?
• Do you have the challenge source/link? Sep 17, 2018 at 12:56
• @Ludisposed Yeah, here it is. But it's in Persian. In fact it's not a challenge. This is an Iranian website to practice programming and this question was a homework passed to students of Sharif University of Iran 3 years ago in fall 2015. Now the question is for the people to practice. Sep 17, 2018 at 14:47
• I struggled with the terminology a bit. I think it's a little more conventional in English to call x the root of D(x), in case that helps anyone else reading this. Otherwise, great question, and welcome to Code Review! Sep 18, 2018 at 9:42

# PEP-8

Try to stick to PEP-8. So snake_case for variable and method names and a lot of other guidelines. Check any other Code Review Python post for tips from people who can explain this better than me.

# Memory

Since you have 128MB of memory available, and a list of 1000 integers (l = list(range(1000)); sys.getsizeof(l) + sum(map(sys.getsizeof, l))) takes only 37kb on my system, I would not worry about clearing intermediate results.

# Pre-calculate the primes to 1000

If the input number never goes beyond 1000, pre-calculating all the primes will be the fastest and most efficient. Here is method rwh_primes from this SO post adapted for Python 3:

def primes(n):
# https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Returns  a list of primes < n """
sieve = [True] * n
for i in range(3, int(n ** 0.5) + 1, 2):
if sieve[i]:
sieve[i * i :: 2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
return [2] + [i for i in range(3, n, 2) if sieve[i]]


This takes about 50µs on my PC.

# prime_factors

You do some of unnecessary calls to set and list. I would implement this as a generator, and store it further upstream as a set:

def prime_factors(n):
for factor in PRIMES:
if factor > n**.5:
yield n
return
while not (n % factor): # n is divisible by factor
yield factor
n //= factor
if n == 1:
return


# sum_digits

This one looks okay. You could use divmod, but that is a matter of taste.

# offspring

No need for the intermediate DX:

def offspring(x):
return x + sum(set(prime_factors(x))) + sum_digits(x)


# Main guard

Keep the main logic behind a if __name__ == '__main__': guard.

# eval

Instead of using eval, since you know it will be int, better use int(). eval can be dangerous, since it can execute arbitrary code. If you need to interpret a python literal, use ast.literal_eval.

Then you do something very inefficient by creating a dict, then take only the values, apply list, set and list again. Easiest would be to just use a set-comprehension:

all_offspring = {offspring(i) for i in range(1, 1001)}


This will include some numbers over 1000, but this extra memory should be negligible.

# Test

You can spoof input on your system by something like

test_case = '''2
4
20'''
input = iter(test_case.split('\n')).__next__


# main

if __name__ == '__main__':
PRIMES = primes(1000)
all_offspring = {offspring(i) for i in range(1, 1001)}
t = int(input())
for i in range(t):
n = int(input())
if n in all_offspring:
print('YES')
else:
print('NO')


# Timing

To time it you can use timeit module. There are enough posts on SO about this, and for memory usage.