griff's math blog!
I go by griff on Project Euler. This is where I’ll post some of the math and programming stuff that I’m working on or think is interesting. Any code will likely be written in Nim or Wolfram Language.
-
Calculating (1/2)! by Lattice Point Counting
Abstract. Here we’ll define $z! = \Gamma(z+1)$ which is standard practice.
We’ll start with an analytical lemma relating a function’s power series coefficient asymptotics to the values of the function itself. We’ll apply that to a function which is related to lattice points inside a circle. -
The Number Floor(n!/e) Is Even
Abstract. There’s a proof in this YouTube video.
We’ll prove it combinatorially instead. -
Summing Multiplicative Functions (Pt. 1)
Abstract. I’ll exhibit some methods for computing partial sums of multiplicative functions. Knowledge of how to sum more basic functions is assumed. We’ll use the square root trick constantly, as well as some basic number theory.
-
Nearly Disjoint Dilations: Primes
Abstract. I’ll prove that if $A$ has nonzero upper density, there are primes $p < q$ so that the intersection $pA \cap qA$ has nonzero upper density. We can also choose $p$ and $q$ to be very close to each other in a specific way. The proof will be probabilistic.
-
Density and GCDs
Abstract. Suppose $A$ is a set of natural numbers, and write $G$ for the set of all $\gcd(x, y)$ where $x, y$ are different members of $A$. I’ll prove that if $G$ has density zero, then $A$ has density zero. This will be written for people who have seen limits before but aren’t familiar with density. Therefore we will be deriving some of its simple properties first, and then aiming at the stated problem. I’ll present a nice proof which will prepare us for some generalizations I’ll get to in future posts.
-
Lucy's Algorithm + Fenwick Trees
Abstract. I describe how Lucy_Hedgehog’s algorithm works, and how it can be implemented. Then I show how Fenwick trees can be used to boost its runtime without much effort. The final runtime is at most $O(x^{2/3} (\log x)^{1/3})$ to compute $\pi(x)$.
I also give an extension to sums of primes and to primes in arithmetic progressions.
The implementation gives $\pi(10^{13})$ in less than 3s.