Number Theory

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.

I'm in the process of putting together a different website to cover these topics in a more interesting, clearer way.

Anyway, in the meantime, here are the results of some of my older explorations. The very first link is probably the most noteworthy one, on the basis of the speed of the algorithm.

• Prime Counting in O(n^2/3 log n) time and O(n^1/3 log n) space with Linnik's identity

  (PDF, 2011-23-2011) 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.
  



• Some Results Concerning the Riemann Prime Counting Function and the Generalized Divisor Summatory Function

  (PDF, 2014-9-1) This paper collects and enumerates a number of my evolving thoughts and results about the divisor summatory function and the Riemann Prime Counting function. In particular, it contains interesting ways of connecting the Riemann Prime Counting function to the logarithmic integral, and also broaches the subject of the zeros of the generalized divisor summatory function.
  



• Divisor Functions and the Distribution of the Primes

  (PDF, 2013-10-5) This paper covers, in pretty good detail, elementary derivations of Linnik's identity and several ways of computing the number of primes. It has detailed Mathematica examples of almost all identities, making it good for exploration. As a document, it's a bit incomplete.
  



• A Few Novel, Quick Prime Number Counting Techniques

  (PDF, 2012-12-5) This paper presents several prime counting approaches all stemming from Linnik's identity. It includes both Mathematica and C code.
  



• Approximating the Prime Counting Function with Linnik's Identity

  (PDF, 2011-11-26) 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, 2011-11-27) 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, 2011-9-6) 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, 2011-11-23) 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 here.
  



• Earlies Writeup of Assorted Results Connected to Linnik's Identity

  (PDF, 2011-3-24) Before I wrote the above documents, I collected many of my results in the following long document. The document is perhaps somewhat less systematic than the above results, but it still contains a many possibly interesting results that I haven't yet added to any other papers.