MathDB
2011 PUMaC Combinatorics B4

Source:

September 24, 2019
combinatorics

Problem Statement

A function f:{1,2,,n}{1,,m}f:\{1,2, \ldots, n\} \to \{1, \ldots, m\} is multiplication-preserving if f(i)f(j)=f(ij)f(i)f(j) = f(ij) for all 1ijijn1 \le i \le j \le ij \le n, and injective if f(i)=f(j)f(i) = f(j) only when i=ji = j. For n=9,m=88n = 9, m = 88, the number of injective, multiplication-preserving functions is NN. Find the sum of the prime factors of NN, including multiplicity. (For example, if N=12N = 12, the answer would be 2+2+3=72 + 2 + 3 = 7.)