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

2
votes
0answers
40 views

Online lecture Videos on Algebraic or Analytic Number Theory or Sieve Theory [closed]

I found some lectures on youtube but I need something which starts from the basics.Any help will be truly appreciated.
2
votes
2answers
33 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
3
votes
1answer
87 views

Distribution of composite numbers

This question is moved from mathoverflow, there are several excellent answers at mathoverflow which improve my question greatly. For more information, please see the original question posted on ...
1
vote
0answers
62 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
0
votes
0answers
11 views

An inequality related to Brun's sieve

My question is about the presentation of Brun's sieve by Gelfond & Linnik's Elementary methods in the analytic theory of numbers. The authors denote by $P(\Delta~;~D~;~x~;~a_1p_1b_1, \ldots, ...
1
vote
1answer
92 views

Factorizable huge semiprime

I'm trying to understand how the number decimal The correct decimal number is: ...
3
votes
2answers
128 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
41 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
75 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
82 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 ...
1
vote
0answers
43 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
98 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
73 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 ...
1
vote
2answers
61 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
69 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
55 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 ...
1
vote
0answers
42 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 ...
12
votes
0answers
398 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
1answer
160 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
255 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
158 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
149 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
62 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
124 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
1answer
155 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^2 (N)$$ where $j(N)$ is the Jacobsthal function. I am very interested in ...
0
votes
1answer
165 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
115 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
96 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 ...
14
votes
0answers
379 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 ...
3
votes
2answers
6k 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
105 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
51 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
144 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
74 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
94 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
479 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
202 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
134 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 ...
4
votes
1answer
150 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
219 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
318 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
239 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
99 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
56 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 ...