8
$\begingroup$

Overview

While playing with numbers in my amateur math studies, I found a remarkable and beautiful function big delta that returns the highest prime number equal to or less than a given natural number. Iterating this function with $n = 1$ to $x$ outputs the list of all prime numbers between $1$ and $x$.

The big and small delta functions

Given a natural number $x$ with representation $d_t...d_1d_0=\sum_{i=0}^t d_i\cdot b^i$ in base $b$ we define: $$ \delta(x,b):=\sum_{i=0}^t d_i $$ so that $\delta(x,b)$ is the digit sum of $x$'s base $b$ representation. Based on this we define: $$ f(x):=\sum_{b=2}^{x+1}\delta(x,b) $$ and finally $$ \Delta(n):=\max_{2\leq x\leq n}\left[f(x)-f(x-1)\right] $$ Then it appears to be the case that $\Delta(n)$ is the largest prime less than or equal to $n$.

The big and small delta functions described

A visual rendering of the big delta function

A visual rendering of the big delta function

Experimental proof

In order to prove the above experimentally, I wrote an implementation of the small and big delta functions above in Python. It is available on the following GitHub repository: Big Delta GitHub repository

Sample output

Unfortunately, I can't input large quantities of text here. So here is a sample output of the above script for a very small set of big and small delta functions for numbers up to 15.

$$ \begin{array}{|c|ccc|cc|} \hline n&\Delta&df&f&\delta_2&\delta_3&\delta_4&\delta_5&\delta_6 &\delta_7&\delta_8&\delta_9&\delta_{10} &\delta_{11}&\delta_{12}&\delta_{13}&\delta_{14} &\delta_{15}&\delta_{16}\\ \hline 1 & - & - & 1 & 1 \\ 2 & 2 & 2 & 3 & 1 & 2 \\ 3 & 3 & 3 & 6 & 2 & 1 & 3 \\ 4 & 3 & 2 & 8 & 1 & 2 & 1 & 4 \\ 5 & 5 & 5 & 13 & 2 & 3 & 2 & 1 & 5 \\ 6 & 5 & 3 & 16 & 2 & 2 & 3 & 2 & 1 & 6 \\ 7 & 7 & 7 & 23 & 3 & 3 & 4 & 3 & 2 & 1 & 7 \\ 8 & 7 & 2 & 25 & 1 & 4 & 2 & 4 & 3 & 2 & 1 & 8 \\ 9 & 7 & 5 & 30 & 2 & 1 & 3 & 5 & 4 & 3 & 2 & 1 & 9 \\ 10 & 7 & 5 & 35 & 2 & 2 & 4 & 2 & 5 & 4 & 3 & 2 & 1 & 10 \\ 11 & 11 & 11 & 46 & 3 & 3 & 5 & 3 & 6 & 5 & 4 & 3 & 2 & 1 & 11 \\ 12 & 11 & 0 & 46 & 2 & 2 & 3 & 4 & 2 & 6 & 5 & 4 & 3 & 2 & 1 & 12 \\ 13 & 13 & 13 & 59 & 3 & 3 & 4 & 5 & 3 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 13 \\ 14 & 13 & 7 & 66 & 3 & 4 & 5 & 6 & 4 & 2 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 14 \\ 15 & 13 & 9 & 75 & 4 & 3 & 6 & 3 & 5 & 3 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 15 \\ \hline \end{array} $$ where in this table $df$ is shorthand for $f(n)-f(n-1)$ and $\delta_b$ is shorthand for $\delta(n,b)$.

Experimental results

I upload my experimental results here: Big Delta Github repository

It contains various outputs for [n]={1...31}, [n]={1...1024}, up to ~132'000.

Question 1

The above is no more than a conjecture because I did not provide a formal proof. In consequence, my main question is: how can we demonstrate this?

Question 2

Is this relationship found between the sums of digits in multiple bases and the set of prime numbers a well-known relationship or is it an original discovery?

$\endgroup$
  • $\begingroup$ In this field, $1024$ is nothing, I'm afraid Take it up to ten million at least, and see how it shapes up. $\endgroup$ – TonyK Oct 16 '16 at 20:30
  • 2
    $\begingroup$ This site is a question and answer site, and is not meant to be a means to publish mathematical results. $\endgroup$ – Thomas Andrews Oct 16 '16 at 20:30
  • $\begingroup$ It would help your question if you added a math outline of what the code does, plus plausible reasoning why you think it might work in general. $\endgroup$ – dxiv Oct 16 '16 at 20:37
  • 3
    $\begingroup$ Summarizing OP's description: $\delta(x,b)$ is the sum of the digits in the base $b$ representation of natural number $x$. Then $f(x)=\sum_{b=2}^x \delta(x,b)$ is the sum of these numbers over all bases $b$ from $2$ to $x$. Finally, $\Delta(n)=\max_{1 \le x \le n} (f(x+1)-f(x))$ is what is claimed to be the largest prime $\le n$. $\endgroup$ – angryavian Oct 16 '16 at 20:52
  • 1
    $\begingroup$ I edited my post accordingly to state my questions in clearer terms. Can you verify that the summary given in @angryavian's comment is indeed the math formulation of your question? If so, then that should be posted as the question, instead of raw code (or, at least, along it). This is primarily a math q&a site, and you can't assume that everybody speaks (or likes to decipher) Python. $\endgroup$ – dxiv Oct 16 '16 at 21:45
10
$\begingroup$

The Growth of $\delta_b$

Let us write $\delta_b(n)$ instead of $\delta(n,b)$ to mean the digit sum of the base $b$ representation of $n$. Then it turns out that we have $$ \delta_b(n)=n-\beta_b(n)\cdot(b-1)\tag1 $$ where $\beta_b(n)$ counts the number of times $b$ divides $1,2,...,n$ (counted by multiplicity). To see this, let us use the notation $n=(d_t,...,d_1,d_0)$ to mean $n=\sum_{i=0}^k d_i\cdot b^i$, and then consider $n$ of the form: $$ n=(d_t,...,d_k,0,...,0), \quad\text{where }d_k\neq 0 $$ for such $n$ we have $$ n-1=(d_t,...,d_k-1,b-1,...,b-1) $$ Comparing those we have: $$ \delta_b(n)=\delta_b(n-1)+1-k\cdot(b-1) $$ Therefore $\delta_b(n)$ is $1$ greater than $\delta_b(n-1)$ minus $b-1$ times the multiplicity $k$ of how often $b$ divides $n$. If $b$ does NOT divide $n$, we have $$ \delta_b(n)=\delta_b(n-1)+1\tag2 $$ Hence, as $n$ increases by $1$ repeatedly, $\delta_b(n)$ is increased by $1$ each time (starting from $\delta_b(1)=1$), but whenever $n$ is divisible by $b$ by a multiplicity of $k$, then $k$ times $b-1$ is subtracted. The claim expressed in $(1)$ follows. Note also that $$ \delta_b(b)=1\tag3 $$

These results lead to the following proof:


Proof of Correctness of Algorithm

Let $p$ be a prime number. Then $$ f(p)-f(p-1)=p\tag4 $$ This can be seen by first considering $\delta_b(p)$ vs. $\delta_b(p-1)$ for $b\leq p-1$. Since such $b$ does not divide $p$, we have from $(2)$ that $$ \delta_b(p)=\delta_b(p-1)+1 $$ and therefore $$ \sum_{b=2}^{p-1}\delta_b(p)=p-2+\sum_{b=2}^{p-1}\delta_b(p-1) $$ Now, since $\delta_p(p)=1$ and $\delta_p(p-1)=p-1$ which again has a difference of $p-2$, it follows that $$ \begin{aligned} f(p)-p&=f(p)-\delta_{p+1}(p)\\ &=\sum_{b=2}^p\delta_b(p)\\ &=\sum_{b=2}^p\delta_b(p-1)\\ &=f(p-1) \end{aligned} $$ and the claim in $(4)$ follows.


If on the other hand $n$ is composite having some $2\leq q<n-1$ as a factor, we have $$ \sum_{b=2}^{n-1}\delta_b(n)<n-2+\sum_{b=2}^{n-1}\delta_b(n-1) $$ because $\delta_q(n)<\delta_q(n-1)+1$ by equation $(1)$. Hence the conclusion this time becomes $$ f(n)-n<f(n-1)\iff f(n)-f(n-1)<n $$ which finishes the proof of the proposition.


A Final Remark - Complexity of the Algorithm

Note that your proposed algorithm is not very efficient as a primality test. One has to carry out $n$ base $b$ conversions of $n$ and $n-1$ conversions of $n-1$ in order to check whether $$ f(n)-f(n-1)=n $$ in which case $n$ is a prime number. In comparison, one could simply compute the single digit $d_0$ of the representation of $n$ in all bases $b=2,...,\lfloor\sqrt n\rfloor$, and if none of those were zero we would already know that $n$ is not divisible by $1<b<n$. Hence $n$ would be prime. So in this regard your algorithm wastes a lot of work. And there are even faster algorithms than that.

If ones goal is to compute $\Delta(n)$, the largest prime number less than or equal to $n$, the process is even heavier, since we then have to compute $f(x)$ for all $1\leq x\leq n$.


So I see your algorithm as more of a curious number theoretic result, rather than a proposal for an efficient way to approach prime number generation.

$\endgroup$
  • $\begingroup$ HI @String, thank you so much for your detailed answer. It took me a little bit of time to get through the demonstration but thanks to your explanations, I now gained a nice visual understanding of the whole reasoning. Finally, once nicely demonstrated, the whole thing becomes so obvious it loses interest. Best regards, David $\endgroup$ – David Doret Oct 20 '16 at 19:49
  • $\begingroup$ @DavidDoret: Well, in terms of efficiency/complexity the result is maybe not so promising, but I would say that you should keep playing around with numbers like this - at least this result was to some degree surprising and interesting in its own right :o) $\endgroup$ – String Oct 20 '16 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.