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
3answers
46 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
60 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
24 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 ...
0
votes
0answers
15 views

Do Sieve Methods all depend on some properties of prime number distribution?

Do Sieve Methods all depend on some properties of prime number distribution to reach any meaningful results ? Particularly, those sieve methods that are used in Goldbach Conjecture. Such as: Brun, ...
1
vote
0answers
36 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
83 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
70 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
27 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
49 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
43 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
25 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
23 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
38 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 ...
9
votes
0answers
239 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
50 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
32 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
98 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
203 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
47 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
152 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
141 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
55 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
105 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
72 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
132 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
88 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
292 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
76 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
96 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
49 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
122 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
57 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
92 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
358 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
130 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
126 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
135 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
193 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
263 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
192 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
87 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
53 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
232 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
248 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 ...
0
votes
1answer
140 views

On the probability that $ 2x^2 + 1 $ is prime (quadratic residue)

I tried to compute the multiplicative inverse of the probability that $ 2 x^2 +1 $ is prime. (I'm aware that proving there are infinitely many such primes is not done yet, but let's ignore that for ...