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
0answers
24 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
45 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
81 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
136 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
92 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
46 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
36 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
21 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)$. ...
3
votes
2answers
65 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
41 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
47 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
39 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 ...
1
vote
0answers
37 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
33 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
80 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
53 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
103 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
68 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
0answers
16 views

An inequality related to Brun's sieve

My question is about the presentation of Brun's sieve by Gelfond & Linnik's Elementary methods in the analytic theory of numbers. The authors denote by $P(\Delta~;~D~;~x~;~a_1p_1b_1, \ldots, ...
0
votes
1answer
111 views

Factorizable huge semiprime

I'm trying to understand how the number decimal The correct decimal number is: ...
3
votes
2answers
131 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 ...
2
votes
0answers
59 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
75 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 ...
4
votes
1answer
85 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
46 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
154 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
67 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
81 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
60 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
45 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
513 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
218 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. ...
0
votes
2answers
277 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
165 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 ...
2
votes
1answer
152 views

Sieving integers

Let $2=p_1,p_2,\cdots ,p_n$ be the first $n$ prime numbers. Suppose $N$ is a natural number and that $A=\{a+1,\cdots, a+N\}$ be a set of $N$ consecutive integers. Let $P_n=p_1\cdot p_2\cdot \cdots ...
0
votes
0answers
66 views

Recommend a good read on prime sieving for primes of the form $x^2 + y^2$

Recommend a good read on prime sieving, which can be applied to sieve primes of the form $x^2 + y^2$ (or $x^2 + ny^2$, if possible). I actually need to find up to a certain limit numbers that are ...
1
vote
1answer
196 views

Sieve for Prime Numbers

I will use some simple arguments on a prime numbers formula that has been deterministically checked by computer. I would like to compare this result with others you already know. The set of all ...
2
votes
1answer
164 views

Can anyone sketch an outline of Iwaniec's proof for the upper bound regarding the Jacobsthal function?

A proof by H. Iwaniec in 'On the problem of Jacobsthal, Demonstratio Math. 11, 225–231, (1978)' shows that: $$j(N) \ll \log^2 (N)$$ where $j(N)$ is the Jacobsthal function. I am very interested in ...
0
votes
1answer
189 views

collatz conjecture $\mod 2^n$ stopping distance

an interesting book Old and new unsolved problems in plane geometry and number theory by Klee/Wagon (1991) includes the Collatz conjecture. on p225 they consider iterates $\mod 2^n$ and state that ...
4
votes
1answer
115 views

Are most numbers of the form $a\cdot b^n+c$ composite?

It seems evident that for $a,b,c$ with $a>0$ and $b>1$ that there are only $o(x)$ primes of the form $a\cdot b^n+c$ with $n\le x.$ Has this been proven? Hooley (Applications of Sieves to the ...
0
votes
0answers
100 views

Is my sieve generalisable?

I was curious about extending Euler's polynomial generator n^2 - n + 41 for n > 41, and looking for the simplest sieves. I examined the gaps between non-primes and found a set of simple sieves of the ...
16
votes
0answers
426 views

Using the Brun Sieve to show very weak approximation to twin prime conjecture

I recently stumbled across MIT OCW for analytic number theory. As a budding number theorist, my ears perked up and I looked through some of the material haphazardly. I don't really know much about ...
3
votes
2answers
8k views

Most efficient algorithm for nth prime, deterministic and probabilistic?

What's the most efficient algorithm for calculating an $nth$ prime, both deterministically and probabilistically? Deterministic Iterate through only odd values, incrementing by $2$. Divide each ...
0
votes
2answers
82 views

Sieve of Erathosthenes - when can I stop crossing out?

Here is an exercise: Show that when finding the primes from 2 to $n$ using the Sieve of Erathosthenes, we can stop crossing out once $p \geq \frac{n}{2}$. Let $p$ be denoted by a star. Suppose ...
5
votes
1answer
107 views

Counting numbers of the form $ai + bj + cij$ and finding related L-series?

Let $a,b,c$ be given nonnegative integers with $gcd(a,b,c)=1$. Consider a given positive integer $n$ and positive integers $i,j$. Let $f_n(a,b,c)$ be the number of distinct solutions to $1<ai + bj ...