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.
2
votes
1answer
36 views
RSA - Quadratic Sieve - Relation Building - How to choose $b$ in $F(b)$?
On p153 of Hoffstein Pipher & Silverman's book "Intro. to Mathematical Cryptography", the list of numbers:
$$F(a),F(a+1),F(a+2),...,F(b)$$
is stated. Where $N$ is number to be factored, $F(T)=...
1
vote
0answers
36 views
Does this behavior of simple sieves have a name?
The sieve of Eratosthanes sequentially identifies primes by using smaller known primes to discard numbers from a list, eventually leaving behind only other primes. At the nth step, we use $p_n$ and ...
0
votes
0answers
53 views
Maynard-Tao vs GPY sieve weights for bounded gaps between primes
I'm trying to understand why the Maynard-Tao weights allow one to obtain bounded gaps between primes whereas GPY fail
The usual response is the additional flexibility of allowing the sieve weights to ...
2
votes
0answers
32 views
Find minimum GCD of a pair of elements in an array
Given an list of elements, I have to find the MINIMUM GCD possible
between any two pairs of the array in least time complexity.
Example
Input
list=[7,3,14,9,6]
...
1
vote
1answer
24 views
In the rational Sieve method why does n = gcd(a-b,n)×gcd(a+b,n) exactly?
As a quick notation explanation of the basic rational sieve method, a set of primes $P$ that are coprime to a number $n$ tested for primality are chosen randomly as follows(from wikipedia):
Suppose ...
0
votes
1answer
35 views
Is or can Brun's twin prime theorem be generalized to a sum over all primes differing by less than a fixed gap?
With Zhang's theorem, and further work by others, if I understand it aright, there are infinitely many primes with a gap of less than or equal to 680. So, working from the opposite direction, it would ...
1
vote
1answer
32 views
Number of integers coprime to a given integer $q$ in some range $[x, x+y]$
I am asked to show that for $1 \leq x,y$ and an integer $q$, we have:
$S(x,x+y,q) = |\{x < n \leq x + y \mid n \text{ is comprime to } q\}| = \frac{\phi(q)y}{q} + O(2^{\omega(q)})$, where:
$\...
1
vote
0answers
27 views
Has such a variant of the Möbius function been used in sieve methods?
Let $ S $ be a finite subset of the primes and let $ \mu_{S} $ the multiplicative arithmetic function defined by $ \mu_{S}(p)=-1_{p\not\in S} $ for all prime $ p $. Has any such mock Möbius ...
0
votes
0answers
18 views
Approximate the amount of zeros of Mertens function in interval.
First of all i know that there are two simillar questions:
Approximate how the Numbers $n$ such that Mertens' function is zero grow.
Numbers $n$ such that Mertens' function is zero.
But i ...
0
votes
0answers
15 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$ ...
3
votes
1answer
95 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
104 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
39 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
36 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)$...
3
votes
3answers
269 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
47 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
64 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
35 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
44 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
184 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
61 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
90 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
32 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
57 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
64 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
36 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
34 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
43 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
66 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
102 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 ...
1
vote
1answer
131 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
767 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
148 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 ...
2
votes
2answers
64 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
239 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
496 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
67 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}{...
3
votes
0answers
28 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
320 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
51 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
173 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
39 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
144 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
589 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
62 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
34 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
22 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 ...
