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.

Filter by
Sorted by
Tagged with
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 ...
mick's user avatar
  • 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 ...
mick's user avatar
  • 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 ...
zero2infinity's user avatar
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, \...
hidenori's user avatar
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 ...
LiangPrime's user avatar
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: ...
vvg's user avatar
  • 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,...
vvg's user avatar
  • 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 ...
Ian Campbell's user avatar
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 ...
Keith Backman's user avatar
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 ...
LeonardoOiler's user avatar
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 ...
Steppewolf's user avatar
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) + ...
James's user avatar
  • 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 $$ ...
zielik's user avatar
  • 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 ...
oVlad's user avatar
  • 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) &...
stoic-santiago's user avatar
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 ...
Kevin Zheng's user avatar
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 ...
mike lolis's user avatar
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 ...
Vitaliy Volovyk's user avatar
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 ...
mick's user avatar
  • 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 $...
vvg's user avatar
  • 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 ...
vvg's user avatar
  • 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 ...
user avatar
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 ...
BHT's user avatar
  • 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 ...
user avatar
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 ...
James2390's user avatar
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 ...
James2390's user avatar
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 ...
vvg's user avatar
  • 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 ...
Charles's user avatar
  • 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\...
Steven Clark's user avatar
  • 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)$ ...
James2390's user avatar
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\...
James2390's user avatar
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 ...
Alessandro's user avatar
  • 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 ...
ishandutta2007's user avatar
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}\\...
Nah's user avatar
  • 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....
user avatar
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 ...
user avatar
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/...
user avatar
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 ...
Vik78's user avatar
  • 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/~...
user avatar
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/~...
user avatar
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....
user avatar
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/...
user avatar
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 ...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
W. Wongcharoenbhorn's user avatar
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 ...
user avatar
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 ...
learningmathematics's user avatar
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(...
TravorLZH's user avatar
  • 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 $[...
Wirdspan's user avatar
  • 603

1
2 3 4 5 6