Happy Birthday, Undertale (9/15/2015)!

If $m,n$ are coprime positive integers, then a positive integer $a$ divides $mn$ if and only if $a = bc$ where $b,c$ are positive integers where $b$ divides $m$ and $c$ divides $n$ . Thus $P(mn) \; = \; \prod_{b|m\,,\,c|n} bc \; = \; \prod_{b|m}b^{\sigma_0(n)}P(n) \; = \; P(m)^{\sigma_0(n)} P(n)^{\sigma_0(m)}$ where $\sigma_0(n)$ is the number of divisors of $n$ . This means that $Q(n) = P(n)^{\frac{1}{\sigma_0(n)}}$ is a multiplicative function. Since $Q(p^a) \; = \; \left(\prod_{j=0}^a p^j\right)^{\frac{1}{a+1}} \; = \; p^{\frac12a} \; = \; \sqrt{p^a}$ for all primes $p$ and positive integers $a$ , we deduce that $Q(n) = \sqrt{n}$ for all $n\ge 1$ , and hence $P(n) = n^{\frac12\sigma_0(n)}$ . Note that $\sigma_0(n)$ is even except when $n$ is a perfect square, and so this formula for $P(n)$ always yields an integer, thankfully!

The last condition tells us that $\lfloor \tfrac12\sigma_0(N) \rfloor = 1100$ , and hence that $\sigma_0(N) = 2200$ or $2201$ . The second condition tells us that the index of $2$ in $N$ lies between $60$ and $84$ , and hence $\sigma_0(N)$ is divisible by some integer between $61$ and $85$ . There is no such factor of $2200$ , and hence $\sigma_0(N) = 2201 = 31 \times 71$ . Thus it follows that $N = 2^{70} \times p^{30}$ for some odd prime $p$ . This makes the first condition automatically true.

The smallest prime $p$ for which $2^{70} \times p^{30} \equiv 379 \pmod{915}$ is $p=11$ , and hence the answer is $2\times70+11\times30 = \boxed{470}$ .

Define $f(n)$ as the number of positive submultiples of a natural number $n.$

Lemma: $P(N)=N^{\frac{f(N)}{2}}.$

---

Let $\displaystyle N=\prod_{k=1}^m {P_k}^{A_k}.$

$~~~~\small \color{#3D99F6} \text{Let } 84 = 2^2\times3\times7.$

.

Then let's enumerate all the submultiples of $N,$ with all of them factorized.

$~~~~\small \color{#3D99F6} 2^0\times3^0\times7^0,~2^0\times3^1\times7^0,~2^0\times3^0\times7^1,~2^0\times3^1\times7^1,~2^1\times3^0\times7^0,~2^1\times3^1\times7^0,~2^1\times3^0\times7^1,~2^1\times3^1\times7^1,~2^2\times3^0\times7^0,~2^2\times3^1\times7^0,~2^2\times3^0\times7^1,~2^2\times3^1\times7^1$

.

For some arbitrary natural numbers $i\le m$ and $j\le A_i,$ we will see that ${P_i}^j$ is written exactly $f\left(\dfrac{N}{{P_i}^{A_i}}\right)$ times.

$~~~~\small {\color{#3D99F6}2^0}\times{\color{#D61F06}3^0}\times{\color{#EC7300}7^0},~{\color{#3D99F6}2^0}\times{\color{#E81990}3^1}\times{\color{#EC7300}7^0},~{\color{#3D99F6}2^0}\times{\color{#D61F06}3^0}\times{\color{#CEBB00}7^1},~{\color{#3D99F6}2^0}\times{\color{#E81990}3^1}\times{\color{#CEBB00}7^1},~{\color{cyan}2^1}\times{\color{#D61F06}3^0}\times{\color{#EC7300}7^0},~{\color{cyan}2^1}\times{\color{#E81990}3^1}\times{\color{#EC7300}7^0},~{\color{cyan}2^1}\times{\color{#D61F06}3^0}\times{\color{#CEBB00}7^1},~{\color{cyan}2^1}\times{\color{#E81990}3^1}\times{\color{#CEBB00}7^1},~{\color{#20A900}2^2}\times{\color{#D61F06}3^0}\times{\color{#EC7300}7^0},~{\color{#20A900}2^2}\times{\color{#E81990}3^1}\times{\color{#EC7300}7^0},~{\color{#20A900}2^2}\times{\color{#D61F06}3^0}\times{\color{#CEBB00}7^1},~{\color{#20A900}2^2}\times{\color{#E81990}3^1}\times{\color{#CEBB00}7^1}$

.

Which means, if we multiply all of them, ${P_i}^j$ will be multiplied $f\left(\dfrac{N}{{P_i}^{A_i}}\right)=\dfrac{\displaystyle \prod_{k=1}^n (A_k+1)}{A_i+1}$ times.

$~~~~\small \color{#3D99F6} \text{Think }N\text{ as a factorized form. }\dfrac{N}{{P_i}^{A_i}}\text{ contains everything except }{P_i}^{A_i},\text{ and therefore, all }(A_k+1)\text{'s are going to be multiplied except }(A_i+1).$

.

So if we multiply all ${P_i}^j$ 's, the product would be $\large ({P_i}^j)^{\frac{f(N)}{A_i+1}}=\left({P_i}^{\frac{f(N)}{A_i+1}}\right)^j.$

$~~~~\small \color{#3D99F6} \text{Remember, }\displaystyle \prod_{k=1}^n (A_k+1)=f(N).$

.

Since this applies for all $j\le A_i,$ if we multiply all the factors with base $P_i,$ the product would be $\large \left({P_i}^{\frac{f(N)}{A_i+1}}\right)^{\frac{A_i(A_i+1)}{2}}={P_i}^{\frac{f(N)\cdot A_i}{2}}.$

$~~~~\small \color{#3D99F6} 0+1+2+~\cdots~+j+(j+1)+~\cdots~+A_i=\dfrac{A_i(A_i+1)}{2}.$

.

Since this applies for all $i\le m,$ if we multiply all the submultiples of $N,$ (!!!) the product would be $\displaystyle \large P(N)= \prod_{i=1}^m {P_i}^{\frac{f(N)\cdot A_i}{2}}=\prod_{i=1}^m \left({P_i}^{A_i}\right)^{\frac{f(N)}{2}}=N^{\frac{f(N)}{2}}.$

Therefore the lemma is proven.

Now we see that $\displaystyle \left\lfloor\log_{N} P(N)\right\rfloor=\left\lfloor\frac{f(N)}{2}\right\rfloor=2015-915=1100.$

---

However, if $f(N)=2200,$ we need $2^{k}~(60\le k \le 84)$ multiplied inside $N$ however, $2200$ doesn't have a submultiple that is between $61$ and $85.$

$~~~~\small \color{#3D99F6} \text{CONDITION: }\dfrac{N}{2^{60}}\text{ is a natural number, but }\dfrac{N}{2^{85}} \text{ is not.}$

.

So we need $f(N)=2201=31\times71,$ so that $2^{70}$ is multiplied inside $N.$

Values of $N$ would be, then, $2^{70}\times7^{30},~2^{70}\times 11^{30},~2^{70}\times 13^{30},~...$

$~~~~\small \color{#3D99F6} \text{CONDITION: } N\equiv 379 \pmod{915};\text{ which implies that }N\text{ is not a multiple of 3 or 5.}$

.

Note that $N\equiv 1\pmod{3},~N\equiv4\pmod{5},~N\equiv13\pmod{61}.$

$~~~~\small \color{#3D99F6} 915=3\times5\times61;~379\equiv 1\pmod{3},~379\equiv4\pmod{5},~379\equiv13\pmod{61}$

---

Let $N=2^{70} \times 7^{30}.$ Then,

$N \equiv 4\times 9\equiv 6 \pmod{10};~N\equiv1 \pmod{5}.$

This is inconsistent with the condition, so this is not the correct answer.

.

Let $N=2^{70} \times 11^{30}.$ Then,

$N \equiv 1 \pmod{3}.~~~~~~\small\color{#3D99F6} \text{square of a natural number is always equivalent to 1 in mod 3.} \\ N \equiv 4\times 1\equiv 4 \pmod{10};~N\equiv4 \pmod{5}. \\ \begin{aligned} N & \equiv 2^{10} \times 121^{15} &&\small\color{#3D99F6} \phi(61)=60.\\ & \equiv 128\times8 \times (-1)^{15} &&\small\color{#3D99F6} 121\equiv -1 \pmod{61}. \\ & \equiv 6\times8\times(-1) &&\small\color{#3D99F6} 128\equiv 6 \pmod{61}. \\ & \equiv -48 \\ & \equiv 13 \pmod{61}. \end{aligned}$

This is consistent with all the conditions given, and thus, the minimum value for $N$ is $2^{70}\times 11^{30}.$

$\therefore~\displaystyle \sum_{k=1}^n p_k a_k = 2\times70+11\times30=\boxed{470}.$