Author Archives: Brian
$p$-adic Valuation and the bsf / tzcnt and popcnt Instructions
Today, 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 … Continue reading
bsf / tzcnt and popcnt Instructions
Erdős–Straus Conjecture and Computing
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 … Continue reading
An Interesting Problem Involving a Partition of $\mathbb{N}\setminus \left\lbrace 0\right\rbrace$
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 … Continue reading
More Fun With Combinatorics: A Very Short Post
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 … Continue reading
The probability that $s$ integers are relatively $r$-prime for a class of probability distributions on the integers
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 … Continue reading
Fun Polynomial Problem
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}$.
On The Product of All Primes Between $N$ and $2N$ Compared to $2^{N}$
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 … Continue reading
All Harmonic Series Diverge — And a Consequence!
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 … Continue reading
A Generalized Fun Integral Problem (and Particular Values of the Riemann $\zeta$ Function)
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 … Continue reading
The probability that $s$ positive integers chosen according to the binomial distribution are relatively $r$-prime.
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. … Continue reading