1
vote
0answers
58 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) = ...
0
votes
1answer
54 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 ...
3
votes
1answer
181 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 ...
0
votes
0answers
344 views

How to find integer solutions of an equation using approximation methods?

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 ...
2
votes
0answers
94 views

Recursive Sequence from Finite Sequences

I'm searching for the name of these kind of sequences: Suppose you start off with a finite sequence containing one term: S0 = {3} To get the next sequence you ...
2
votes
0answers
72 views

A question on algorithm complexity

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