It is possible to find a generic solution for: $T(n)$ such that: $$T(n^2) = T^2(n)/n$$ with a start point defined in $T(p) = q$
and $ n, p, q \gt 1$ and $n, p, q \in Z_{+}$
I tried to solve it by developing the equation replacing variables, but I believe that this is not a correct or valid method. Does anyone have an idea?
Using the recursive development method, find one of the solutions, but I believe that this is not a generic and correct method. Does anyone have a suggestion? Let's do:
$$T(n^2) = \frac{T^2(n)}{n}$$
$$T(n^4) = \frac{T^2(n^2)}{n^2} = \left(\frac{T^2(n)}{n}\right)^2/n^2 = \frac{T^4(n)}{n^4}$$
$$T(n^8) = \frac{T^2(n^4)}{n^4} = \left(\frac{T^4(n)}{n^4}\right)^2/n^4 = \frac{T^8(n)}{n^{12}}$$
$$T(n^{16}) = \frac{T^2(n^8)}{n^8} = \left(\frac{T^8(n)}{n^{12}}\right)^2/n^8 = \frac{T^{16}(n)}{n^{32}}$$
$$......$$
$$T(n^z) = \frac{T^z(n)}{n^w}$$
$$w = g(z)$$ analyzing the evolution to find $w$:
for $z=2 \to w = 1 = 2^0$
for $z=4 \to w = 2*1 + 2 = 2^1 + 2^1 = 2*2^1$
for $z=8 \to w = 2(2^1 + 2^1) + 2^2 = 2^2 + 2*2^2 = 3*2^2$
for $z=16 \to w = 2(2^2 + 2*2^2) + 2^3 = 2^3 + 3*2^3 = 4*2^3$
for $z=32 \to w = 2(2^3 + 3*2^3) + 2^4 = 2^4 + 4*2^4 = 5*2^4$
$......$
for $z = 2^t \to w = t2^{t-1}$
But $t = \log_2 z \to w = (log_2 z)2^{log_2 z - 1} = (zlog_2 z)/2$
applying in $T(n^z) = \frac{T^z(n)}{n^w}$ we have do:
$$T(n^z) = \frac{T^z(n)}{n^{(zlog_2 z)/2}} $$
but the problem was that $T(p) = q$, so with $n = p$:
$$T(p^z) = \frac{q^z}{p^{(zlog_2 z)/2}}$$
doing $x = p^z \to z = log_p x$
so:
$$T(x) = q^{log_p x}/p^{(log_p x)*log_2 (log_p x)/2}$$
with $x = n$:
$$T(n) = q^{log_p n}/\left(n^{log_2 log_p n)}\right)^{1/2}$$
Now we must analyze the values of $n, p, q$ such that the function is possible! So we can find a domain for this solution.
Obviously one of the necessary conditions for the function to exist is that: $n \gt 1, p \gt 0 $ and $p \neq 1$.
As an example, see a sequence generated by the function starting at $T(2) = 4$ and how curious is its evolution:
$n = 2 \to T(2) = 4$
$n = 4 \to T(4) = 8$
$n = 16 \to T(16) = 16$
$n = 256 \to T(256) = 16$
$n = 256^2 \to T(256^2) = 1$
$n = 256^4 \to T(256^4) = 1/256^2$
$......$
$$\lim_{n\to \infty} T(n) = 0$$