On representability by arithmetic terms
Consider number-theoretic functions like tau(n), which represents
the number of divisors of n, sigma(n), which is the sum of the
divisors, or Euler's Totient function phi, the number of remainders
modulo n, which are relatively prime to n. There are methods to
compute these functions from the prime number decomposition of n, but
it is difficult to imagine arithmetic closed terms in n alone,
computing them.
Yet, those functions are Kalmar elementary and by the results of
Mazzanti and Marchenkov, such terms do exist. As well,
closed arithmetic terms represent the n-th prime and various
other number-theoretical functions.
I will show how such terms can be effectively constructed.
Mihai Prunescu
Last modified: Wed Apr 17 2024