Sieve theory deals with number theoretic sieves, and sifted sets. E.g. the Sieve of Eratosthenes, Brun sieve, and other modern sives.

learn more… | top users | synonyms

0
votes
0answers
11 views

Can you get the average order of $ \left( 1+|\mu(n)| \right)^{M(n)} $, where $\mu(n)$ and $M(n)$ are the Möbius and Mertens functions, respectively

When yesterday I was interested in do a little study about the arithmetic function $$f(n)=\left( 1+|\mu(n)| \right)^{M(n)},$$ defined for integers $n\geq 1$, which $\mu(n)$ is the Möbius function and ...
3
votes
1answer
69 views

Sum of products of $(1 - 1/p)$

Let $\pi(n)$ denote the number of primes not greater than $n$, and $p_k$ the $k$th prime, so that $p_{\pi(n)}$ denotes the largest prime not greater than $n$. I'm interested in the value of the ...
0
votes
1answer
21 views

Theorem precedding Schnirelmann's Theorem

An Introduction to Sieve Methods and their applications has the following Theorem 6.3.4 $$|\lbrace p\leq x:\;|p+\alpha| \text{ is prime} \rbrace|<\frac{cx}{(\log x)^2} ...
3
votes
1answer
122 views

Can we replace the upper limit condition of the Sieve of Eratosthenes $\sqrt{n}$ with the value $\sqrt{p}$ where $p$ is the last sieved prime $\lt n$?

By chance I stumbled upon the OEIS list A033677 of the smallest divisor of $n$ greater or equal to $\sqrt{n}$. Roughly speaking if we use the classic enhanced sieve of Eratosthenes, $\sqrt{n}$ is the ...
0
votes
1answer
16 views

Classes of exponent

I found this terminology in an a paper (link) and did not understand it's meaning. Here is the set of lines that I am talking about: For each prime $p \le g$, we remove all residue classes $\mod p$ ...
4
votes
1answer
66 views

Lower bound on $\pi(x)$

The book I am working through uses the bound $\pi(x)>\frac{x}{ \log x}$ without proof. Is it possible to prove this in a simple way using Sieve methods?
0
votes
0answers
11 views

Effective algorithmic calculation of gcd determinant

This is a contest problem taken from here: http://www.e-olymp.com/en/problems/3243 I need to calculate the following determinant: $$ D(1,\dots,n)=\begin{vmatrix} (1,1) & \cdots & (1,k) & ...
1
vote
0answers
14 views

Connection between Brun's Sieve and the Sieve of Eratosthenes

I have read in a couple of places that the above mentioned sieves are connected in some way. In particular, Brun's Sieve builds upon that of Eratosthenes. I do not see why this is the case and hope ...
2
votes
0answers
32 views

Finite sequence created by reducing $n$ with each prime under $n$ ends in $0$?

Given $n$ a fixed integer we constuct the following sequence: $a_0=n$, $a_i=\lfloor \frac{a_{i-1}(p_i-1)}{p_i}\rfloor$. For what values of $n$ do we have $a_{\pi(n)}=0$? Computer calculation shows ...
6
votes
0answers
87 views

Twin-prime sieve

My question concerns the following sieve (call it S), which was an exercise in applying some elementary aspects of Brun's sieve while reading Halberstam's text. Using the Chinese Remainder theorem ...
1
vote
2answers
91 views

Primes and 32 - where did this pattern come from?

If we position all the natural numbers into a 'periodic table' with the period equal to $32$, we get the following pattern for primes. The primes are colored according to their last digit. I did not ...
0
votes
1answer
57 views

$2^k+3$ : Primality Brute Forcing Theory Below The Square Root

I'm testing a theory of brute forcing $2^k+3$. I've tried to test $(2^k)+3$ where $k=84$ but my computer just takes too long... Java takes too long too.. It's pretty stupid to assume 83 tests makes ...
1
vote
1answer
63 views

How long does the General Number Field Sieve actually take?

According to the researchers who cracked it, RSA-768 took an equivalent 2000 years to factor on a 2.2GHz single-core computer. Using the complexity equation for the General Number Field Sieve with ...
0
votes
0answers
17 views

Prime Counting: In truncation rule #2 mentioned in an AMS.org article, I'm unclear how “special leaves” work?

I'm reading through an AMS.org article on prime counting. The article covers the history of prime counting and focuses on improvements to the Meissel-Lehmer method. It is the improvement on page ...
3
votes
0answers
46 views

Unclear on how a sieve function is being generalized into a function that uses the möbius function

I am reading through an AMS.org article on prime counting. Let $\Phi(x,b)$ be the number of integers $i$ where $1 \le i \le x$ and $\gcd(i,p_b\#)=1$ where $p_b$ is the $b$th prime and $p_b\#$ is the ...
3
votes
1answer
86 views

Patterns in Sieve of Eratosthenes

Consider an integer sequence $$0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0...$$ Each term denotes the number of times the corresponding natural number, starting from $0$, was hit by ...
7
votes
3answers
140 views

Computing the first $n$ values of the Liouville function in linear time

Is it possible to compute the first $n$ values of the Liouville function in linear time? Since we need to output $n$ values we clearly cannot do better than linear time, but the best I can figure out ...
9
votes
2answers
108 views

Prove there are infinitely many primes in $\mathbb{Z}[i]$

I saw a proof online there are infinitely many primes in $\mathbb{Z}$. The Euler product let's us factor the harmonic series: $$ \prod \left( 1 - \frac{1}{p} \right) = \sum \frac{1}{n}$$ I wonder ...
0
votes
1answer
49 views

Current Research Using Sieve Methods

I've been learning various basics of Sieve Methods in Analytic Number Theory, and I'm wondering what are some uses of these methods in current research? Not famous, unsolved problems, but areas of ...
1
vote
1answer
37 views

Quadratic Sieve Algorithm: Why is $(x − \lfloor \sqrt{n} \rfloor)^2 ≡ n ($mod $p)$?

If someone here understands the Quadratic Sieve Algorithm, I'm having trouble understanding why every prime $p$ in the factor base needs to a prime such that $n$ is a quadratic residue modulo $p$. It ...
0
votes
1answer
23 views

If $x\not\equiv\pm y ($mod$n)$ but $x^2 \equiv y^2($mod $n)$, why is gcd$(x-y, n)$ not equal to $1$ or $n$?

Let's say I have an integer $n$ and two integers $y$ and $x$ such that $x\not\equiv\pm y ($mod$n)$ but $x^2 \equiv y^2($mod $n)$ This would of course imply that $(x-y)(x+y) \equiv 0 ($mod $n)$. ...
4
votes
2answers
79 views

Fractals with Moduli in Pascal's Triangle

I'm working through a problem for my graduate math class and am hitting a wall. Here's the problem: For the first 10 lines of Pascal's Triangle, replace the odd numbers by black squares and the even ...
2
votes
2answers
48 views

Sieve of Eratosthenes Refinement

From Wikipedia: Create a list of consecutive integers from $2$ through $n$: $(2, 3, 4, ..., n)$. Initially, let $p$ equal $2$, the smallest prime number. Starting from $2p$, enumerate the ...
2
votes
1answer
49 views

Is this proof of the Eratosthenes sieve correct?

In particular, we want to show that composite numbers all have a prime factor less or equal to $\sqrt n$. We take a positive composite number n, with a prime factorization $n = p_1 \cdots p_r$. For ...
4
votes
1answer
40 views

Integers with a divisor in a given interval

Please bear with me, I have a notation question. In Kevin Ford's paper with the above title, the following statement occurs in Theorem T1, p. 369: If $2 ≤ y ≤ z ≤ x$, then $$H(x, y, z) = x\left(1 + ...
1
vote
0answers
21 views

Selberg's sieve: how to evaluate the main part of the asymptotic expansion?

I'm currently reading the presentation of Selberg's sieve by Gelfond & Linnik, Elementary methods in the elementary theory of numbers. I have difficulties in evaluating the sum $$\sum_{d \leq ...
2
votes
0answers
47 views

Where to find Brun's original combinatoric treatment of Brun Sieve?

I tried to understand Brun's original combinatoric treatment of Brun Sieve. (Unfortunately, I do not understand German), so I could not read Brun's original paper as in following: Viggo Brun (1915). ...
1
vote
1answer
35 views

Large Sieve Method for Weird Prime Problem

I've been working on a problem now, but I'm having a difficult time due to my lack of familiarity with sieve methods (this is not a hw problem or anything like that btw) Let $P$ be the set of all ...
2
votes
0answers
99 views

Online lecture Videos on Algebraic or Analytic Number Theory or Sieve Theory [closed]

I found some lectures on youtube but I need something which starts from the basics.Any help will be truly appreciated.
2
votes
2answers
77 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
3
votes
1answer
110 views

Distribution of composite numbers

This question is moved from mathoverflow, there are several excellent answers at mathoverflow which improve my question greatly. For more information, please see the original question posted on ...
1
vote
0answers
72 views

Prime twins and $1 \mod 30$ confusion

Jie Wu improved Brun's theorem and showed that the number of prime twins up to $n$ satisfies for sufficiently large $n$ : $$\pi_2(n) < 4.5 \frac{n}{ln(n)^2} $$ However this confused me while ...
0
votes
1answer
114 views

Factorizable huge semiprime

I'm trying to understand how the number decimal The correct decimal number is: ...
3
votes
2answers
133 views

Can anyone sketch the proof or provide a link that there is always a prime between $n^3$ and $(n+1)^3$

In a recent forum discussion on number theory, it was mentioned that A. E. Ingham had proven that there is always a prime between $n^3$ and $(n+1)^3$. Does anyone know if there is a link available on ...
3
votes
0answers
69 views

parity problems for sieve methods, is it only for Selberg Sieve or for all sieve methods?

It is said that sieve methods have parity problems. Terence Tao gave this "rough" statement of the problem: "Parity problem. If A is a set whose elements are all products of an odd number of primes ...
2
votes
3answers
77 views

Arithmetic functions of particular type

Any there any natural functions real valued single variable that: changes (increases) values only at primes but otherwise stay constant (like a non periodic increasing staircase)? whose increase in ...
5
votes
1answer
93 views

Twin Primes between $n$ and $2n$

Is it theoretically possible for there to always be a twin prime pair between $n$ and $2n$ for all sufficiently large $n$ (assuming of course that there are infinitely many twin primes) or would this ...
1
vote
0answers
47 views

Question about large sieve

I'm studing the large sieve inequality, following the method of Selberg. I'm reading the book "Opera de cribro", by Friedlander and Iwaniec. At page 154 I've found this ...
4
votes
1answer
159 views

Brun's sieve bounds

Working from Halberstam-Richert they state the following bounds \begin{align} S(\mathcal{A}; \mathfrak{P}, z) \leq XW(z)\left(1 + 2 \frac{\lambda^{2b + 1}e^{2\lambda}}{1 - \lambda^2 e^{2 + ...
4
votes
1answer
78 views

Factors of integers of the form $2^n-1$

I came across a problem where i had to tell the number of divisors of $2^i-1$ which are of the form $2^j-1$. I saw many contestants using the fact that if $i$ is divisible by $j$ then $2^i-1$ is ...
1
vote
2answers
79 views

Is the Legendre sieve explicit?

The Wikipedia page for the Legendre sieve... http://en.wikipedia.org/wiki/Legendre_sieve ...says that the Legendre sieve gives upper and lower bounds on the number of primes in a given range. In ...
1
vote
0answers
86 views

Fast algorithm for generating consecutive primes larger than N

I'm looking for a fast algorithm to generate primes larger than a random 4096 bit number $N$. I know about the Sieve of Atkin, but AFAIK it can only be used to find all primes up to a certain limit. ...
1
vote
1answer
85 views

Sizes of Blocks of Consecutive Integers Divisible by at Least One Prime Less than or Equal to $r$.

Let $f(r)$ be the largest integer such that there exists a block of $f(r)$ consecutive integers each divisible by some prime that is less than or equal to $r$. For example, $f(2)=1$ because it is ...
1
vote
0answers
47 views

What is the status of research on primes as an example of general sieve-generated sequences?

I have been interested in treating the prime numbers as a special case of sieve-generated sequences, however they may be defined by different authors. Can someone here give me any information about ...
12
votes
0answers
568 views

How does a Lehmer Sieve work?

http://en.wikipedia.org/wiki/Lehmer_sieve Apparently a Lehmer Sieve was a mechanical device that used chains and pulleys to factor numbers and solve diophantine equations. It once was able to factor ...
0
votes
0answers
56 views

For all prime $\ p > \ 2,\ p=2^x \cdot Ord_p(2)+1$?

For all prime $\ p\ > \ 2,\ p=2^x \cdot Ord_p(2)+1?\ $ Where $\ x \in \mathbb{Z}_{\geq 0}.\ $ Such as $\ Ord_3 (2) = 2, \ 3=2^0 \cdot 2 + 1$. Is there some way to prove this?
0
votes
1answer
231 views

What are some good introductory textbooks on Sieve Theory?

I fail to find a duplicate. If it exists, please give me the link and close the question accordingly. As the title suggests, I am looking for recommendations on introductory books to Sieve Theory. ...
-1
votes
2answers
300 views

Twin Prime Conjecture's Proof [closed]

I've found this article that claims to have a proof of the Twin Prime Conjecture. Can you find any error? (I have some doubts about the last page of the paper...)
0
votes
1answer
51 views

well known sieve?

Incidentally I've shown the following fact. Cancelling from the natural numbers $1$, the even integers, the integers of the form $n^2+2nk$, with $n>1$ odd and $k$ nonnegative, we obtain all (and ...
3
votes
1answer
172 views

Explanation for Terry T. post

I read here that : " If one inserts these inequalities into the Legendre sieve and optimises the parameter, one can improve the upper bound for the number of primes in $[N,2N]$ to $$O \left(\frac{N ...