bsf / tzcnt and popcnt InstructionsToday, we’ll be looking at $p$-adic valuation defined on the integers, with a specific look at a special formula for finding the $p$-adic valuation of $n!$ for any given $n.$ We won’t be as concerned about optimizations this time, since we’re looking at something with a known formula.
This will be a very quick post with a bit of mathematics and programming, but this time we’ll be looking at the disassembly of our program!
bsf / tzcnt and popcnt Instructions
While looking through some of my older programming projects, I found my old Egyptian Form project, which implements a greedy algorithm described by Solomon W. Golomb [1] for turning any fraction of positive integers into a sum of reciprocals of positive integers in C++. Since I want to stretch out my programming legs some more in preparation for (hopefully) entering Georgia Tech’s OMSCS program, I decided to see if there’s anything related to this that I could do some mathematics on while also programming a basic demonstration. That’s when I found the following conjecture:
Erdős–Straus Conjecture. For every integer $N\geq 2,$ there exist integers $0 \lt x\leq y \leq z$ such that $\frac{4}{N} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}.$
This conjecture is still open, but it does lend itself nicely to computational verification. And it also features some interesting optimizations that allow for huge performance gains, like taking something that originally didn’t finish after several minutes (I ended the process before it could finish) to taking just about 1 ms!
Note that this is a journey I went on on my own, so there may be better and more correct ways of computing these than what I’ll look at in this blog post. I haven’t spent much time looking at the literature for this problem, except for the identities in Mordell [2] mentioned on the Wikipedia page for the conjecture. This is just the result of a couple of days of experimentation, discovery, and programming.
Suppose the positive integers are partitioned as $\left\{\left\{1\right\},\left\{2,3\right\},\left\{4,5,6\right\},\ldots\right\}.$ Call the elements of the partition $A_{n}$ where $A_{n}$ contains $n$ integers. Then, what is the sum of the integers in $A_{n}$? Call these sums $S_{n}.$
We can calculate a few sums easily by hand: $S_{1}=1,$ $S_{2}=5,$ $S_{3}=15,$ $S_{4}=34,$ $S_{5}=65,$ and $S_{6}=111.$
I actually did these in my head! But how? Well, with a little trick from our friend Gauss!
One of my favorite facts from combinatorics is that $\sum\limits_{0\leq k\leq n}\binom{n}{k} = 2^{n}$. To prove it is simple: Note that $2 = 1 + 1$, and that $\binom{n}{k} = \binom{n}{k}\cdot 1^{k}\cdot 1^{n-k}$, and appeal to binomial theorem:
$$\sum_{0\leq k\leq n}\binom{n}{k} = \sum_{0\leq k\leq n}\binom{n}{k}\cdot 1^{n-k}\cdot 1^{k} = \left(1+1\right)^{n} = 2^{n}.$$
But what can we say about $\sum\limits_{1\leq k\leq n}k\binom{n}{k}$, or maybe even more general binomial coefficient sums?
For each real number $t>1$, one can define a probability distribution $P_{t} = \left\{\mathrm{pr}_{t}\left(n\right)\right\}_{n\in\mathbb{N}}$ by $\mathrm{pr}_{t}\left(n\right) = \displaystyle{\frac{n^{-t}}{\zeta\left(t\right)}}$. This class of probability functions was studied by Golomb in [1]. In this post, we will prove a theorem about relatively $r$-prime $s$-tuples of integers.
This problem was studied for the case $r = 1$ by Nymann in Example 2 of Section 2 of [2].
I was recently introduced to an interesting polynomial problem.
Problem. Determine all polynomials $p\left(x\right)\in \mathbb{R}\left[x\right]$ such that $\left(x – 16\right)p\left(2x\right) = 16\left(x – 1\right)p\left(x\right)$ for all $x\in \mathbb{R}$.
While reading some course notes from MIT 18.703 (Modern Algebra), I came across the following statement on page 3:
Lemma 22.3. The product of all primes $r$ between $N$ and $2N$ is greater than $2^{N}$.
However, this can quickly be shown false for $N = 8$.
So I had a question: “How many more counterexamples are there?”
Continue reading
Recall that the harmonic series $\displaystyle{\sum_{n=1}^{\infty}\frac{1}{n}}$ diverges.
This is because we may bound the partial sums below, like so:
$$1+\frac{1}{2}+\left(\frac{1}{3}+\frac{1}{4}\right)+\left(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+\cdots >$$ $$\frac{1}{2}+\frac{1}{2}+\left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right)+\cdots=$$ $$\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\cdots\to\infty$$
We may replace $n$ by $an+b$, where $a,b\in\mathbb{R}$, $a$ and $b$ not both $0$, to retain a divergent sum, which we will prove below.
In an earlier post, titled A Fun Integral Problem, I gave a calculation for an integral as an infinite sum $\sum_{n=1}^{\infty}\frac{1}{n^{2}}$. I’ve been told that I should generalize it, so I’ll do that here (hence the title). I will also show how one may calculate some of the particular values of the Riemann $\zeta$ function we will be getting from this generalization, thus making good on my promise to give the value of that sum.
Problem. Calculate the integral
\[
\int_{\left[0,1\right]^{k}}\frac{dx_{1}\cdots dx_{k}}{1-x_{1}\cdots x_{k}}.
\]
Stop here if you want to try to use that previous post to solve this generalization. Continue reading for the solution as well as the actual values of the integrals for various values of $k$.
In two papers of Nymann and Leahey from the mid-to-late 70’s, they determined the asymptotics of the probabilities of selecting $k$ relatively prime integers [1] and selecting an integer which is $k$-free [2] according to the uniform and binomial distributions. I thought it would be a fun exercise to combine the results in the obvious way, extending their results in the binomial distribution while also coming up with an alternative proof of Benkoski’s result for the uniform distribution [3].
Continue reading