Project Euler 12 (triangle numbers), solved using functools.reduce() and looping

Question

I have solved problem 12 on Project Euler website, which reads:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 +たす 2 +たす 3 +たす 4 +たす 5 +たす 6 +たす 7 =わ 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

And I've solved this in two ways:

1.functools.reduce()

import math
from functools import reduce
import time
def primeFactors(n):
 i = 2
 factors = {}
 num = 0
 while i ** 2 <= n:
 if n % i:
 i += 1
 else:
 n //= i
 num = factors.get(i, None)
 if num is None:
 factors[i] = 1
 else:
 factors[i] = num+1 
 if n > 1:
 num = factors.get(n, None)
 if num is None:
 factors[n] = 1
 else:
 factors[n] = num+1
 return factors
start_time = time.time()
numOfDivisors = 500
n = 2
while True:
 t = int(n*(n+1)/2)
 factors = primeFactors(t).values()
 if reduce(lambda x, y: x*y, [t+1 for t in factors]) >= numOfDivisors:
 print(t)
 break
 else:
 n += 1
print("----%s seconds ----" % (time.time() - start_time))

2.for-loop

import math
import time
def primeFactors(n):
 i = 2
 factors = {}
 num = 0
 while i ** 2 <= n:
 if n % i:
 i += 1
 else:
 n //= i
 num = factors.get(i, None)
 if num is None:
 factors[i] = 1
 else:
 factors[i] = num+1 
 if n > 1:
 num = factors.get(n, None)
 if num is None:
 factors[n] = 1
 else:
 factors[n] = num+1
 return factors
start_time = time.time()
numOfDivisors = 500
n = 2
while True:
 t = int(n*(n+1)/2)
 factors = primeFactors(t).values()
 k = 1
 for i in factors:
 k *= (i+1)
 if k >= numOfDivisors:
 print(t)
 break
 else:
 n += 1
print("----%s seconds ----" % (time.time() - start_time))

I tested out which one was faster, found that there was a fine line only:

1.670 secs and 1.678 secs

I attempted to calculate the average computing time by making the given number bigger from 500 to 1000, repeating this process 10 times.

But both solutions were done almost simultaneously:

1. functools.reduce

   [13.616845607757568, 13.67394757270813, 13.623621225357056, 13.596383094787598, 13.657264471054077, 13.694176197052002, 13.669324398040771, 13.65349006652832, 13.66620421409607, 13.57088851928711, 13.686619901657104]

2. for-loop

   [13.56181812286377, 13.686477422714233, 13.548126935958862, 13.565587759017944, 13.562162637710571, 13.556873798370361, 13.562631845474243, 13.572312593460083, 13.57419729232788, 13.567578315734863, 13.611796617507935]

Question: Are there any insignificant or significant differences between the two from a practical view and in a normal case, Or is this just a matter of behavior of two functions to use?

• 200_success: Your solutions give 253 as the answer. A number that is smaller than 500 cannot possibly have over 500 divisors.
• 123123123123123: @200_success There was incorrect indentation in primeFactors function. I fixed this. And.. thanks for your revision.

Answer 1

Here's an in-depth view from BDFL.

reduce should be faster, especially if you supply it with function that is written in C . Try replacing your multiplication lambda with operator.mul and see if anything changes.

There is a matter of style which of two functions to prefer, because more complex tasks would require more complex lambdas and the whole thing would be less comprehensible than for-loop. Thus, use of reduce was discouraged and it was moved into functools.

On the other hand, for less complicated tasks there are such things as sum, all and any. Latter two also short-circuit, whereas reduce does not.

• Peilonrayz: Could you source where it was said that reduce was removed as it didn't short-circuit? I always thought it was due to readability concerns
• Daerdemandt: Very funny. 123
• 123123123123123: your source seems very helpful for me. Thanks!