2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ are a and b two different primes? $\endgroup$ – miracle173 Jan 20 '18 at 16:53
  • $\begingroup$ I apologise, n and m are natural. $\endgroup$ – Mainak Roy Jan 20 '18 at 17:33
  • $\begingroup$ 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. $\endgroup$ – miracle173 Jan 21 '18 at 8:37
  • $\begingroup$ Honestly, I don't know how to mathematically approach it either. All my own findings were by looking for patterns. $\endgroup$ – Mainak Roy Jan 21 '18 at 9:08
  • $\begingroup$ I think there is an error in my recurrancy for small n and m (n or m in {0,1,2}) $\endgroup$ – miracle173 Jan 21 '18 at 12:00
2
$\begingroup$

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.$

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

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$.

enter image description here

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)$

$\endgroup$
  • $\begingroup$ I honestly did not understand what is going on here. Can you please explain? $\endgroup$ – Mainak Roy Jan 21 '18 at 16:03
  • $\begingroup$ @MainakRoy I tagged the formulas. which one is unclear? $\endgroup$ – miracle173 Jan 22 '18 at 5:56
  • $\begingroup$ I got what you meant upto the paraxial rectangle. But I can't understand what came after that. $\endgroup$ – Mainak Roy Jan 22 '18 at 6:06
  • $\begingroup$ you still understand (6)? $\endgroup$ – miracle173 Jan 22 '18 at 6:11
  • $\begingroup$ No. I understood upto (5) but didn't understand what the $R(A)\{A}$ term meant exactly. $\endgroup$ – Mainak Roy Jan 22 '18 at 6:38
1
$\begingroup$

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}}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – miracle173 Jan 22 '18 at 15:54
  • $\begingroup$ 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. $\endgroup$ – miracle173 Jan 22 '18 at 16:41
  • $\begingroup$ But g (2,2)= a^4 . b^3 . g (1,1)^2 . g (1,2) = (8,8) $\endgroup$ – SDA OFFICIAL Jan 22 '18 at 16:49
  • $\begingroup$ $b^{2^{(m-2)(m+1)}} =b^{2^0}=b$ if m=2 $\endgroup$ – miracle173 Jan 22 '18 at 16:52
  • $\begingroup$ 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 $\endgroup$ – miracle173 Jan 22 '18 at 17:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.