6
$\begingroup$

Context:

I am looking at a modified version of the sieve of Eratosthenes. I started by generalising Eratosthenes' sieve, like so:

  1. Choose some starting "root", $n_0\in\mathbb{N}$, a sieve limit (the highest number to sieve), $l\in\mathbb{N}$, and $f:\mathbb{N}^2\to\mathbb{N}^2$ such that $\forall a,b\in\mathbb{N}:f(a,b) > f(a,b-1)$.
  2. "Eliminate" numbers iteratively by adding $f(n_i,j)$ up to $l$, where $n_i$ is the current root and $j$ is the number of previous eliminations.
  3. The next root, $n_{i+1}$, is defined as the lowest number $>n_i$ not previously eliminated. If $n_{i+1}<l$, repeat from (2).
  4. We may then study the set of generated roots: $R=\{n_0,n_1,...,n_k\}$. Note that for a generalized counting function, $\pi(l)=|R|$.

Case $f(a,b)=a$ (the primes):

In this example, we let:

$n_0=2$,

$l=\infty$,

$f(a,b)=a$.

We start by adding $n_0=2$, eliminating multiples of $2$:

enter image description here

Our next root, $n_1$, is then $3$, and so the process repeats - yielding $P=\{2,3,5,7,11...\}$.


Case $f(a,b)=a+b$:

This is the case I have most recently been investigating. Note that, unlike primes, we may choose $n_0$ to be either $1$ or $2$. Let's define:

$n_0=1$,

$l=\infty$,

$f(a,b)=a+b$.

Then, we eliminate numbers from 1 by adding (0+1=1), (1+1=2), (2+1=3), etc:

enter image description here

The continuation of this sieve yields the roots $\{1,3,5,8,9,12,13,14,17,19,20...\}$, shown in the following diagram:

enter image description here

This set of roots appears to have a similar "pseudo-random" nature to the primes - highlighted by plotting a graph of $\frac{\pi(n)}{n}$, which appears to have some sort of asymptotic limit (perhaps 0, like the primes? One of my failed attempts to obtain a value resulted in $\frac{2}{9}$ before I spotted a logical error):

enter image description here

I've also managed to prove some results on this set, for example:

  • All numbers of the form $2^a+1$, where $a\in\mathbb{N}$, are roots, hence the cardinality of the set is infinite.
  • Given two $x,y$ in the set, if $x>y$, then there is only a finite amount of "overlap" (numbers eliminated by both $x$ and $y$). Furthermore, the largest such overlap can be given exactly by a fourth degree equation in $x$ and $y$. This is contrary to the primes, where two primes $x,y$ have infinite overlap at multiples of $xy$.
  • I have found an upper bound for the number of overlaps between $x$ and $y$ based on an inequality by Ramanujan.

If necessary I can post my proofs and further details for these statements as they currently reside in my notebook.


Question:

I have been trying to define an efficient algorithm for testing whether a number is a root, but can't seem to gain much insight. The current algorithm is, I believe, quite inefficient - requiring $O(n\sqrt{n})$ time and a lot of space. My main question is therefore: how do I improve the efficiency of my algorithm, and are there any known texts I may refer to related to these kinds of sieving methods within Computer Science? This would also help to quicken data gathering on these numbers.

Of course there are plenty more questions to ask, for example:

  • What is the value of $\lim\limits_{n\to\infty} \frac{\pi(n)}{n}$?
  • Can every number be written as the sum of two roots?
  • What can be said more generally of these sieves? I have only investigated the case $f(a,b)=a+b$. Perhaps $f(a,b)=a+b^2$ has a positive constant limit as its density, similar to how the harmonic series diverges whereas $\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}$.
  • Might these generalised number sieves have any practical applications? For example in cryptography?

EDIT #1: Proof of infinitude for case $f(a,b)=a+b$

We start with a formula for $a$, the $b$th number "eliminated" by some root $c$:

$$a=(b+1)c + \frac{1}{2}b(b-1)=\frac{1}{2}(b+1)(b+2c-2)+1$$

where $a,b,c\in\mathbb{N}$. The set

$$S=\left\{x:\forall b,c\in\mathbb{N}, x\not =\frac{1}{2}(b+1)(b+2c-2)+1,x\in\mathbb{N}\right\}$$

then denotes the set of all "strong" roots. These are roots not eliminated by any $n\in\mathbb{N}$, whereas the set $D$ contains all roots not eliminated by any $d\in D$. Since $D\subset\mathbb{N}$, we can conclude that $S\subset D$.

To determine which numbers are in $S$, we will investigate $a$ such that

$$a\not=\frac{1}{2}(b+1)(b+2c-2)+1$$

First, we let

$$2k=(b+1)(b+2c-2)$$

and look for solutions where $k\in\mathbb{N}$. Substituting

$$b=2m,c=2^{n-1}+1-m$$

where $n,m\in\mathbb{N}$, we notice that if $2^n>2m-2$, then

$$2k=2^n(2m+1)$$

is a solution. We also find that if

$$b=2^n-1,c=m+2-2^{n-1}$$

where $2^n<2m+4$, then

$$2k=2^n(2m+1)$$

is also a solution. Since

$$\forall n\in\mathbb{N}\exists m\in\mathbb{N}:\left(\left(2^n>2m-2\right)\lor \left(2^n<2m+4\right)\right)$$

we can conclude that

$$\forall b,c\in\mathbb{N}\exists n,m\in\mathbb{N}:\left(\frac{1}{2}(b+1)(b+2c-2)=2^{n-1}(2m+1)\right)$$

Substitution into our original formula yields

$$a=2^{n-1}(2m+1)+1$$

which implies $S$ may only contain numbers of the form $2^{n-1}+1$. We will now show that all numbers of the form $2^{n-1}+1$ are in $S$. Let us assume that

$$(b+1)(b+2c-2)=2^n$$

Then

$$b+1\equiv 0\pmod 2\implies b+2c-2\equiv 1\pmod 2$$

but $2^n$ cannot have any odd factors other than $1$, implying $b=c=1$, hence $r=0$, but $0\not\in\mathbb{N}$, and so we have a contradiction. Therefore

$$S=\left\{x:x=2^{r-1}+1,r\in\mathbb{N}\right\}\cup\left\{1\right\}$$

As there are infinite numbers of the form $2^{n-1}+1$, we know that $|S|$ is infinite, and since $S\subset D$, $|D|\ge |S|$, hence $|D|$ is infinite.

$\endgroup$
  • 1
    $\begingroup$ You will probably get more answers on Mathematics. They like this sort of thing. $\endgroup$ – Yuval Filmus Aug 1 '18 at 7:14
  • 1
    $\begingroup$ Is there any motivation for studying this sieve? Since to me, for a root $x$ it just sieves out $xj+a_j$ with any fixed sequence $a_j$. What about $a_j$ being linear in $j$, or even bounded by a constant? $\endgroup$ – Willard Zhan Aug 1 '18 at 18:01
  • $\begingroup$ @YuvalFilmus I posted a shorter related question on the Math stack exchange but didn't get much of a response. I thought I'd post here since I'm a CS student. $\endgroup$ – Daniel Castle Aug 2 '18 at 0:04
  • $\begingroup$ @WillardZhan There wasn't any particular motivation for the sieve I looked at, or any of this, though the idea of bounding $a_j$ by a constant sounds interesting, I'll have a look. $\endgroup$ – Daniel Castle Aug 2 '18 at 0:04
  • 3
    $\begingroup$ One technique which is sometimes helpful and which you don't mention having tried is to search the Online Encyclopedia of Integer Sequences. In this case it doesn't give any result, so I mention it (a) to save other people the effort; and (b) because you might find it helpful in future when working on other problems. $\endgroup$ – Peter Taylor Aug 2 '18 at 8:51

Your Answer

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

Browse other questions tagged or ask your own question.