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

1
vote
1answer
20 views

Generate Sieve of Eratosthenes without “sieve” (generate prime set in interval)

How do I generate a list of primes based on the Sieve of Eratosthenes? I mean by excluding the divisible numbers beforehand, which is tricky for large numbers. I am an number theory amateur, but was ...
0
votes
0answers
8 views

Approximating $L_n[1/3, 1.92]$ for GNFS

Approximating the RHS of $T(n) = L_n[1/3, 1.92]$ Perhaps related to this earlier question on the cost of running the GNFS, I am looking for an approximation for solving equations of this form, when $...
1
vote
0answers
20 views

There are at least: $\big\lfloor\sqrt{p_{n}}\big\rfloor(p_{n}-1)-|p_{n}-2n|+1$, primes less than $p_{n}^{2}$, where $p_{n}$ is the $n$-th prime?

There are at least: $\big\lfloor\sqrt{p_{n}}\big\rfloor(p_{n}-1)-|p_{n}-2n|+1$, primes less than $p_{n}^{2}$, where $p_{n}$ is the $n$-th prime? Is this true or false? If true, how does one prove it?...
1
vote
0answers
61 views

Is this a new twin prime sieve method? Any information or comments is very appreciated.

I'm studying the twin prime numbers. Instead of sieving prime numbers, I found this method to sieve $\{x: x \neq \pm 1 \text{( mod $p$)}, x \in \mathbb{N}, p \le p_i\}$, so that $(x-1,x+1)$ will be ...
1
vote
0answers
37 views

Can you share some information to help study this unified sieve function for prime, twin prime and Goldbach sums of $2n$?

Let $p_i$ be the $i^{th}$ prime number. For Goldbach sums of $2n$, let $p_i$ be the largest prime less than $\sqrt{2n}$, define $$ P(p_i,n,x)=\sum_{p\le{p_i}}\frac{c_p}{p}\left(1+2\sum_{k=1}^{p-1}(1-\...
1
vote
0answers
42 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 $...
5
votes
2answers
100 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} \prod_{p\mid\alpha}\left(1-\...
4
votes
1answer
130 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
17 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
67 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
14 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
16 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
94 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
93 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
58 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
66 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
89 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 ...
8
votes
4answers
172 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
113 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
50 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
38 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
24 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
91 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
54 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
58 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
38 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
123 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
96 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.$$ $\pi(x)$...
3
votes
1answer
114 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
73 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
117 views

Factorizable huge semiprime

I'm trying to understand how the number decimal The correct decimal number is: ...
3
votes
2answers
134 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
71 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
80 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
95 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 $$-F\left(-x\right):=1+2\left(\...
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 + 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
84 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
87 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
48 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
592 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 $...