# Tagged Questions

36 views

I have a number triangle as follows: $$\begin{array}{|c|c|c|} \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline 0 ... 0answers 61 views ### Solving a Recurrence Relation With Summation and Tau Function How can I solve the following:$$ T(n) = \sum_{i = 1}^{d(n) - 2}T(v_i) + \sum_{i = d(n) - 1}^{n - 1}c + c' $$Where d(n) is the Tau function, and v is the set of values dividing n. e.g. d(18) = ... 1answer 93 views ### Show that gcd(x,y) and z = lcm(x,y) is primitive recursive For the gcd(x,y) we note: gcd(x,0) = x gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y))) succ(x) and mod(x,y) are both primitive recursive, so gcd(x,y) must be as well. z = lcm(x,y) if ... 1answer 193 views ### Computing sums of divisors in O(\sqrt n) time? I have a sequence: 1,3,5,8,10,14,16,20,23,27,\dots I know that the recursive relation is:$$p[i] := p[i-1] + \text{number of factors of $i$}, \quad \text{with $p[1]=1$.} How do I solve this ...
If I have a function called $f(x)$ that have several roots, integers and not integers. How can I find just the integer ones by approximations methods? A simple example would be ...
It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...