Sieve theory deals with number theoretic sieves, and sifted sets. E.g. the Sieve of Eratosthenes, Brun sieve, and other modern sives.
4
votes
1answer
66 views
Eratosthenes-like sieve - infinitely many left unstruck?
Given any infinite sequence $c_1,c_2...$ of natural numbers, if all of the natural numbers $x$ such that there exists $n$ such that $x\equiv c_n (\mod p_n)$ and $x \geq 2p$, where $p_n$ is the nth ...
3
votes
1answer
53 views
What happened to the Mertens constant in the strong prime twins conjecture ??
To estimate the amount of primes in an interval $\left(2,x\right)$ one might naively sieve by computing $ x \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)...\left(1-\dfrac{1}{p_i}\right)$ ...
4
votes
1answer
117 views
Is this the way to estimate the amount of lucky twins?
To estimate the amount of prime twins between $3$ and $x$ we just take $x \prod_{p}(1-2/p)$ where $p$ runs over the primes between $3$ and $\sqrt x$. Lucky numbers are similar to prime numbers. Does ...
2
votes
1answer
79 views
How does sieve that Chen used to prove Chen's theorem work?
In the Number Theory for Computing, Song Y. Yan states that Chen used "complicated arguments based on sieve method", when proving what is now called Chen's theorem.
How does this sieve work? Does it ...
2
votes
1answer
64 views
Matrix Processing in the Quadratic Sieve
I am working through the example in implementation of the quadratic sieve, and I have got stuck at the very last part: the matrix processing. In the example we must find the vector $S$ by left null ...
1
vote
1answer
59 views
Differences among different sieves encountered in sieve theory
Are the sieve techniques used in understanding the twin prime conjecture or other number theoretical conjectures different from sieve theory used in primality testing or integer factorization? What ...
0
votes
1answer
34 views
Inequality from Erathostenes’ sieve
Let $a_1<a_2<a_3$ be three positive integers. Let $n$ be another positive integer, and $I$ an interval of $n$ successive integers. Denote by $\mu$ the number of integers in $I$ not divisible by ...
2
votes
1answer
49 views
Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …?
Is there a way to quickly iterate multiples of some prime $N$ while avoiding multiples of blacklisted primes $X$, $Y$, $Z$, ...? By quickly I mean is there a faster way than:
Increment current ...
9
votes
2answers
130 views
“Dirichlet's theorem” on pairs of consecutive primes
The number of primes in each of the $\phi(n)$ residue classes relatively prime to $n$ are known to occur with asymptotically equal frequency (following from the proof of the Prime Number Theorem). ...
0
votes
0answers
27 views
Definition of “sieve support associated to a prime sieve support”
Early on in E. Kowalski's "The Large Sieve and its applications", something called 'a prime sieve support' (denoted by $\mathcal{L}^*$) is defined to be a finite subset of some index set $\Lambda$. ...
3
votes
0answers
132 views
Question about recursive defined functions.
This question is about counting functions.
With counting functions $F$ I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ...
0
votes
1answer
104 views
On the probability that $ 2x^2 + 1 $ is prime (quadratic residue)
I tried to compute the multiplicative inverse of the probability that $ 2 x^2 +1 $ is prime.
(I'm aware that proving there are infinitely many such primes is not done yet, but let's ignore that for ...
0
votes
0answers
37 views
sum over prime index done by a weird sieve?
As you might have noticed i considered in 2 previous questions sums of the form $f(p_i x)$ where the sum is over the primes $p_i$ ( between some integer bounds : $a \leqslant p_i \leqslant b$ ) , $x$ ...
2
votes
0answers
115 views
How many co-primes are there for a big integer N over a specified interval?
How many co-primes are there for a big integer $N$ over a specified interval ?
bounds of $N$ are $[1,10^9]$ and the interval is $[a,b]$ where ($1\leq a\leq b \leq 10 ^{15}$) and there are $100$ ...
1
vote
1answer
151 views
Numbering primes within a range.
$$n\ln n + n\ln\ln n−n < p_n < n\ln n+n\ln\ln n \mbox{ for } n\geq 6$$
This is the range where the $n$-th prime must lie.
However sieving within this range generates a large number of primes. ...
1
vote
1answer
126 views
How to select the values X and Y in the Sieve Of Atkin Algorithm
I came to know Sieve of Atkin is the fastest algorithm to calculate prime numbers till the given integer. I am able to understand the sieve of Eratosthenes from wikipedia page but i am not able to ...
1
vote
4answers
414 views
Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N?
I need to write a program in C++ that finds all primes up to 2^32. I used a Sieve of Eratosthenes with multiple threads, but it only worked well up to about 10 million. After that it just takes too ...
3
votes
2answers
446 views
Erdős and the limiting ratio of consecutive prime numbers
The following is a piece of math lore from the late forties, which was described in an Intelligencer article entitled "The Elementary Proof of the Prime Number Theorem". It reads:
Turán, who was ...
1
vote
1answer
264 views
Quadratic forms and prime numbers in the sieve of Atkin
I'm studying the theorems used in the paper which explains how the sieve of Atkin works, but I cannot understand a point.
For example, in the paper linked above, theorem 6.2 on page 1028 says that if ...
4
votes
1answer
966 views
Understanding the Sieve of Atkin
I'm attempting to construct a program (in C++) that will count the prime factors of a given number for a Project Euler problem using the Sieve of Atkin, but I'm having trouble understanding a few ...
7
votes
1answer
187 views
primegaps w.r.t. the m first primes / jacobsthal's function
Maybe I don't see the obvious here; but well.
I looked at an old discussion concerning prime gaps. I now tried to ask a somehow opposite way:
Assume the set $\small P(m)$ of first m primes $\small ...
2
votes
4answers
494 views
Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved?
Why in Sieve of Erastothenes of $N$ number you need to check and cross out numbers up to $\sqrt{N}$? How it's proved?
For example if $N = 20$:
with $2$ we cross out:
...
2
votes
2answers
96 views
Estimating number of crossings for Erastothenes' Sieve
In this paper (2.1) I need to understand the formula for the total number of operations: $$\sum_{i=1}^{\pi(\sqrt n)}\frac{n}{p_i} \approx n\ln \ln n + O(n)$$ On a sidenote, since we're only checking ...
9
votes
2answers
315 views
Gaussian Primes
I need to adapt the Sieve of Eratosthenes for the usual integers to find all Gaussian primes with norm less than a specific limit. How to apply it to finding all Gaussian primes with norm less than ...
7
votes
2answers
484 views
Accuracy of approximation to inclusion-exclusion formula in prime sieve
This thing came up in a combinatorics course I am taking.
Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...
