# Tagged Questions

66 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 ...
17 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 ...
46 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. ...
30 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 ...
36 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 ...
48 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?
181 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...)
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 ... 1answer 133 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 ... 0answers 54 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 ... 0answers 93 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 ... 0answers 66 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 \log (N)$$where j(N) is the Jacobsthal function. I am very interested ... 1answer 104 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 ... 0answers 83 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 ... 2answers 2k 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 ... 1answer 89 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 ... 2answers 49 views ### At what rate are composites removed in a set after each prime multiple is cancelled out? I was looking at sieves today, mainly sieving for primes and I noticed a pattern type thing. As I crossed out primes in a small set, the number of composites that were crossed out decreased. I haven't ... 0answers 328 views ### Confusing proof of brun's theorem? I read Brun's proof of Brun's theorem here : http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f110.image (and the following pages) and here http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f138.image ... 1answer 125 views ### What happened to the Mertens constant in the strong prime twins conjecture ?? To estimate the amount of primes in an interval \left(2,x\right) one might naively sieve by computing  x \left(1-\dfrac{1}{2}\right)\left(1-\dfrac{1}{3}\right)...\left(1-\dfrac{1}{p_i}\right) ... 1answer 185 views ### Is this the way to estimate the amount of lucky twins? To estimate the amount of prime twins between 3 and x we just take x \prod_{p}(1-2/p) where p runs over the primes between 3 and \sqrt x. Lucky numbers are similar to prime numbers. Does ... 1answer 236 views ### How does sieve that Chen used to prove Chen's theorem work? In the Number Theory for Computing, Song Y. Yan states that Chen used "complicated arguments based on sieve method", when proving what is now called Chen's theorem. How does this sieve work? Does it ... 1answer 53 views ### Quick way to iterate multiples of a prime N that are not multiples of primes X, Y, Z, …? Is there a way to quickly iterate multiples of some prime N while avoiding multiples of blacklisted primes X, Y, Z, ...? By quickly I mean is there a faster way than: Increment current ... 2answers 217 views ### “Dirichlet's theorem” on pairs of consecutive primes The number of primes in each of the \phi(n) residue classes relatively prime to n are known to occur with asymptotically equal frequency (following from the proof of the Prime Number Theorem). ... 0answers 219 views ### Question about recursive defined functions. This question is about counting functions. With counting functions F I mean functions from the positive integers to the positive integers that are strictly nondecreasing and can grow no faster than ... 1answer 134 views ### On the probability that  2x^2 + 1  is prime (quadratic residue) I tried to compute the multiplicative inverse of the probability that  2 x^2 +1  is prime. (I'm aware that proving there are infinitely many such primes is not done yet, but let's ignore that for ... 0answers 60 views ### sum over prime index done by a weird sieve? As you might have noticed i considered in 2 previous questions sums of the form f(p_i x) where the sum is over the primes p_i ( between some integer bounds : a \leqslant p_i \leqslant b ) , x ... 0answers 162 views ### How many co-primes are there for a big integer N over a specified interval? How many co-primes are there for a big integer N over a specified interval ? bounds of N are [1,10^9] and the interval is [a,b] where (1\leq a\leq b \leq 10 ^{15}) and there are 100 ... 1answer 189 views ### Numbering primes within a range.$$n\ln n + n\ln\ln n−n < p_n < n\ln n+n\ln\ln n \mbox{ for } n\geq 6$$This is the range where the n-th prime must lie. However sieving within this range generates a large number of primes. ... 1answer 219 views ### How to select the values X and Y in the Sieve Of Atkin Algorithm I came to know Sieve of Atkin is the fastest algorithm to calculate prime numbers till the given integer. I am able to understand the sieve of Eratosthenes from wikipedia page but i am not able to ... 4answers 1k views ### Is it a bad idea to use a Sieve of Eratosthenes to find all primes up to very large N? I need to write a program in C++ that finds all primes up to 2^32. I used a Sieve of Eratosthenes with multiple threads, but it only worked well up to about 10 million. After that it just takes too ... 2answers 778 views ### Erdős and the limiting ratio of consecutive prime numbers The following is a piece of math lore from the late forties, which was described in an Intelligencer article entitled "The Elementary Proof of the Prime Number Theorem". It reads: Turán, who was ... 1answer 362 views ### Quadratic forms and prime numbers in the sieve of Atkin I'm studying the theorems used in the paper which explains how the sieve of Atkin works, but I cannot understand a point. For example, in the paper linked above, theorem 6.2 on page 1028 says that if ... 1answer 3k views ### Understanding the Sieve of Atkin I'm attempting to construct a program (in C++) that will count the prime factors of a given number for a Project Euler problem using the Sieve of Atkin, but I'm having trouble understanding a few ... 1answer 255 views ### primegaps w.r.t. the m first primes / jacobsthal's function Maybe I don't see the obvious here; but well. I looked at an old discussion concerning prime gaps. I now tried to ask a somehow opposite way: Assume the set \small P(m) of first m primes \small ... 4answers 526 views ### Why in Sieve of Erastothenes of N number you need to check and cross out numbers up to \sqrt{N}? How it's proved? Why in Sieve of Erastothenes of N number you need to check and cross out numbers up to \sqrt{N}? How it's proved? For example if N = 20: with 2 we cross out: ... 2answers 117 views ### Estimating number of crossings for Erastothenes' Sieve In this paper (2.1) I need to understand the formula for the total number of operations:$$\sum_{i=1}^{\pi(\sqrt n)}\frac{n}{p_i} \approx n\ln \ln n + O(n) On a sidenote, since we're only checking ...
This thing came up in a combinatorics course I am taking. Choose a fixed set of primes $p_1,p_2,\dots,p_k$ and let $A_n$ be number of integers in $\{1,2,\dots,n\}$ which are not divisible by any of ...