# Questions tagged [sieve-theory]

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

167 questions
20 views

### In the rational Sieve method why does n = gcd(a-b,n)×gcd(a+b,n) exactly?

As a quick notation explanation of the basic rational sieve method, a set of primes $P$ that are coprime to a number $n$ tested for primality are chosen randomly as follows(from wikipedia): Suppose ...
30 views

### Is or can Brun's twin prime theorem be generalized to a sum over all primes differing by less than a fixed gap?

With Zhang's theorem, and further work by others, if I understand it aright, there are infinitely many primes with a gap of less than or equal to 680. So, working from the opposite direction, it would ...
28 views

97 views

### Finding $p$ such that $pn \pm 1$ is prime for a fixed $n$

I want to find a prime $p$ such that $pn \pm 1$ is prime for some fixed $n$. Examples of $n$ are $1683$ or $99617$. Any $p$ will do, it doesn't need to be the smallest possible value. I have tried ...
36 views

### a question about the notation in the book “Opera de Cribro”

When I study the book "Opera De Cribro" by John Friedlander, Henryk Iwaniec-(2010), in Sections 1.2 and 1.3, I confused with notation used there. In page 3 it is defined: $$\cal{A} = (a_n) , n\le x$$,...
32 views

### How correct an estimate for twin primes obtained from the Rosser-Iwaniec sieve and Prime number theorem for arithmetic progressions could be?

Let $P$ be the set of primes $p$, $x \geq D \geq z^2 \geq 2$, and let $A⊂[1,x]$ be a set of integers. Suppose $A_{d}=|A| \frac{v(d)}{d}+R_{d}$ for square free d with $v$ being multiplicative and $v(p)$...
126 views

### How exactly does wheel factorization work and what is it used for?

I would like to learn how to use wheel factorization but am having trouble understanding it. I tried reading the wikipedia article but found it confusing (even the talk page says it's a mess). What ...
33 views

### Prove $π(x+y)- π(x) \ll \frac y{\log (\log (y))}$ using Legendre sieve such that $10 ≤ y ≤ x$

How to prove $$π(x+y)- π(x) \ll \frac y{\log (\log (y))}$$ using Legendre sieve such that $10 ≤ y ≤ x$?
57 views

### Fast sieve for sum of Euler totient values (phi) values from 1 to 'n'

I wanted to optimize the sieve method for computing Euler's Totient (Phi) values from 1 to n. Basically, i came across this Quora comment :https://www.quora.com/What-is-the-fastest-function-to-...
35 views

### Can you determine small primes from larger primes?

Suppose you are given the primes in the range $[n,n^2]$. Is there a known way to effectively reconstruct the primes less than $n$? Ideally, something that takes less calculation than figuring them out ...
42 views

173 views

62 views

### What is the set of numbers generated by this sieve called?

The sieve of Eratosthenes' characterizes the set of prime numbers by sifting composite numbers from the set of natural numbers $> 2$. Say we use the same sieve to instead sift all perfect powers ...
102 views

### Infinitely many primes $p$ such that $\frac{p-1}{2}$ is a product of two primes

The second answer to this question says the following: "I believe that sieve methods (in particular methods similar to Chen's result on "almost" Goldbach and twin primes) should give infinitely ...
50 views

### How long would it take a computer to check that a number is not divisible by any 20-digit prime?

If a computer could perform 10^18 division operations per second, how long would it take to check that a given number is not divisible by any 20-digit prime? So I think I'm supposed to use trial ...
129 views

### Generalization of Opperman's Conjecture

Does this conjecture have a name? What about a counterexample?: $$\forall n,k \in \mathbb{N}, k \gt 1, \exists d \in (kn-n,kn] \text{ s.t. } d \perp n!$$ An equivalent statement is this: Take a ...
759 views

132 views

### What should I do if I wrote an algorithm faster than the Sieve of Atkin?

I have been having fun with prime numbers. I sat down and, following a hunch and after a few weeks of headbanging against the wall, I was able to write an algorithm that, at least on my local, ...
35 views

### Why does this strategy sieve out composites without factors $2,3$?

Take $$3 + 2 = 5 \\ 3 + 4 = 7 \\ 5 + 6 = 11 \\ 5 + 8 = 13 \\ 7 + 10 = 17 \\ 7 + 12 = 19 \\ 9 + 14 = 23 \\ 9 + 16 = 25 \\ \cdots$$ I'm having trouble writing down what the pattern is to start with. ...
531 views

### Prime Factorization using The Sieve of Eratosthenes

I understand how the Sieve of Eratosthenes works for finding all primes less than a number n (start at 2 and cross out multiples and move on to next uncrossed out number and repeat etc.), but is there ...
61 views

### Why is $12$ special in relation to $6n\pm1$?

If you take the numbers of the form $6n\pm1$ and arrange them into $12$ columns, i.e., $$5,7,11,13,17,19,23,25,29,35,37,41,\ldots,$$ all the columns have digital roots that are the same throughout ...
33 views

### Unable to understand the meaning of $\mathcal{B\pmod t}$

My Question : What is the meaning(/definition) of the image of $\mathcal{B\pmod t}$ ? First of all what is the meaning of $\mathcal{B\pmod t}$ ?
Let $f$ be a primitive integral polynomial of degree $d$. In Arithmetical properties of polynomials, Ërdos says (page 417) that the integers $n$ for which $f(n)$ is $d$-th power free have positive ...