Sieve theory deals with number theoretic sieves, and sifted sets. E.g. the Sieve of Eratosthenes, Brun sieve, and other modern sives.

learn more… | top users | synonyms

3
votes
2answers
116 views

Can anyone sketch the proof or provide a link that there is always a prime between $n^3$ and $(n+1)^3$

In a recent forum discussion on number theory, it was mentioned that A. E. Ingham had proven that there is always a prime between $n^3$ and $(n+1)^3$. Does anyone know if there is a link available on ...
2
votes
0answers
21 views

parity problems for sieve methods, is it only for Selberg Sieve or for all sieve methods?

It is said that sieve methods have parity problems. Terence Tao gave this "rough" statement of the problem: "Parity problem. If A is a set whose elements are all products of an odd number of primes ...
2
votes
3answers
69 views

Arithmetic functions of particular type

Any there any natural functions real valued single variable that: changes (increases) values only at primes but otherwise stay constant (like a non periodic increasing staircase)? whose increase in ...
4
votes
1answer
66 views

Twin Primes between $n$ and $2n$

Is it theoretically possible for there to always be a twin prime pair between $n$ and $2n$ for all sufficiently large $n$ (assuming of course that there are infinitely many twin primes) or would this ...
0
votes
0answers
28 views

Quadratic Sieve, matrix problem

I read this: Quadratic Sieve Matrix Reduction and I am basically stuck. My Gaussian elimination says the answer is v= 0,0,0. Although you can clearly see that the correct answer is (1,1,1). How does ...
1
vote
0answers
38 views

Question about large sieve

I'm studing the large sieve inequality, following the method of Selberg. I'm reading the book "Opera de cribro", by Friedlander and Iwaniec. At page 154 I've found this ...
3
votes
0answers
85 views

Brun's sieve bounds

Working from Halberstam-Richert they state the following bounds \begin{align} S(\mathcal{A}; \mathfrak{P}, z) \leq XW(z)\left(1 + 2 \frac{\lambda^{2b + 1}e^{2\lambda}}{1 - \lambda^2 e^{2 + ...
4
votes
1answer
71 views

Factors of integers of the form $2^n-1$

I came across a problem where i had to tell the number of divisors of $2^i-1$ which are of the form $2^j-1$. I saw many contestants using the fact that if $i$ is divisible by $j$ then $2^i-1$ is ...
0
votes
1answer
30 views

Is the Legendre sieve explicit?

The Wikipedia page for the Legendre sieve... http://en.wikipedia.org/wiki/Legendre_sieve ...says that the Legendre sieve gives upper and lower bounds on the number of primes in a given range. In ...
1
vote
0answers
51 views

Fast algorithm for generating consecutive primes larger than N

I'm looking for a fast algorithm to generate primes larger than a random 4096 bit number $N$. I know about the Sieve of Atkin, but AFAIK it can only be used to find all primes up to a certain limit. ...
1
vote
1answer
45 views

Sizes of Blocks of Consecutive Integers Divisible by at Least One Prime Less than or Equal to $r$.

Let $f(r)$ be the largest integer such that there exists a block of $f(r)$ consecutive integers each divisible by some prime that is less than or equal to $r$. For example, $f(2)=1$ because it is ...
0
votes
0answers
26 views

On certain error terms

Define $$E_k(x)=-\sum_{d|k}\mu(d)B_1\left(\left\{\frac{x}{d}\right\}\right)$$ where $\mu(d)$ is the mobius function, and $B_1(x)$ is $x-1/2$ and $\{x\}$ is the fractional part of $x$. define $s(k)$ ...
0
votes
0answers
24 views

products of bernoulli poynomial

prove the following assuming that $d|k$, $e|k$, $(d,e)=gcd(d,e)$, $B_1(x)=x-1/2$, $\{x\}$ is the fractional part of $x$ $$ \int_0^k ...
1
vote
0answers
40 views

What is the status of research on primes as an example of general sieve-generated sequences?

I have been interested in treating the prime numbers as a special case of sieve-generated sequences, however they may be defined by different authors. Can someone here give me any information about ...
10
votes
0answers
273 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
0
votes
0answers
53 views

For all prime $\ p > \ 2,\ p=2^x \cdot Ord_p(2)+1$?

For all prime $\ p\ > \ 2,\ p=2^x \cdot Ord_p(2)+1?\ $ Where $\ x \in \mathbb{Z}_{\geq 0}.\ $ Such as $\ Ord_3 (2) = 2, \ 3=2^0 \cdot 2 + 1$. Is there some way to prove this?
0
votes
0answers
34 views

Wikipedia Sieve of Atkin Pseudocode

I want to as a question regarding Wikipedia's Sieve of Atkin pseudo code. The pseudocode is as follows: ...
0
votes
1answer
105 views

What are some good introductory textbooks on Sieve Theory?

I fail to find a duplicate. If it exists, please give me the link and close the question accordingly. As the title suggests, I am looking for recommendations on introductory books to Sieve Theory. ...
0
votes
2answers
208 views

Twin Prime Conjecture's Proof [closed]

I've found this article that claims to have a proof of the Twin Prime Conjecture. Can you find any error? (I have some doubts about the last page of the paper...)
0
votes
1answer
48 views

well known sieve?

Incidentally I've shown the following fact. Cancelling from the natural numbers $1$, the even integers, the integers of the form $n^2+2nk$, with $n>1$ odd and $k$ nonnegative, we obtain all (and ...
3
votes
1answer
153 views

Explanation for Terry T. post

I read here that : " If one inserts these inequalities into the Legendre sieve and optimises the parameter, one can improve the upper bound for the number of primes in $[N,2N]$ to $$O \left(\frac{N ...
2
votes
1answer
144 views

Sieving integers

Let $2=p_1,p_2,\cdots ,p_n$ be the first $n$ prime numbers. Suppose $N$ is a natural number and that $A=\{a+1,\cdots, a+N\}$ be a set of $N$ consecutive integers. Let $P_n=p_1\cdot p_2\cdot \cdots ...
0
votes
0answers
56 views

Recommend a good read on prime sieving for primes of the form $x^2 + y^2$

Recommend a good read on prime sieving, which can be applied to sieve primes of the form $x^2 + y^2$ (or $x^2 + ny^2$, if possible). I actually need to find up to a certain limit numbers that are ...
1
vote
0answers
111 views

Sieve for Prime Numbers

I will use some simple arguments on a prime numbers formula that has been deterministically checked by computer. I would like to compare this result with others you already know. The set of all ...
2
votes
0answers
73 views

Can anyone sketch an outline of Iwaniec's proof for the upper bound regarding the Jacobsthal function?

A proof by H. Iwaniec in 'On the problem of Jacobsthal, Demonstratio Math. 11, 225–231, (1978)' shows that: $$j(N) \ll \log \log (N)$$ where $j(N)$ is the Jacobsthal function. I am very interested ...
0
votes
1answer
137 views

collatz conjecture $\mod 2^n$ stopping distance

an interesting book Old and new unsolved problems in plane geometry and number theory by Klee/Wagon (1991) includes the Collatz conjecture. on p225 they consider iterates $\mod 2^n$ and state that ...
4
votes
1answer
113 views

Are most numbers of the form $a\cdot b^n+c$ composite?

It seems evident that for $a,b,c$ with $a>0$ and $b>1$ that there are only $o(x)$ primes of the form $a\cdot b^n+c$ with $n\le x.$ Has this been proven? Hooley (Applications of Sieves to the ...
0
votes
0answers
91 views

Is my sieve generalisable?

I was curious about extending Euler's polynomial generator n^2 - n + 41 for n > 41, and looking for the simplest sieves. I examined the gaps between non-primes and found a set of simple sieves of the ...
13
votes
0answers
306 views

Using the Brun Sieve to show very weak approximation to twin prime conjecture

I recently stumbled across MIT OCW for analytic number theory. As a budding number theorist, my ears perked up and I looked through some of the material haphazardly. I don't really know much about ...
2
votes
2answers
4k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
0
votes
2answers
77 views

Sieve of Erathosthenes - when can I stop crossing out?

Here is an exercise: Show that when finding the primes from 2 to $n$ using the Sieve of Erathosthenes, we can stop crossing out once $p \geq \frac{n}{2}$. Let $p$ be denoted by a star. Suppose ...
5
votes
1answer
98 views

Counting numbers of the form $ai + bj + cij$ and finding related L-series?

Let $a,b,c$ be given nonnegative integers with $gcd(a,b,c)=1$. Consider a given positive integer $n$ and positive integers $i,j$. Let $f_n(a,b,c)$ be the number of distinct solutions to $1<ai + bj ...
0
votes
2answers
51 views

At what rate are composites removed in a set after each prime multiple is cancelled out?

I was looking at sieves today, mainly sieving for primes and I noticed a pattern type thing. As I crossed out primes in a small set, the number of composites that were crossed out decreased. I haven't ...
3
votes
0answers
46 views

Question on Brun's Work

In Brun's Pure Sieve (using standard sieve theory notation), Brun showed that $$S(A,P,z)=A-\sum_{p\leq z}A_p+\sum_{p_1<p_2\leq z}A_{p_1p_2}-\dots\pm ...
1
vote
1answer
128 views

Efficiency of the Sieve of Eratosthenes.

It's well-known that the sieve of Eratosthenes, using the first $m$ primes {$p_1, p_2, ..., p_m$}, sifts out all composite numbers up to $(p_m+2)^2$, since every composite $n \lt (p_m+2)^2$ contains ...
2
votes
1answer
59 views

Selberg Sieve Question

The following question uses standard sieve theory terminology. Let $A=\vert\{a_n: a_n=n(n-2); n\in[N/2,N]\}\vert$ and let $A_d=\vert\{a_n: d\vert a_n\}\vert$. If we are looking for $S^T$ the number ...
0
votes
0answers
93 views

estimate $\sum_{x<p\le x+y} \log{p}/p$

In his paper the prime number theorem via the large sieve, A. Hildebrand made use of the following inequality $$\sum_{x<p\le x+y} \frac{\log{p}}{p} \le (2+o(1))\log{\frac{x+y}{x}}$$ where $x\ge y$ ...
2
votes
0answers
35 views

Least value of a multi-residue CRT

Given coprime moduli $m_1,\ldots,m_n$ with $k\ge2$ residues in each modulus, what is the least nonnegative value congruent to one of the specified residues to each modulus? Obviously it must be less ...
3
votes
0answers
372 views

Confusing proof of brun's theorem?

I read Brun's proof of Brun's theorem here : http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f110.image (and the following pages) and here http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f138.image ...
0
votes
1answer
136 views

Space complexity of the segmented sieve of Eratosthenes

It's commonplace to say that without compromising on the time complexity of $O(n\log\log n)$, the space complexity of the sieve of Eratosthenes can be reduced to $O(\sqrt{N})$ using a segmented ...
4
votes
1answer
128 views

Eratosthenes-like sieve - infinitely many left unstruck?

Given any infinite sequence $c_1,c_2...$ of natural numbers, if all of the natural numbers $x$ such that there exists $n$ such that $x\equiv c_n (\mod p_n)$ and $x \geq 2p$, where $p_n$ is the nth ...
3
votes
1answer
136 views

What happened to the Mertens constant in the strong prime twins conjecture ??

To estimate the amount of primes in an interval $\left(2,x\right)$ one might naively sieve by computing $ x \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)...\left(1-\dfrac{1}{p_i}\right)$ ...
3
votes
1answer
197 views

Is this the way to estimate the amount of lucky twins?

To estimate the amount of prime twins between $3$ and $x$ we just take $x \prod_{p}(1-2/p)$ where $p$ runs over the primes between $3$ and $\sqrt x$. Lucky numbers are similar to prime numbers. Does ...
2
votes
1answer
275 views

How does sieve that Chen used to prove Chen's theorem work?

In the Number Theory for Computing, Song Y. Yan states that Chen used "complicated arguments based on sieve method", when proving what is now called Chen's theorem. How does this sieve work? Does it ...
3
votes
1answer
198 views

Matrix Processing in the Quadratic Sieve

I am working through the example in implementation of the quadratic sieve, and I have got stuck at the very last part: the matrix processing. In the example we must find the vector $S$ by left null ...
1
vote
1answer
90 views

Differences among different sieves encountered in sieve theory

Are the sieve techniques used in understanding the twin prime conjecture or other number theoretical conjectures different from sieve theory used in primality testing or integer factorization? What ...
0
votes
1answer
39 views

Inequality from Erathostenes’ sieve

Let $a_1<a_2<a_3$ be three positive integers. Let $n$ be another positive integer, and $I$ an interval of $n$ successive integers. Denote by $\mu$ the number of integers in $I$ not divisible by ...
2
votes
1answer
55 views

Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?

Is there a way to quickly iterate multiples of some prime $N$ while avoiding multiples of blacklisted primes $X$, $Y$, $Z$, ...? By quickly I mean is there a faster way than: Increment current ...
9
votes
2answers
234 views

“Dirichlet's theorem” on pairs of consecutive primes

The number of primes in each of the $\phi(n)$ residue classes relatively prime to $n$ are known to occur with asymptotically equal frequency (following from the proof of the Prime Number Theorem). ...
3
votes
0answers
253 views

Question about recursive defined functions.

This question is about counting functions. With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ...