Waste less time on Facebook — follow Brilliant.
×

Investigating Variations of the Prime Sieve

Introduction:

In one particularly dull class I found myself constructing visual sieves of numbers, starting with the well-known sieve of Eratosthenes which yields the primes. I then tried repeating the process, where instead the gap between eliminations is incremented by \(1\) successively. This results in a new sequence of numbers: 1,3,5,8,9,12,13,14,17,19,20,27,30,32,33,41,42,44...

I later searched the internet for more information on variations of Eratosthene's sieve, for example looking up the sequence on the OEIS, but couldn't seem to find anything related. I also made a few conjectures that seemed to be reasonable, for example:

  • Are there infinitely many of these numbers?
  • Can every number be represented as the difference of two of these?
  • Defining the counting function of this sequence up to \(n\) as \(d(n)\), is \(\lim(n\to \infty)\frac{d(n)}{n}=0?\)
  • And so on...

I believe I have proven the first conjecture (see below), and I would really appreciate for some of you guys to give suggestions or investigate this with me further. These numbers seem to display similar behaviour to the primes, for example here is a graph of \(\frac{d(n)}{n}\):

Definition of the Sequence:

The sequence 1,3,5,8,9,12,13,14,17,19,20,27,30,32,33,41,42,44... is obtained by eliminating numbers that come after some some initial number ("root"), \(n\), by successively adding \(n+i\), where \(i\) is the number of previous eliminations from the initial number. For example, starting from 1 we would eliminate by adding \(1+0=1\), getting us to 2, then \(1+1=2\), getting us to 4. The next root is then simply the smallest number not already in the sequence that also has not been eliminated, just like in the sieve of Eratosthenes. In my proof, I have named the set containing integers sieved this way \(D\).

Proof of Infinitude of \(D\):

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=\{x:\forall b,c\in\mathbb{N}, x\not =\frac{1}{2}(b+1)(b+2c-2)+1,x\in\mathbb{N}\}\) 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\in\mathbb{N}\) such that \(a\not=\frac{1}{2}(b+1)(b+2c-2)+1\). First, we let \(k=\frac{1}{2}(b+1)(b+2c-2)\) and look for solutions where \(k\in\mathbb{N}\). Substituting \(b=2m\) and \(c=2^n+1-m\), where \(n,m\in\mathbb{N}\), we notice that if \(2^n>m-1\), then \(k=2^n(2m+1)\) is a solution. We also find that if \(b=2^{n+1}-1\) and \(c=m+2-2^n\), where \(2^n<m+2\), then \(k=2^n(2m+1)\) is a solution.

Since for any \(n\) there exists some \(m\) such that either \(2^n>m-1\) or \(2^n<m+2\), \(k\) must always be of the form \(2^n(2m+1)\). Substitution into our original formula yields \(a=2^n(2m+1)+1\), implying \(S\) may only contain 1 and numbers of the form \(2^n+1\), as these are the only numbers that cannot be expressed this way.

Clearly, \(1\in S\). We will now show that all numbers of the form \(2^n+1\) are in \(S\). Let us assume that \((b+1)(b+2c-2)=2^n\). Then \(b+1\equiv 0\pmod 2\), but \(b+2c-2\equiv 1\pmod 2\), however \(2^n\) cannot have any odd factors other than \(1\), therefore \(b=c=1\) and \(r=0\), but \(0\not\in\mathbb{N}\), and so we have a contradiction. We can now define \(S=\{1\}\cup\{x:x=2^r+1,r\in\mathbb{N}\}\).

As there are infinite numbers of the form \(2^r+1\), we know that \(|S|\) is infinite, and since \(S\subset D\), \(|D|\ge |S|\), hence \(|D|\) is infinite.

Note by Daniel Castle
4 weeks, 1 day ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...