I have spent a fair bit of time exploring sums of arithmetic functions from Number Theory (like the prime counting function, the Mertens function, and so on), especially from a computational perspective. Here are some of my results:
Prime Counting in O(n^2/3 log n) time and O(n^1/3 log n) space with Linnik's identity (PDF) This is a write up of an algorithm I've put together for counting the number of primes less than some number n,
relying on Linnik's identity and properties of the divisor summatory functions. This paper includes both a detailed description of the algorithm as well as a function C implementation that demonstrates
its running time properties.
Approximating the Prime Counting Function with Linnik's Identity (PDF) Starting from Linnik's identity, this paper shows that the divisor summatory functions in that identity
can be approximated in a fairly straightforward fashion that, when combined, immediately lead to Logarithmic Integral, thus providing an interesting representation of the error term in the Prime Number
Theorem. It uses a similar technique to derive approximations for Mertens function and Chebyshev's Psi function. I've been chewing on this idea for a while; see Sections 5, 6, and 7 of
this link for a public newgroup reference I made to this idea back from 2006 (this was from before I understood that I had rediscovered Linnik's identity, in fact).
Some notes from Professor Mark Coffey related to the ideas in this paper can be found here, which is a response to a previous threadbare document I had uploaded, found here.
Generalizing Linnik's Identity: Arithmetic Functions and Power Series(PDF) The core style of relationship of Linnik's identity can be massively generalized to
develop a more general theory of strict divisor-style functions that mimic the strict count of divisor function d_k. This leads to many, many other interesting number theoretic identities. This document
as currently written covers much of the core theory but lacks many of the specific identities that make it so interesting. Some of those identities can be found in the final link on this webpage.
This document should be considered incomplete and will be further updated.
Demonstrating One Connection Between the Prime Counting Function and the Logarithmic Integral(Webpage) This webpage has a visual demonstration of the connection that
Linnik's identity provides between the prime counting function and the logarithmic integral. Not strictly rigorous, it relies on flash and animation to explain the results.
Extending My Prime Counting Algorithm to Computing the Sums of Primes(PDF) My prime counting algorithm can actually be generalized to compute any non-negative integer prime sums in
O(n^2/3 log n) time and O(n^1/3 log n) space. This is an informal and rough write-up of how such an algorithm works. A rough implementation of this idea (with some shaky precision issues) can be found
Earlies Writeup of Assorted Results Connected to Linnik's Identity(Webpage) Before I wrote the above documents, I collected many of my results in the following
(c) 2011 icecreambreakfast.com |