Those primes and omega

Published on November 7, 2024

On the 31st of October 2024, Mihai Prunescu gave a talk at the Logic Seminar in Bucharest presenting the results of our recent collaboration. This talk was entitled: “Primes Resurrection on Halloween”.

Our collaboration pertains to an arithmetic term approach to the prime numbers. In the spirit of Halloween, I will leave it somewhat mysterious for now, but let’s just say: I am extremely excited to share the results and I hope that you will find them as incredible as I do! The paper is finished and in its final stages of proofreading and internal verification. Barring any unforeseen issues, I anticipate that the preprint will be made available by the end of this month.

In the meantime, I would like to offer a sneak preview of a result from our paper: An arithmetic term for the omega function $\omega(n)$ , which counts the number of distinct prime divisors of $n$ . This is the OEIS sequence A001221. Starting from $n=1$ , it begins as

$\begin{align*} 0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 3, \ldots \end{align*}$

The following arithmetic terms are used in Mazzanti [1]:

$\begin{align*} \gcd(a,b) &= \left\lfloor \frac{(2^{a^2 b(b+1)} - 2^{a^2 b}) (2^{a^2 b^2} - 1)}{(2^{a^2 b} - 1)(2^{ab^2}-1)2^{a^2 b^2}} \right\rfloor \bmod 2^{ab} , \\ \nu_2(a) &= \left\lfloor \frac{\gcd(a, 2^a)^{a+1} \bmod (2^{a+1}-1)^2}{2^{a+1}-1} \right\rfloor , \\ \operatorname{HW}(a) &= \nu_2\left( \left\lfloor \frac{(2^{2a}+1)^{2a}}{2^{2a^2}} \right\rfloor \bmod 2^{2a} \right) , \end{align*}$

where $\operatorname{HW}(a)$ returns the Hamming weight of $a$ , and $\nu_2(a)$ returns the highest exponent of $2$ dividing $a$ .

We define the arithmetic term:

$\begin{align*} M(n) &= (2^{2 n (n+4)^2+n+4}-2^{n+4}) (2^{n+4}+1)^{-1} \\ &\quad - (2^{2n^2+8n}-1) (n 2^{2n^2+9n+5} - n 2^{2n^2+8n+1}) (n 2^{2 n^2 (n+4)} - n 2^{2 n^2 (n+4)} + 1) \\ &\quad \cdot (2^{2n+8}-1)^{-1} (2^{2n^2+8n}-1)^{-2} \\ &\quad + (2^{3n+13}-2^{2n+9}) (2^{2 n^2 (n+4)}-1) \cdot \ell_1 \cdot (2^{2n+8}-1)^{-3} (2^{2n^2+8n}-1)^{-1} \\ &\quad + n 2^{2n^2+10n+9} (2^{n+4}-1) (n 2^{2 n^2 (n+4)} - n 2^{2 n^2 (n+4)}+1) \cdot \ell_1 \cdot (2^{2n+8}-1)^{-3} (2^{2n^2+8n}-1)^{-2} \\ &\quad - n^2 (2^{2n^2+8n}-1) (2^{2n^2+9n+4}-2^{2n^2+8n}) \cdot \ell_2 \cdot (2^{2n+8}-1)^{-1} (2^{2n^2+8n}-1)^{-3} \\ &\quad - (2^{3n+12)}-2^{2n+8}) (2^{2 n^2 (n+4)}-1) \cdot \ell_3 \cdot (2^{2n+8}-1)^{-5} (2^{2n^2+8n}-1)^{-1} , \end{align*}$

where

$\begin{align*} \ell_1 &= n^2 2^{2(n+4)(n+2)} - (2 n^2+2n-1) 2^{2n^2+8n} + n^2 2^{2n^2+8n}-2^{2n+8}-1 , \\ \ell_2 &= n^2 2^{2n(n+4)(n+2)} - (2 n^2+2n-1) 2^{2 n^2 (n+4)} + n^2 2^{2 n^2 (n+4)} - 2^{2n^2+8n}-1 , \\ \ell_3 &= (6 n^4+12 n^3-6 n^2-12n+11) 2^{2(n+4)(n+2)} + (-4 n^4-12 n^3-6 n^2+12n+11) 2^{2n^2+8n} \\ &\quad + (-4 n^4-4 n^3+6 n^2-4 n+1) 2^{2(n+4)(n+3)} + n^4 2^{2n^2+8n)} -2^{6n+24} - 11 \cdot 2^{4n+16} \\ &\quad - 11 \cdot 2^{2n+8}-1 + n^4 2^{2(n+4)^2} . \end{align*}$

Theorem. For all $n \in \mathbb{Z}^+$ , one has

$\begin{align*} \omega(n) = \nu_2 \left( \frac{\operatorname{HW}(M(4n))}{4n+4} - 16 n \right) - 1 . \end{align*}$

This immense formula is difficult to appreciate. To maintain the air of mystery, I omit the proof for the moment. This result and its proof will be included in our forthcoming preprint.

References

[1] Stefano Mazzanti. (2002), Plain Bases for Classes of Primitive Recursive Functions, Mathematical Logic Quarterly.
[2] Mihai Prunescu and Lorenzo Sauras-Altuzarra. (2024), An Arithmetic Term for the Factorial Function, Examples and Counterexamples.

josephshunia

Categories:

discoveries

formulas

mathematics

prime numbers

Uncategorized

Joseph Shunia's Blog

Those primes and omega

References

Leave a Reply Cancel reply