Sunday Times Teaser 2729 – Factorial Fact

by Nick MacKinnon

Published: 11 January 2015 (link)

The “factorials” of numbers are defined by 1! = 1, 2! = 2×1, 3! = 3x2x1, 4! = 4x3x2x1, etc.

It is possible to take eleven of the twelve factorials

1!, 2!, 3!, 4!, 5!, 6!, 7!, 8!, 9!, 10!, 11!, 12!

and to split them into groups of three, four and four so that in each group the product of the factorials in that group is a perfect square.

What are the factorials in the group whose product is the smallest?

One Comment Leave one →

Brian Gladman permalink


from itertools import combinations
from functools import reduce
from operator import mul

# return the product of the items in the sequence s
def product(s):
  return reduce(mul, s, 1)

# return True if the product of the items in the sequence
# s is a perfect square
def is_square_product(s):
  x = reduce(mul, s, 1)
  return round(x ** 0.5) ** 2 == x

# dictionary whose keys are factorials for n with n as its values
facts = {product(range(1, n + 1)):n for n in range(1, 13)}

# combine factorials in groups of four if the product 
# of their elements is a square
c4 = [x for x in combinations(facts, 4) if is_square_product(x)]

# combine two groups of four factorials
for q1, q2 in combinations(c4, 2):
  # that have no common elements
  if not set(q1) & set(q2):
    # and form the four factorials that are in neither group
    fr = tuple(set(facts) - (set(q1) | set(q2)))
    # combine these three at a time
    for f3 in combinations(fr, 3):
      # and find a group with a product of its elements that is a square
      if is_square_product(f3): 
        # sort the three groups in order of the product of their elements
        t = sorted((q1, q2, f3), key=product)
        # and invert factorial(n) to output these groups in terms of n 
        print(tuple(tuple(sorted(facts[x] for x in y)) for y in t))

from itertools import combinations

from functools import reduce

from operator import mul

# return the product of the items in the sequence s

def product(s):

return reduce(mul, s, 1)

# return True if the product of the items in the sequence

# s is a perfect square

def is_square_product(s):

x = reduce(mul, s, 1)

return round(x ** 0.5) ** 2 == x

# dictionary whose keys are factorials for n with n as its values

facts = {product(range(1, n + 1)):n for n in range(1, 13)}

# combine factorials in groups of four if the product

# of their elements is a square

c4 = [x for x in combinations(facts, 4) if is_square_product(x)]

# combine two groups of four factorials

for q1, q2 in combinations(c4, 2):

# that have no common elements

if not set(q1) & set(q2):

# and form the four factorials that are in neither group

fr = tuple(set(facts) - (set(q1) | set(q2)))

# combine these three at a time

for f3 in combinations(fr, 3):

# and find a group with a product of its elements that is a square

if is_square_product(f3):

# sort the three groups in order of the product of their elements

t = sorted((q1, q2, f3), key=product)

# and invert factorial(n) to output these groups in terms of n

print(tuple(tuple(sorted(facts[x] for x in y)) for y in t))

Sunday Times Teaser 2729 – Factorial Fact

by Nick MacKinnon

Published: 11 January 2015 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta