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
2
votes
0
answers
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 ...
- 15.2k
0
votes
0
answers
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 ...
- 15.2k
1
vote
0
answers
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 ...
- 723
1
vote
0
answers
76
views
Is the quadratic sieve algorithm on Wikipedia wrong/inefficient?
I'm confused by a few aspects of the algorithm.
https://en.wikipedia.org/wiki/Quadratic_sieve
First, I'm confused by the choice of $a_i$'s.
For each iteration:
Choose $x \in \{ 0, \pm 1, \pm 2, \...
- 21
0
votes
0
answers
27
views
A corollary of Brun's pure sieve from Opera de Cribro by Friedlander and Iwaniec
I'm stuck on the one (if not many) step of the proof of Corollary 6.2 (page 58) from the book "Opera de Cribro" by Friedlander and Iwaniec.
The statement is a corrollary of Brun's pure sieve ...
- 31
0
votes
1
answer
36
views
On the Sieve of Sundaram
I have an implementation of Sieve of Sundaram in C# that returns all odd primes as follows:
...
- 3,195
0
votes
0
answers
32
views
Sieving a sequence of integers using an AP
Consider the sequence $1, 2, 3, \cdots, N$ where $N = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{ e_k}$ is the unknown factorization of a given $N$.
Define the set
$$M = \left\{\overbrace{p_1, 2p_1, \cdots,...
- 3,195
1
vote
0
answers
22
views
Does the ability to factor in polynomial time give you smooth numbers in the number field sieve?
I have read that despite strong connections between prime factorization and DLP an algorithm for the former does not imply the latter directly. But I was reading about the number field sieve and it ...
- 11
0
votes
0
answers
40
views
An improved(?) expression for sieving intervals for prime numbers
I was looking at this question which postulates the existence of at least one prime number between the squares of successive primes. One of the complicating issues in addressing that conjecture as ...
- 7,123
4
votes
2
answers
180
views
Prime squares of the form $a^2+b^4$
The Friedlander–Iwaniec theorem states there are infinitely many primes of the form $p=a^2+b^4$.
I am interested in whether there are infinitely many primes satisfying $p^2=a^2+b^4$ and $a\neq p$.
I ...
- 307
0
votes
0
answers
24
views
Sieves in arithmetic geometry
What are some good resources to learn more about applications of sieve methods in arithmetic geometry?
There are some applications of sieve methods to function fields in the notes of Zeev Rudnick that ...
- 174
1
vote
1
answer
54
views
How to compute a smooth number over a factor base in General Number Field Sieve (GNFS) factoring algorithm?
Following this on page 12, I understand the first steps of the general number field sieve (GNFS) algorithm for factoring as follows:
Step 1:
Let
$$N = 77$$
and choose
$$m = 4$$
Then
$$N=77 = 1(4^3) + ...
- 710
0
votes
0
answers
28
views
Dirichlet convolutions and a formula given in Selberg's sieve
I was reading the Selberg's sieve theorem and stumbled on one equation that I honestly cannot understand. As in theorem, we let $A$ be a set of positive integers, $\mathcal{P}$ -set of primes, let
$$
...
- 1
8
votes
1
answer
387
views
Prime numbers $p$ such that $p-1$ has no small odd factors
I am interested in a (simple) proof of this result:
There exists $\alpha>0$ and infinitely many prime numbers $p$ such that $p-1$ does not have any odd prime factor smaller than $p^\alpha$.
I ...
- 239
2
votes
1
answer
113
views
Ramanujan's Proof of Chebycheff's Theorem
Background: We define $$\theta(x) := \sum_{p\le x} \log p$$
where the sum is taken over primes $\le x$.
Chebycheff’s Theorem: There exist positive constants $A$ and $B$ such that $$Ax < \theta(x) &...
- 13.2k
3
votes
1
answer
226
views
A general theorem concerning arithmetic functions
I am self-learning An Introduction to Sieve Methods and their Applications by Alina Carmen Cojocaru & M. Ram Murty.
The authors left the proof of Proposition 9.1.1 as an exercise and I try to ...
- 813
2
votes
0
answers
67
views
A general Sieve method
I am studying "Sieve Methods" by Halberstam and Richert and I'm kinda stuck. In chapter 2 "The Combinatorial Sieve", in the first chapter about a general Sieve method we want to ...
- 41
0
votes
0
answers
47
views
Sieving stage of Quadratic Sieve
N is number to be factored. I use this expression to set factor base size
$$
B = e^{\frac{\sqrt{2*\ln(n)*\ln(\ln(n))}}{4}}
$$
Then for each prime $p_i$ in factor base i compute such s that $s^2 \equiv ...
5
votes
0
answers
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 ...
- 15.2k
1
vote
1
answer
67
views
On a problem related to Lehmer sieve
I had asked this question about Lehmer's bicycle chain sieve and while exploring that, the following question came up.
Consider the residue representation of $187 = 11 \times 17$ for residues modulo $...
- 3,195
0
votes
0
answers
59
views
Sieving the range $[a,b]$
In Sieve of Eratosthenes we sieve the range $[1,N]$ by crossing out 1, then crossing out 2 and multiples of 2, then take 3 and then cross out 3 and multiples of 3 and so on... picking the next ...
- 3,195
1
vote
1
answer
61
views
Which is the lowest or most accurate upper bound formula for the maximum gap in this modified sieve of Eratosthenes after a particular iteration?
As I discuss a similar question regarding the best upper bound for maximum gap after $n^{th}$ iteration of sieve of Eratosthenes here, I'm interested to know whether such a thing is possible for a ...
user1115576
3
votes
1
answer
107
views
Random choice of distinctly-colored edges from edge-coloring of complete graph
Let $G = (V,E)$ be the complete graph on $n=2k+1$ vertices, and let $E = E_1\amalg\cdots\amalg E_n$ be a proper edge-coloring with $n$ colors. Suppose for each $1\leqslant i\leqslant n$, we choose an ...
- 2,173
0
votes
1
answer
90
views
Which is the lowest or most accurate upper bound formula for the maximum gap in sieve of Eratosthenes after a particular iteration?
Consider a function $a(x)$ which gives the larget gap in the sieve of Eratosthenes after the $x^{th}$ iteration.
So,
$a(0) = 0$
$a(1) = 1$, After removing the multiples of 2.
$a(2) = 3$, After ...
user1115576
1
vote
1
answer
93
views
The number of $n$ and $n+2$ that have at most seven prime factors
In Murty and Cojocaru, we have the theorem: As $x\rightarrow\infty$,
$$\#\{n\le x: n \text{ and } n+2 \text{ have at most seven prime factors}\}\gg \frac{x}{(\log x)^2}$$
The proof uses Brun's sieve ...
- 77
2
votes
1
answer
109
views
Consequence of Brun's Sieve
I'm following a text that uses Brun's sieve (as described in https://pages.cs.wisc.edu/~cdx/Sieve.pdf in Theorem 2.2.2) to prove the following theorem:
For any $\alpha\in\mathbb{Z},\alpha\neq0$, we ...
- 77
1
vote
0
answers
53
views
A question on primes larger than a bound in an arithmetic progression
Let $n \in \mathbb{Z}$ be a semi-prime with unknown factorization, $n = pq$, where $p, q \in \mathbb{P}$, the set of primes. Without loss of generality, let $p \lt q$.
Say we have done trial division ...
- 3,195
5
votes
1
answer
192
views
Iterating over numbers with many divisors
I would like to iterate over the numbers with more than $D$ divisors in a large range $[x, x+N]$. Current values I'm working with are $D=626$ and $x\approx N\approx10^{11}.$
At the moment I'm using a ...
- 31.9k
2
votes
0
answers
123
views
Questions Related to the Twin-Prime Conjecture
For the sieve of Eratosthenes, let $E_k$ be the number of elements left after removing all primes up to $p_k$ and their multiples from the set $\left\{1,2,3,...p_k\#\right\}$ where $p_k\#=\prod\...
- 6,908
1
vote
1
answer
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)$ ...
- 77
0
votes
1
answer
38
views
In Proving Gallagher's Larger Sieve
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\...
- 77
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 ...
- 1,334
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 ...
- 481
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}\\...
- 879
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....
user1060925
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 ...
user775699
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/...
user775699
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 ...
- 3,742
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/~...
user775699
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/~...
user775699
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....
user775699
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/...
user775699
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 ...
user775699
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 ...
user775699
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$ ...
user775699
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 ...
- 1,025
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 ...
user775699
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(...
- 6,373
1
vote
2
answers
123
views
Landau's problem in sieve theory
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 $[...
- 603