Skip to main content

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
0 votes
0 answers
21 views

Density or growth rate for Eisenstein integers by products and doing $2 x + k$

Consider these two sets of Eisenstein integers. SET 1 : constructed by these rules : a) any unit is in the set. b) if $x$ is in the set, then so is $2 x + 7$. c) if $x$ and $y$ are in the set then so ...
mick's user avatar
  • 16.4k
1 vote
0 answers
46 views

Comparing two sets : if $u$ is in the set, so is $2u +1$ vs $2u + 5$ (extended mersenne numbers followup)

Consider these two sets of odd positive integers. SET 1 : constructed by these rules : a) $1$ is in the set. b) if $x$ is in the set, then so is $2 x + 1$. c) if $x$ and $y$ are in the set then so is $...
mick's user avatar
  • 16.4k
0 votes
0 answers
31 views

Use the Legendre Sieve to find the number of $n\le x$ with exactly $k$ prime factors.

I am working on this problem: For $k\ge 1$, let $\pi_k(x)$ denote the number of $n\le x$ with exactly $k$ prime factors (not necessarily distinct). Use the Sieve of Eratosthenes (Legendre Sieve) to ...
Rudy's user avatar
  • 67
0 votes
0 answers
38 views

Normal Order of Distinct Prime Factor $\omega(n)$

Define $\omega(n)$ as number of distinct prime factors $n$ has, that is if $n=p_1^{a_1}... p_k^{a_k}$, then $\omega(n)=k$. It is commonly understood that normal order of $\omega(n)$ is $\log\log(n)$, ...
spicychicken's user avatar
4 votes
1 answer
115 views

What is a prime sieve method, and how did they help Zhang, Maynard and Tao?

At children's school we learned about the Sieve of Eratosthenes for sieving our primes from an interval of natural numbers. I was surprised to hear that "sieve methods" were used to make ...
Penelope's user avatar
  • 3,325
0 votes
0 answers
50 views

Smoothed and truncated Von Mangoldt function

The Von Mangoldt function $\Lambda : \mathbb{N} \to \mathbb{R}$ is defined as $$\Lambda (n)={\begin{cases}\log p&{\text{if }}n=p^{k}{\text{ for some prime }}p{\text{ and integer }}k\geq 1,\\0&{...
James's user avatar
  • 1
0 votes
1 answer
25 views

Is this sub-exponential time less than quadratic time in the quadratic sieve?

The L-Notation is defined as: $$L_n[\alpha,c]=e^{(c+O(1))\ln(n)^\alpha\ln^2(n)^{1-\alpha}}$$ As such, the Quadratic Sieve complexity is defined to be: $$L_n[1/2,1]=e^{(1+O(1))\sqrt{\ln(n)\ln^2(n)}}$$ ...
Simón Flavio Ibañez's user avatar
0 votes
1 answer
32 views

question about the definition of a sieve in a category

One way to define a sieve $S$ in category $C$ is as a collection of arrows with a common codomain that satisfies the condition: If $g: c' \rightarrow c$ is an arrow in $S$, and if $f:c'' \rightarrow c'...
Yan King Yin's user avatar
  • 1,219
3 votes
1 answer
86 views

Density of squares using large sieves

I am reading Serre's Lectures on the Mordell-Weil Theorem, where he specifically talks about a Large Sieve inequality and proceeds to give an example. Theorem. (Section 12.1) Let $K$ be a number ...
Batrachotoxin's user avatar
3 votes
0 answers
32 views

Does a set with no divisibility pairs necessarily have arbitrarily large gaps? [duplicate]

The set of prime numbers has the following properties: No element is divisible by any other element. We can find arbitrarily large gaps between consecutive elements. Does (1) imply (2) for arbitrary ...
Karl's user avatar
  • 11.7k
1 vote
0 answers
62 views

What does Schroeder mean by "we have found 4 more primes" in section 3.2 of his book Number Theory in Science and Communication (5th ed.)? [duplicate]

This has been puzzling me for a few days now. Here is the relevant excerpt from the book mentioned in the title: What four primes is he referring to, right at the end of the excerpt?
Daniel L's user avatar
  • 365
1 vote
0 answers
47 views

Question regarding basis (for a Grothendieck topology)

I am studying a little bit of basis (for a Grothendieck topology), following MacLane's Sheaves in Geometry and Logic. Here they give an example as follows, Let $\mathbf{T}$ be a small category of ...
babu's user avatar
  • 315
3 votes
0 answers
127 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
  • 16.4k
0 votes
0 answers
110 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
  • 16.4k
1 vote
0 answers
54 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
82 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
45 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
47 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,341
0 votes
0 answers
35 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,341
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
45 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
208 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
1 vote
1 answer
68 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
  • 802
0 votes
0 answers
36 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
441 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
  • 339
2 votes
1 answer
134 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
231 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's user avatar
  • 907
2 votes
0 answers
92 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
5 votes
0 answers
179 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
  • 16.4k
1 vote
1 answer
70 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,341
1 vote
1 answer
94 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,341
1 vote
1 answer
70 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
130 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,235
0 votes
1 answer
106 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
97 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
134 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
57 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,341
5 votes
1 answer
228 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
  • 32.2k
2 votes
0 answers
142 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
  • 7,621
1 vote
1 answer
91 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
50 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
82 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,344
0 votes
1 answer
113 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
1 vote
1 answer
99 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
  • 899
0 votes
1 answer
27 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
57 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
47 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,887
0 votes
1 answer
90 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
59 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

1
2 3 4 5 6