# 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.

288 questions
Filter by
Sorted by
Tagged with
39 views

### Prime twin counting by $\pi_2(t^2) =^? \sum_{2<j<t^2} (-2)^{\omega(j)} (1/2)(\lfloor{\frac{t^2}{j}}\rfloor +\lfloor{\frac{t^2-2}{j}}\rfloor) +C$?

Let $\omega(n)$ count the number of distinct prime factors of the integer $n \geq 2$. This $\omega(n)$ is called the prime omega function. Inspired by these ideas : Improved sieve for primes and ...
82 views

### Are there modular arguments for Legendre's conjecture?

Legendre's conjecture says that there is always a prime between $n^2$ and $(n+1)^2$ for every positive integer. See : https://en.wikipedia.org/wiki/Legendre%27s_conjecture Now I wonder why people ...
1 vote
31 views

### Large Sieve Inequality

I am currently delving into the Large Sieve Inequality, consulting Chapter 27 of Davenport's Multiplicative Number Theory. Having completed the chapter, I seek a deeper understanding of the practical ...
1 vote
76 views

159 views

### Density of extended Mersenne numbers?

Consider the subset of odd positive integers defined and constructed as follows by these rules : A) $1$ is in the set. B) if $x$ is in the set , then $2x + 1$ is in the set. C) if $x$ and $y$ are in ...
1 vote
67 views

1 vote
66 views

### On the Proof of the Normal Order of the Number of Prime Divisors

I'm working through Murty's "An Introduction to Sieve Methods and their Applications" and I've come across the Turan's Theorem and Corollary, showing the normal order of $v(n)$, where $v(n)$ ...
Without going into the details of the theorem, we have the following definitions: $\mathbf{B}$ is a non-empty finite set of integers and $\mathbf{T}$ be a set of prime powers. Suppose for each $t\in\... 0 votes 1 answer 73 views ### Some Sieves problems I'm currently reading some lectures notes on Sieves Problems and I stumbled across a couple of problems I'm not able to solve. Honestly, since this is my first time I'm reading on analytic number ... 0 votes 1 answer 98 views ### What is the most efficient way to compute sum of sum of divisors of all numbers from 1 to n? ​​$σ_1(i)$be the sum of divisors of$i$, Calculate ​$S(n) = \sum_{i=1}^n σ_1(i)$I am looking for something better than$O(\sqrt{n})$To address @ingix's question here is my$O(\sqrt{n})$python ... 0 votes 1 answer 74 views ### Example 1.2 Opera de Cribro I'm reading the book "Opera de Cribro" by J. Friedlander and H. Iwaniec, and Example 1.2 states Edit: Here$$A(x)=\sum_{m~:~m^{2}+1\leq x}1~~,~~A_{d}(x)=\sum_{\substack{m~:~m^{2}+1\leq x}\\... 0 votes 1 answer 26 views ### Help needed in deducing an inequality in a lemma in the proof of linnik's theorem. I have been reading Sieve theory from notes of Zeev Rudnick here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and I have a question on page 5 of lecture 14 here: http://www.math.tau.ac.... 0 votes 1 answer 58 views ### 2 questions in the proof of Brun Titchmarch Inequality This question is from lecture 13 of the notes of Sieve Theory here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html I have 2 questions in the proof of lemma 2.2 on page 3: Question 1 : I am ... 1 vote 1 answer 54 views ### 2 questions in the theory of Counting Perfect Squares I have been reading sieve theory from notes of zeev rudnick here :http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and in page 2 of lecture 16(http://www.math.tau.ac.il/~rudnick/courses/... 2 votes 0 answers 34 views ### van der Waerden's proof that a monic$p(x) \in \mathbb{Z}[x]$has Galois group$S_n$with probability 1 This paper mentions that van der Waerden proved some results on the density of monic integer polynomials with Galois group the symmetric group$S_n$in 1936. I have found van der Waerden's original ... 0 votes 1 answer 77 views ### Some questions in the proof of Analytic Large Sieve I am learning about the analytic large sieve from the lecture notes here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html . I have some question in lecture 15:http://www.math.tau.ac.il/~... 0 votes 1 answer 52 views ### Questions in proof of Arithmetic Large Sieve I am studying Arithmetic Large Sieve from following notes of Zeev Rudnick:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html I have questions in lecture 14 here: http://www.math.tau.ac.il/~... 0 votes 1 answer 46 views ### A question in proof of analytic large sieve I have been reading Sieve theory from notes of Zeev Rudnick here:http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html and I have a question on page 5 of lecture 14 here: http://www.math.tau.ac.... 0 votes 1 answer 94 views ### A question in proof of Linnik's Theorem in Arithmetic Large Sieve This question is from course notes in sieve theory and I am struck on this assertion in the proof of Linnik's theorem. Consider Page 4 of lecture 14 here: http://www.math.tau.ac.il/~rudnick/courses/... 0 votes 0 answers 60 views ### How to estimate S(z) in Arithmetic Large Sieve This question is part of a proof in course in Sieve Theory( http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html, precisely lecture 11 and 14)and I am not able to prove this particular ... 3 votes 1 answer 188 views ### Estimating reducible monic polynomials of degree n with integer coefficients of height of atmost N This question is from my assignment in Sieve Theory and I am struck on it. I am following following notes on Sieve Theory: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html Question: For a ... 3 votes 1 answer 60 views ### Show that number of primes$p\leq x$so that$2p+1$is also a prime... This question is from assignment 4 of the following sieve theory course: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html Question : Show that the number of primes$p\leq x$so that$2p+1$... 0 votes 0 answers 32 views ### Atkin sieve algorithm asymptotic analysis In section 5 in Atkin sieve paper. I don't really understand his analysis of algorithm complexity. He started with defining$\displaystyle W=12\left(\prod_{3<p\le \sqrt{\log N}}p\right)$which is ... 0 votes 1 answer 51 views ### What is meant by supported on prime numbers in this context? I am reading Sieve - Theory from following lecture notes of Prof. Zeev Rudnick: http://www.math.tau.ac.il/~rudnick/courses/sieves2015.html . I am studying lecture 11 page 6. But I think you will be ... 1 vote 1 answer 220 views ### Why do sieves have the parity problem? Sieve methods have the "parity problem". Terry Tao gives a "rough" statement of the problem: If A is a set whose elements are all products of an odd number of primes (or are all ... 6 votes 1 answer 215 views ### On an approximation to Goldbach's conjecture I've been recently reading Yuan Wang's paper on an approximation to Goldbach's problem, in which he showed that Proposition 1: For all large even integer$x$, there exists$1<n<x-1$such that$n(...
In Tao's blog, one of Landau's problems is interpreted in the setting of sieve theory. More precisely, the twin prime conjecture leads to considering the following: $A$ the set of prime numbers on \$[...