# A recursive divisor function

Question:

Function definition:
$$f(1)=1$$ $$f(p)=p$$ where $p$ is a prime, and
$$f(n)=\prod {f(d_n)}$$ where $d_n$ are the divisors of $n$ except $n$ itself.

End result:

The end result of the function is when all divisors have been reduced to primes or 1.
Example:$$f(12)=f(2)f(3)f(4)f(6)=f(2)f(3)f(2)f(2)f(3)=f(2)^3f(3)^2=72$$

Question parts:

(a) Find a general formula for $f(a^n)$ where $a$ is a prime and $n$ is a natural number.
(b) Find a general formula for $f(a^nb^m)$ (following same notation). [Note: $a$ and $b$ are unique primes. $n$ and $m$, however, may be equal.]

Attempts at solutions:

(a) We have solved it. The solution is:
$a^{2^{n-2}}$ if $n≥2$,
$a$ if $n=1$.

(b) As of yet, none of us (me and my colleagues) have come up with a solution. We have solved the special cases $$f(ab^m)=a^{2^{m-1}} \times b^{(2^{m-2})(m+1)}$$ $$f(a^2b^m)=a^{(2^{m-1})(m+2)} \times b^{(2^{m-2})(m^2+5m+2)/2}$$ $$f(a^3b^m)=a^{(2^{m-1})(m^2+7m+8)/2} \times b^{(2^{m-2})(m^3+12m^2+29m+6)/6}$$
Update 1: $f(a^4b^m)$ has been solved as well.
$$f(a^4b^m)=a^{(2^{m-1})(m^3+15m^2+56m+48)/6} \times b^{(2^{m-2})(m^4+22m^3+131m^2+206m+24)/24}$$

An answer to the above questions is needed. A general formula for $f(n)$ is appreciated, along with an explanation.

• are a and b two different primes? – miracle173 Jan 20 '18 at 16:53
• I apologise, n and m are natural. – Mainak Roy Jan 20 '18 at 17:33
• I get the following reccurrency for the exponents of $a$ and $b$: if $$f(a^n \cdot b^m)=a^{e_1(n,m)}\cdot b^{e_2(n,m)}$$ and $$e(x,y)=(e_1(x,y),e_2(x,y))$$ then $$e(0,0)=(0,0),\\ e(1,0)=(1,0),\\ e(0,1)=(0,1), \\e(n,m)=2e(n-1,m)+2e(n,m-1)-2e(n-1,m-1)$$ But I don't know how t solve it. – miracle173 Jan 21 '18 at 8:37
• Honestly, I don't know how to mathematically approach it either. All my own findings were by looking for patterns. – Mainak Roy Jan 21 '18 at 9:08
• I think there is an error in my recurrancy for small n and m (n or m in {0,1,2}) – miracle173 Jan 21 '18 at 12:00

The polynomials in the exponent of $b$ can be written $${m+1\choose1}\\{m+3\choose2}-{2\choose1}\\ {m+5\choose3}-{3\choose1}{m+3\choose1}\\ {m+7\choose4}-{4\choose1}{m+5\choose2}+{4\choose2}$$ The values at $m=0,1,2$ are $1,2^k,2^{k-1}(k+2)$ so I predict the next two polynomials are $${m+9\choose5}-{5\choose1}{m+7\choose3}+{5\choose2}{m+5\choose1}\\ {m+11\choose6}-{6\choose1}{m+9\choose4}+{6\choose2}{m+7\choose2}-{6\choose3}$$

The polynomial for $a$ is the polynomial for $b$ coming from $m+1$ and $n−1.$

• The pattern is obvious here. But how to put it in terms of m and n? – Mainak Roy Jan 22 '18 at 13:45
• good guess, I checked the numbers for m=1,...,20 and they match. – miracle173 Jan 22 '18 at 15:01
• did you already find the pattern for the polinomials in the exponent of a? – miracle173 Jan 22 '18 at 15:04
• @miracle173 yes, in comments under the original post, the polynomial for $a$ is the polynomial for $b$ coming from $m+1$ and $n-1$. – Michael Jan 23 '18 at 6:33

The function can be defined recursively in the following way.

If $a$ and $b$ are different primes then $$f(a^m \cdot b^n)= a^r\cdot b^s \tag{1}$$ so we can use the function $e$ that uses and calculates the exponents of the primes instead of $f$ and $1$ can be written as $$e(m,n)=(r,s)\tag{2}$$

We have $$f(a^m\cdot b^n)=\prod\limits_{i=0,\ldots,m\\ j=0,\ldots,n\\ (i,j)\ne(m,n)} f(a^i\cdot b^j)\tag{3}$$ and therefore $$e(m,n)=\sum\limits_{i=0,\ldots,m\\ j=0,\ldots,n\\ (i,j)\ne(m,n)} e(i, j)\tag{4}$$

The area of the praxial rectangle defined by $A(m, n)$ is the area of the praxial rectancle defined by $B$ plus the area of the praxial rectancle defined by $C$ minus the area of the praxial rectancle defined by $D$.

And similar: The number of grid points in the praxial rectangle defined by $A(m, n)$ is the number of grid points of the praxial rectancle defined by $B$ plus the number of grid points of the praxial rectancle defined by $C$ minus the number of grid points of the praxial rectancle defined by $D$.

So the arguments of $e$ in the sum are all grid points contained in the paraxial rectangle determined by $A=(m,n)$. This rectangle is defined as
$$R(m,n)=\{(i,j),i=0,\ldots,m; j=0\ldots,n\}\tag{5}$$ then

$$e(m,n)=e(A)=\sum\limits_{(u,v)\in R(A)\setminus \{A\}}e(u,v)\tag{6}$$ $$= \sum\limits_{(u,v)\in R(B)}e(u,v)+\sum\limits_{(u,v)\in R(C)}e(u,v)-\sum\limits_{(u,v)\in R(D)}e(u,v)\tag{7}$$

But we have

$$e(B)=\sum\limits_{(u,v)\in R(B)\setminus \{B\}}e(u,v)\tag{8}$$ if the coordinates of $B$ are larger or equal than $3.$ So in this case we have

$$\sum\limits_{(u,v)\in R(B)}e(u,v)=e(B)+\sum\limits_{(u,v)\in R(B)\setminus \{B\}}e(u,v)=e(B)+e(B)\tag{9}$$ and similar holds for the other two sums so we finally get

$$e(m,n)=2e(m-1,n)+2e(m,n-1)-2e(m-1,n-1), \\ \forall m,n:\; m+n>2, (m,n)\not \in \{(2,1), (1,2)\},m>0, n>0\tag{10}$$

Further we have $$e(0,0)=(0,0)\\ e(1,0)=(1,0)\\ e(0,1)=(0,1)\\ e(2,0)=(1,0)\\ e(1,1)=(1,1)\\ e(0,2)=(0,1)\\ e(2,1)=(3,2)\\ e(1,2)=(2,3) \tag{11}$$

and $$e(m,0)=2e(m-1,0)\\ e(0,n)=2e(0,n-1) \tag{12}$$

From $(11)$ and $(12)$ we get

$$e(m,0)=(2^{m-1},0), \forall m>0\\ e(0,n)=(0,2^{n-1}), \forall n>0 \tag{12.1}$$

But I don't know how to solve this recursion.

Here is the code of the function e in Maxima

e[0,0]:[0,0];
e[1,0]:[1,0];
e[0,1]:[0,1];
e[2,0]:[1,0];
e[1,1]:[1,1];
e[0,2]:[0,1];
e[2,1]:[3,2];
e[1,2]:[2,3];
e[m,n]:=if (m=0) then 2*e[m,n-1] else (
if (n=0) then 2*e[m-1,n]
else 2*e[m,n-1]+2*e[m-1,n]-2*e[m-1,n-1]);

/* solution function of Michael */
sol(m,n):=2^(m-2)*if evenp(n) then
sum(combination(m+n+2*i-1,2*i)*(-1)^(n/2-i)*combination(n,n/2-i),i,0,n/2)
else
sum(combination(m+n+2*i,2*i+1)*(-1)^((n-1)/2-i)*combination(n,(n-1)/2-i),i,0,(n-1)/2);


From the calculations in the OP we see that $$\begin{eqnarray} e(1,m)&=&\left(2^{m-1},\right.& \left. 2^{m-2}(m+1)\right) \\ e(2,m)&=&\left(2^{m-1}(m+2),\right.& \left. 2^{m-2}\frac{m^2+5m+2}{2}\right)\\ e(3,m)&=&\left(2^{m-1}\frac{m^2+7m+8}{2},\right.& \left. 2^{m-2}\frac{m^3+12m^2+29m+6}{6}\right)\\ e(4,m)&=&\left(2^{m-1}\frac{m^3+15m^2+56m+48}{6},\right.& \left. 2^{m-2}\frac{m^4+22m^3+131m^2+206m+24}{24}\right) \end{eqnarray}$$ Michael proposed $$s(m,n)=\begin{cases} 2^{m-2}\sum\limits_{i=0}^{\frac{n}{2}}(-1)^{\frac{n}{2}-i}{m+n+2i-1 \choose 2i}{n\choose \frac{n}{2}-i} & n\equiv 0 \pmod 2\\ 2^{m-2}\sum\limits_{i=0}^{\frac{n-1}{2}}(-1)^{\frac{n-1}{2}-i}{m+n+2i \choose 2i}{n\choose \frac{n-1}{2}-i}& n\equiv 1 \pmod 2 \end{cases}$$ This math.stackexchange by Ross Milikan says that the solution of

$$F(m,n) = F(m-1,n) + F(m,n-1)\\ F(m,0)=F(0,n)=1 \tag{13}$$ is $$F(m,n)={{m+n}\choose{m}} \tag{14}$$

If we set $$e(m,n)=2^{m+n}h(m,n) \tag{15}$$ an substitute this in $(10) then we get $$2^{m+n}g(m,n)=2^{m+n}g(m-1,n)+2^{m+n}g(m,n-1)-2^{m+n-1}g(m-1,n-1)\tag{16}$$ and further $$g(m,n)=g(m-1,n)+g(m,n-1)-\frac{1}{2}g(m-1,n-1)\tag{17}$$ and $$g(m,0)=(\frac{1}{2},0)\\ g(0,n)=(0,\frac{1}{2})$$ The solution function$g$of$(17)$is smaller than the solution function$F$of$(13)$, because we add additionally a negative amount on the right side. So we can conlude that $$g(m,n)\le{m+n\choose m}\tag{18}$$ and further $$e(m,n)\le \left(2^{m+n}{m+n\choose m},2^{m+n}{m+n\choose m}\right)\tag{19}$$ So this is an upper bound for$e(m,n)$• I honestly did not understand what is going on here. Can you please explain? – Mainak Roy Jan 21 '18 at 16:03 • @MainakRoy I tagged the formulas. which one is unclear? – miracle173 Jan 22 '18 at 5:56 • I got what you meant upto the paraxial rectangle. But I can't understand what came after that. – Mainak Roy Jan 22 '18 at 6:06 • you still understand (6)? – miracle173 Jan 22 '18 at 6:11 • No. I understood upto (5) but didn't understand what the$R(A)\{A}$term meant exactly. – Mainak Roy Jan 22 '18 at 6:38 I Found $$f(a^n\cdot b^m) = a^{{(2^{m})}{(m-1)}} \cdot b^{{(2^{m-2})}{(m+1)}} \cdot \prod _{j=1} ^{m} \prod _{i=1} ^{n-1} f(a^i\cdot b^{j})^{2^{m-j}}$$ • I calculated g(u,v):=[2^v,2^((v-2)*(v+1))]+2^v*sum(sum(e[i,v-j],i,1,u-1),j,1,v);, where g(u,v) is your function (the exponents) and e(u,x) is my function and got g(2,2)=[12,5], which means$a^{12}b^5$. but my function calculates e([2,2])=[8,8]. So I think there is an error in your formula. – miracle173 Jan 22 '18 at 15:54 • g(u,v):=[2^v,2^((v-2)*(v+1))]+sum(sum(2^(v-j)*e[i,j],i,1,u-1),j,1,v) sorry, but I get g(2,2)=[8,6] now. – miracle173 Jan 22 '18 at 16:41 • But g (2,2)= a^4 . b^3 . g (1,1)^2 . g (1,2) = (8,8) – SDA OFFICIAL Jan 22 '18 at 16:49 •$b^{2^{(m-2)(m+1)}} =b^{2^0}=b$if m=2 – miracle173 Jan 22 '18 at 16:52 • g(u,v):=[2^v,2^(v-2)*(v+1)]+sum(sum(2^(v-j)*e[i,j],i,1,u-1),j,1,v) gives g(3,4)=[192,252] but e[3,4]=[208,252], but the exponent of b seens to be correct now. It also works for higher number – miracle173 Jan 22 '18 at 17:23 So, the friend who originally came up with this question also came up with a solution for it. $$f(a^mb^n)=a^{[F(m-1,n)]}\times{b^{[F(m,n-1)]}}$$ where $$F(m,n)=\frac{1}{2}\sum_{i=0}^{min(m,n)}{2^{m+n-i}\times{(-1)^i}\times{\frac{(m+n-i)!}{(m-i)!(n-i)!i!}}}$$ Note:$[X]$is smallest integer larger than$X$. I believe the above is a correct answer to part (b) of the question. Now only an answer to the final part (which was not part of the original question) is needed, which is to find a general formula for$f(n)$where$n\$ is any natural number.