2
$\begingroup$

Is there an iterative formula for the function $d(n)$ ?
While d(n) is the count of divisors for n
For example in Euler's totient function $ \phi(nm)= \phi(n)\phi(m) . \frac{d}{\phi(d)} $ where $d=gcd(m,n)$
so using memorization we can iterate on a big number to get the result of $\phi$ without the need of factoring it for example :
to calculate $ \phi(12)$ we first make a list of primes then start a trial division process on that list obviously 2|12 so we perform
$ \phi(6 * 2)= \phi(2)\phi(6) . \frac{2}{\phi(2)} $ from that we get $ \phi(12)= 1*\phi(6)*2 $ since $ \phi(p) = p-1$
then we call the function again for $ \phi(6) $ and after that we save the result of 12 for later calculations of of it is multiples : $ \phi(12*m)= \phi(12)\phi(m) . \frac{d}{\phi(d)} $
so is the same thing possible for $d(n)$ ? is there a similar formula that can break a big number n into smaller parts then calculate those parts ?

  • 0
    This may be of some help: http://en.wikipedia.org/wiki/Divisor_function2012-12-01
  • 0
    not really the only thing there was when n = p*q (both primes)which is :$\sigma(n)=n+1+q+p$2012-12-01
  • 0
    You want $\sigma_0(n)$, not $\sigma(n)$. The former is the number of divisors of $n$. The latter should probably have been $\sigma_1(n)$ in the Wikipedia article...2012-12-01
  • 0
    @LoersAntario do you need to compute d(n) for a single n? Or for all n < K, K fixed?2012-12-01
  • 0
    @Haile for all n2012-12-03

1 Answers 1