ECOO contest 2015: Problem 1

This is my solution to the ECOO 2015 contest, problem 1, Fractorials. I'd appreciate any advice to improve readability, style, organization, etc.

def main():
number = int(input())
fractorial = {}
for i in range(2, number + 1):
prime_factorization = prime_factor(i)
update_fractorial(prime_factorization, fractorial)

print(compute_fractorial_value(fractorial))

def prime_factor(number):
primes = [2, 3, 5, 7, 11, 13, 17, 19]
dict = {}
i = 0
while i < len(primes):
p = 0
while number % primes[i] == 0:
number = number // primes[i]
p += 1

if p != 0:
dict[primes[i]] = p

i += 1

return dict

def update_fractorial(prime_factorization, fractorial):
for key in prime_factorization:
if key in fractorial:
if prime_factorization[key] > fractorial[key]:
fractorial[key] = prime_factorization[key]
else:
fractorial[key] = prime_factorization[key]

# Or should I replace the if/else statements with:
#
# if key in fractorial:
#   if prime_factorization[key] < fractorial[key]:
#      break
#
# fractorial[key] = prime_factorization[key]
#
# since it is shorter.

def compute_fractorial_value(fractorial):
value = 1
for key in fractorial:
value *= key ** fractorial[key]

return value

main()

• So basically you've to find the lowest common multiple! – hjpotter92 Sep 3 '18 at 4:15
• Welcome to Code Review! Your image of text isn't very helpful. It can't be read aloud or copied into an editor, and it doesn't index very well. Please edit your post to incorporate the relevant text directly (preferably using copy+paste to avoid transcription errors). – Toby Speight Sep 3 '18 at 8:04

Overall the code is quite easy to read, but it is more complicated than it needs to be.

    fractorial = {}
for i in range(2, number + 1):
prime_factorization = prime_factor(i)
update_fractorial(prime_factorization, fractorial)

print(compute_fractorial_value(fractorial))


I would expect the name fractorial to be either the final integer or the function which computes it. Perhaps fractorial_factorization would be a clearer name.

compute_fractorial_value doesn't actually do anything specific to fractorials. Perhaps compose_factorization or multiply_powers?

The algorithm used to compute the prime factorisation of the fractorial is correct, but overkill. If $p$ is a prime and $a$ is a positive integer, under what condition is $p^a$ a factor of the $n$th fractorial?

def prime_factor(number):
primes = [2, 3, 5, 7, 11, 13, 17, 19]
dict = {}
i = 0
while i < len(primes):
p = 0
while number % primes[i] == 0:
number = number // primes[i]
p += 1

if p != 0:
dict[primes[i]] = p

i += 1

return dict


Apart from the hard-coded primes, this is a standard implementation. I would suggest that p is more conventionally used to denote primes[i], so perhaps power would be a less surprising name.

def update_fractorial(prime_factorization, fractorial):
for key in prime_factorization:
if key in fractorial:
if prime_factorization[key] > fractorial[key]:
fractorial[key] = prime_factorization[key]
else:
fractorial[key] = prime_factorization[key]

# Or should I replace the if/else statements with:
#
# if key in fractorial:
#   if prime_factorization[key] < fractorial[key]:
#      break
#
# fractorial[key] = prime_factorization[key]
#
# since it is shorter.


Shorter still, and more explicit:

def update_fractorial(prime_factorization, fractorial):
for key in prime_factorization:
if key not in fractorial or prime_factorization[key] > fractorial[key]:
fractorial[key] = prime_factorization[key]


Although it's preferable to avoid repeating the lookup. The efficient way of doing this is

def update_fractorial(prime_factorization, fractorial):
for key, val in prime_factorization.items():
if key not in fractorial or val > fractorial[key]:
fractorial[key] = val


def compute_fractorial_value(fractorial):
value = 1
for key in fractorial:
value *= key ** fractorial[key]

return value


Apart from the previous comment about the name, the only thing I'd say here is that if you really want to scale this up, multiplying lots of small numbers is best done on a tree-like basis. I.e. you pair up the numbers, multiply each pair, pair up again, multiply again, ... But that's overkill for this problem.

main()


This is half-way between the naïve approach of not defining main() at all and just dumping its contents at the end, and the "best practice" approach of

if __name__ == "__main__":
main()


Might as well get used to the best practice approach now.

• Concerning the code you have suggested for the function update_fractorial, in the if condition, you wrote: if key not in fractorial or val > fractorial[key]. Wouldn't val > fractorial[key] raise an error if key is not in fractorial. So wouldn't you have a runtime error? – Alan Tam Sep 3 '18 at 16:57
• or short-circuits, so if key not in fractorial it doesn't evaluate fractorial[key]. – Peter Taylor Sep 3 '18 at 17:21
• So if you have the expression: A or B, then it will look at A first. If A is True, then there's no point of it looking at B because the expression will be still True. But if A is False, then it would have to look at B. – Alan Tam Sep 3 '18 at 17:44

Your iteration technique is a bit clumsy for Python:

• In prime_factor(), the while i < len(primes): loop would be better written as for prime in primes:.
• In compute_factorial_value(), the for key in factorial: loop would be better written as for prime, exponent in factorial.items():.
• Overall, you would be slightly better off using a collections.Counter rather than a dict for storing prime factorizations. The benefit is that every value in a Counter is implicitly 0, so you don't have to worry about non-existent keys.

Clarity could be improved as well:

• It's baffling that in an exercise whose goal is to compute the fractorial of a number, there is no fractorial(n) function.
• It's customary to organize the code to put the more primitive helper functions first, before defining the functions that rely on them. Therefore, main() should appear last.
• The update_fractorial() and compute_fractorial_value() functions are actually not specific to fractorials, and should therefore be named more generically.

Suggested rewrite

from collections import Counter

def prime_factors(number):
assert number <= 22
factors = Counter()
for prime in [2, 3, 5, 7, 11, 13, 17, 19]:
while number % prime == 0:
number //= prime
factors[prime] += 1
return factors

def update_factors(factors, new_factors):
for factor in new_factors:
factors[factor] = max(factors[factor], new_factors[factor])

def multiply_factors(factors):
value = 1
for prime, exponent in factors.items():
value *= prime ** exponent
return value

def fractorial(n):
factors = Counter()
for i in range(2, n + 1):
update_factors(factors, prime_factors(i))
return multiply_factors(factors)

if __name__ == '__main__':
print(fractorial(int(input())))


Simpler solution

As @hjpotter92 noted, the fractorial is simply the LCM of all numbers up to n. The answer can be computed with much less code. Note that functools.reduce() is a more elegant shorthand for a particular kind of loop. (In case you consider using the built-in math.gcd() to be cheating, you can easily reimplement it using the Euclidean Algorithm.)

Note that the challenge says that you should be prepared to accept an input file with multiple lines, which you haven't supported. I've used fileinput.input() to help with that.

import fileinput
from functools import reduce
from math import gcd

def fractorial(n):
lcm = lambda a, b: a * b // gcd(a, b)
return reduce(lcm, range(1, n + 1))

def main():
for line in fileinput.input():
n = int(line)
print('Fractorial ({0}) = {1}'.format(n, fractorial(n)))

if __name__ == '__main__':
main()