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.
298
questions
0
votes
0
answers
23
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 ...
- 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 $...
- 16.4k
0
votes
0
answers
32
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 ...
- 67
0
votes
0
answers
39
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)$, ...
- 43
4
votes
1
answer
116
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 ...
- 3,325
0
votes
0
answers
51
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&{...
- 1
0
votes
1
answer
26
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)}}$$
...
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'...
- 1,219
3
votes
1
answer
95
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 ...
- 600
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 ...
- 11.8k
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?
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 304