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.
0
votes
0answers
13 views
How do we determine the roughness of estimates in number theory?
The question came to me when I was reading a book where a proof of Brun's theorem was given, and was followed by this exercise:
Give an upper bound for the number of primes of the form $n^2+1$ ...
4
votes
1answer
77 views
Improved sieve for primes and prime twins?
Suppose we want to estimate the number of primes between $x$ and its square root, say for example between $10$ and $100$ with a sieve.
There are $90 $ numbers so we estimate :
$\pi(10,100) = 90(1-1/...
4
votes
2answers
86 views
Finding $p$ such that $pn \pm 1$ is prime for a fixed $n$
I want to find a prime $p$ such that $pn \pm 1$ is prime for some fixed $n$.
Examples of $n$ are $1683$ or $99617$. Any $p$ will do, it doesn't need to be the smallest possible value.
I have tried ...
0
votes
0answers
33 views
a question about the notation in the book “Opera de Cribro”
When I study the book "Opera De Cribro" by John Friedlander, Henryk Iwaniec-(2010), in Sections 1.2 and 1.3, I confused with notation used there. In page 3 it is defined:
$$\cal{A} = (a_n) , n\le x$$,...
0
votes
1answer
28 views
How correct an estimate for twin primes obtained from the Rosser-Iwaniec sieve and Prime number theorem for arithmetic progressions could be?
Let $P$ be the set of primes $p$, $x \geq D \geq z^2 \geq 2$, and let $A⊂[1,x]$ be a set of integers. Suppose $A_{d}=|A| \frac{v(d)}{d}+R_{d}$ for square free d with $v$ being multiplicative and $v(p)$...
1
vote
2answers
73 views
How exactly does wheel factorization work and what is it used for?
I would like to learn how to use wheel factorization but am having trouble understanding it. I tried reading the wikipedia article but found it confusing (even the talk page says it's a mess). What ...
2
votes
0answers
32 views
Prove $π(x+y)- π(x) \ll \frac y{\log (\log (y))}$ using Legendre sieve such that $10 ≤ y ≤ x$
How to prove $$π(x+y)- π(x) \ll \frac y{\log (\log (y))}$$ using Legendre sieve such that $10 ≤ y ≤ x$?
0
votes
1answer
50 views
Fast sieve for sum of Euler totient values (phi) values from 1 to 'n'
I wanted to optimize the sieve method for computing Euler's Totient (Phi) values from 1 to n. Basically, i came across this Quora comment :https://www.quora.com/What-is-the-fastest-function-to-...
2
votes
1answer
33 views
Can you determine small primes from larger primes?
Suppose you are given the primes in the range $[n,n^2]$. Is there a known way to effectively reconstruct the primes less than $n$? Ideally, something that takes less calculation than figuring them out ...
1
vote
0answers
42 views
A question about the rationality of Hurwitz Zeta functions.
I'm checking over some of my work from studying prime numbers, and I found where I used the Hurwitz Zeta function $$\zeta(s,\alpha)_{\alpha \in [0,1)} = \sum_{n\in \mathbb{N}} \frac{1}{(n+\alpha)^s}, ...
0
votes
0answers
15 views
Question related to \left\{p\leq x| \ \text{the proprities $A_1(p), A_2(p),\ldots$ hold}\right\}.
It is not difficult to see that
$$\#\left\{p\leq x| \ \text{$p$ is prime and the proprities $A_1(p), A_2(p),\ldots, A_k(p)$ hold}\right\}<\frac{x}{\log x}.$$
Ma questions are:
$$1) \#\left\{p\leq x|...
2
votes
1answer
163 views
Relation between Buchstab identity and prime number theorem
Using the estimate $$\pi(x)=\frac{x}{\log x}+O\left(\frac{x}{\log^2 x}\right)$$ prove that, for $x^{1/3}<y\le x^{1/2}$ and for $u=\log x/\log y$,
$$\Phi(x,y)=\frac{x}{\log x}\{1+\log (u-1)\}+O\...
2
votes
1answer
54 views
Prove that $\Phi(x,y)=\pi(x)-\pi(y)+1$
Define, $\displaystyle \Phi(x,y)=\sum_{n\le x, \substack\\ p|n\implies p>y }1$. Prove that if $\sqrt x <y\le x$ then, $\Phi(x,y)=\pi(x)-\pi(y)+1$, where $\pi(x)$ denotes the number of primes ...
1
vote
0answers
79 views
Compact form of $\pi_k(x)$
Let, $\pi_k(x)$ denote the number of $n\le x$ with $k$-prime factors (not necessarily distinct). Using the Sieve of Eratostheness, show that, $$\pi_k(x) \le \frac{x(A\log \log x+B)^k}{k! \log x}.$$ ...
1
vote
0answers
28 views
Partial summation of character $\chi \pmod{p}$?
In Ch. 8 (p. 142) of the Opera de Cribro (Friedlander, Iwaniec) it is written:
To this end we apply the sieve to remove from each $p$ in a set $\mathcal{P}$ residue classes which are not squares ...
2
votes
0answers
53 views
The sieve formula choosen in Zhang's breakthrough work in Twin Prime conjecture
In the breakthrough work of the proof of weak twin prime conjecture, Goldstone, Pintz and Yildirim as well as Zhang use the following modified Selberg sieve:
$v=\lambda^2$
where $\lambda(n)$takes ...
3
votes
1answer
61 views
Asymptotic relation between $\Phi(x,z)$ and $\Psi(x,z)$
Define, $\Phi(x,z):=\#\{n\le x: n \text{ is not divisible by any prime }<z\}$
$\Psi(x,z):=\#\{n\le x:\text{ if }p|n \text{ then }p<z\}$.
Prove that, $\displaystyle \Phi(x,z)=x\sum_{d|P_z,d\...
0
votes
0answers
27 views
Fibonacci sieve and factoring
I want to know different sieve techniques for Fibonacci numbers and how they works. In wikipedia it is written only that the Cassinie's identity are useful in setting up the special number field sieve ...
0
votes
0answers
31 views
A question on Selberg sieve
In many papers, the Selberg sieve has a simple form with factors $λ_d×\log(d)$ for $d\mid n$ in any summand in its expression, and if we want to truncate it in scale $R$, it has a factor $\log(R/d)$. ...
1
vote
0answers
27 views
Upper bound of $ \sum_{n\leq x}f(n) $ where $ f(n)=\sum_{r=1}^{n-1}\mu(r)\mu(n-r) $
$Cx^2$ is a trivial bound by just counting the total number of terms in these sums. From here I have attempted to use $$ \sum_{n\leq x} \mid \mu(n) \mid =\frac{6}{\pi^2}x(1+o(1)) \text{, } x \to \...
0
votes
2answers
59 views
What is the set of numbers generated by this sieve called?
The sieve of Eratosthenes' characterizes the set of prime numbers by sifting composite numbers from the set of natural numbers $> 2$.
Say we use the same sieve to instead sift all perfect powers ...
1
vote
0answers
101 views
Infinitely many primes $p$ such that $\frac{p-1}{2}$ is a product of two primes
The second answer to this question says the following:
"I believe that sieve methods (in particular methods similar to Chen's result on "almost" Goldbach and twin primes) should give infinitely ...
0
votes
0answers
50 views
How long would it take a computer to check that a number is not divisible by any 20-digit prime?
If a computer could perform 10^18 division operations per second, how long would it take to check that a given number is not divisible by any 20-digit prime?
So I think I'm supposed to use trial ...
2
votes
1answer
124 views
Generalization of Opperman's Conjecture
Does this conjecture have a name? What about a counterexample?:
$$ \forall n,k \in \mathbb{N}, k \gt 1, \exists d \in (kn-n,kn] \text{ s.t. } d \perp n! $$
An equivalent statement is this:
Take a ...
11
votes
3answers
749 views
How to tell if a particular number will survive in this sieve?
I was asked this in an interview.
We have people numbered from one to infinity: $$1, 2, 3, 4, 5, 6, 7, 8, \dotsc\,.$$ In first pass every 2nd person is killed, so we have $$1, 3, 5, 7, 9, 11,\...
3
votes
0answers
88 views
In the General Number Field Sieve, can we estimate the size of the matrix in terms of the number being factored?
One of the last steps of GNFS is to solve a large matrix-vector equation (usually using the Block Lanczos algorithm or the Block Wiedemann algorithm). The matrix for the most recent RSA number ...
3
votes
2answers
56 views
Probability that a random number avoids a set of prime divisors
Let $P=\{p_1,\ldots, p_k\}$ be a set of primes.
For a natural number $n$,
define $\mu_P(n)$ as the probability that a random number
selected from $\mathbb{N}_{\le n} = \{1,2,\ldots,n\}$
has no ...
0
votes
1answer
164 views
Finding Prime Factors of a number in $\log(n)$
Only Strategy I am aware of for finding factors efficiently is sieve of eratosthenes but from sieve I first have to pre-compute the prime numbers less than than $\sqrt{n}$. I want to skip this ...
0
votes
3answers
352 views
Modified sieve to find count all the divisors from 1 to n in o(n) time
I trying to solve a problem that involves finding the number that has the maximum factors from 1 to $N$ where $N = 10^7$ in just under 2 seconds.
I have implemented a sort of "sieve" that starts from ...
1
vote
0answers
58 views
Asymptotic relations of $x$ and $x/(\log\log x)$
This problem is from Problem in Analytic Number theory by M.Ram Murty (Page no. 128).\
$\pi(x,z) = \# (n \leq x: n \ \text{is not divisible by any prime} \ p < z)$
We have, $\pi(x,z) \ll \frac{x}{...
4
votes
0answers
25 views
Bounding the number of semiprimes of the form $2p\pm1$
I would like an upper bound on the number of semiprimes of the form $2p+1$ (and the same with $2p-1$), where $p$ is prime. Is there a general result I can apply? I have not studied sieve theory (but ...
1
vote
3answers
204 views
Sieve of Eratosthenes : why $\sqrt n$ work?
I have a question about Sieve of Eratosthenes,
I refer at the "simply version" :
If I have an $\boldsymbol{n}$ and I want the prime numbers up to n,
I search and delete multiply up to $ \...
0
votes
1answer
50 views
A “ triple-sum-free ” sequence?
Consider the strictly increasing integer sequence $f(n)$ defined as :
$$f(1) = 1$$
$ M $ is in the list If and only if $M$ is not of the form $ f(a) + f(b) + f(c) $ for Some integers $a,b,c > 0$.
...
6
votes
0answers
163 views
Prove that every integer greater than 1 is sum of square and squarefree.
I tried to put some sieve method on this. Here, we denote the classic squarefree sieve function $\sum_{d^2|a}\mu(d)$
(notice that if $a$ is squarefree, the value is 1, and if not squarefree, the value ...
1
vote
0answers
35 views
How to relate the two versions of Bombieri-Vinogradov theorem to one another?
When searching for the Bombieri-Vinogradov theorem on the internet, it appears under different forms, but with some minor differences there are essentially these two:
$$
\sum_{q\leq Q}\max_{(a,q)=1}\...
4
votes
0answers
121 views
What should I do if I wrote an algorithm faster than the Sieve of Atkin?
I have been having fun with prime numbers. I sat down and, following a hunch and after a few weeks of headbanging against the wall, I was able to write an algorithm that, at least on my local, ...
1
vote
1answer
35 views
Why does this strategy sieve out composites without factors $2,3$?
Take
$$
3 + 2 = 5 \\
3 + 4 = 7 \\
5 + 6 = 11 \\
5 + 8 = 13 \\
7 + 10 = 17 \\
7 + 12 = 19 \\
9 + 14 = 23 \\
9 + 16 = 25 \\
\cdots
$$
I'm having trouble writing down what the pattern is to start with. ...
1
vote
3answers
459 views
Prime Factorization using The Sieve of Eratosthenes
I understand how the Sieve of Eratosthenes works for finding all primes less than a number n (start at 2 and cross out multiples and move on to next uncrossed out number and repeat etc.), but is there ...
2
votes
2answers
61 views
Why is $12$ special in relation to $6n\pm1$?
If you take the numbers of the form $6n\pm1$ and arrange them into $12$ columns, i.e., $$5,7,11,13,17,19,23,25,29,35,37,41,\ldots,$$
all the columns have digital roots that are the same throughout ...
1
vote
2answers
33 views
Unable to understand the meaning of $\mathcal{B\pmod t}$
My Question : What is the meaning(/definition) of the image of $\mathcal{B\pmod t}$ ? First of all what is the meaning of $\mathcal{B\pmod t}$ ?
2
votes
0answers
21 views
What is the “sieve and limiting process” technique? (From a paper of Ërdos on polynomials with power-free values)
Let $f$ be a primitive integral polynomial of degree $d$. In Arithmetical properties of polynomials, Ërdos says (page 417) that the integers $n$ for which $f(n)$ is $d$-th power free have positive ...
0
votes
1answer
53 views
Little clarification on Gallagher's Larger Sieve
Edit :
After multiplication the inequality by $\Lambda (t)$ and then sum over $t\in \mathscr{T}$ we get ,
$\displaystyle \sum_{t\in \mathscr{T}}\frac{(\#B)^2}{u(t)}\Lambda(t)\le (\#B)\sum_{t\in \...
0
votes
1answer
37 views
Characteristic function of a divisibility sieve (like Eratosthenes) is periodic for finite sieving set.
Let $a_n \in \Bbb{R}, n \in \Bbb{Z}$ be a bi-infinite sequence. For any set $T\subset \Bbb{Z}$, define a divisibility sieve $\widehat{T}$ to be a transformation of the sequence that deletes every ...
0
votes
0answers
32 views
Estimating an error term when counting primes
Let $f(x,p) = $ the number of integers $i$ where $0 < i \le x$ and lpf($i)>p$ where lpf($i)$ is the least prime factor of $i$.
I believe that the exact answer is captured by this:
$$f(x,p) = \...
1
vote
2answers
410 views
New lower limit for the number of twin primes $\pi_2(n)$
While trying to find a lower limit for the number of twin primes I noticed the problem of having to compensate for duplicates. Once I overcame this problem the duplicates of the duplicates became a ...
2
votes
1answer
180 views
Is this a new twin prime sieve?
I developed a twin prime sieve and would like to know if there is a well known equivalent. Pardon my lack of proper notation. Feedback on how to format this properly would also be appreciated.
...
1
vote
1answer
18 views
Can sieve operations be compared in this way?
Suppose we consider the set of integers in the interval $I_n=[2^n+1,2^{n+1}]$, and we pare this set down in two similar ways with the sieves $ab+a+b=k$ and $2ab+a+b=k$ for $k\in I_n$. These sieves ...
2
votes
1answer
87 views
A proof for the generalizated Brun's theorem about the summability of the reciprocal of twin primes
Please, can anyone prove or indicate a paper or book where it is proved a generalization for the Brun's theorem? That is: the sequence $(1/p_n)$ is summable, where
$p_{n+1}-p_{n}=k$, (for some $k\geq2$...
1
vote
2answers
51 views
Understanding Lemma 2.1 in P. Erdos and I. Z. Ruzsa's "On the Small Sieve. I, Sifting by Primes.
I am reading a paper of P. Erdos and I. Z. Ruzsa and I had a question on Lemma 2.1.
Let $A$ be a set of natural numbers.
Let $B$ denote the set of natural numbers divisible by no element of $A$.
...
3
votes
1answer
199 views
Prime Counting Function from the Sieve of Eratosthenes
This may seem a very simple question, but I did not find any answer for it on the Internet.
It is known that the Sieve of Erastothenes can be analytically stated as:
$$\pi(x)-\pi(x^{\frac{1}{2}})+1=\...
