**41**

votes

**0**answers

2k views

### the topology of arithmetic progressions of primes

The primary motivation for this question is the following: I would like to extract some topological statistics which capture how arithmetic progressions of prime numbers "fit together" in a manner ...

**18**

votes

**0**answers

1k views

### Permutations of $(Z/pZ)^*$

Let $p$ be a prime integer, and let $(\mathbb Z/p\mathbb Z)^*$ be the set of non-zero elements of $\mathbb Z/p \mathbb Z$.
Denote by $S((\mathbb Z/p \mathbb Z)^*)$ the group of permutations of ...

**14**

votes

**0**answers

824 views

### Small primes attract large primes

I posted a version of this to stackexchange and got 12 up-votes and no answers in somewhat more than a day. Someone in a comment construed it as asking for a lot of novel research including figuring ...

**9**

votes

**0**answers

445 views

### Are the twin primes the only positive double zeros of this real function?

Agno's answer
was extremely helpful.
For $x \in \mathbb{R}, x \ge 1$ define
$$ f(x) = \sin\frac{\pi(\Gamma(x)+1)}{\lfloor x \rfloor}$$
By Wilson's theorem the positive integer zeros of $f(x)$ are ...

**8**

votes

**0**answers

112 views

### Does the given operation on pairs of primes always repeat?

Let $p$ and $q$ be two distinct primes. The set
$$A(p,q) =\{m+n : mp+nq=1 \textrm{ and } m,n \in \mathbb{Z}\}$$
is an arithmetic progression. Its step size $p-q$ is coprime to a fixed $m+n$ because
...

**8**

votes

**0**answers

316 views

### Sieve bound for prime $k$-tuples

Let $d_1<d_2<\dots<d_k$ be integers. Then the number of integers $n\leq x$, such that $n+d_1, n+d_2, \ldots, n+d_k$ are simultaneously prime, is bounded above by
$$
\mathfrak{S}(d_1, \ldots, ...

**8**

votes

**0**answers

530 views

### Would the following conjectures imply $\lim\inf_{n\to\infty}p_{n+k}-p_{n}=O(k\log k)$?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...

**7**

votes

**0**answers

243 views

### Montgomery's conjecture and lower bound on certain Fourier transform.

Recently I have come across the following question, while meditating about Matt Young's answer to this question of mine, explaining the heuristic (or at least, one possible heuristic) behind ...

**7**

votes

**0**answers

476 views

### Two different ways to count Mersenne Primes

Hi there, the motivation for this question is to better understand the heuristics of Mersenne primes, and I was motivated by the recent questions (Mersenne quasi-primes) and (Primes in generalized ...

**6**

votes

**0**answers

241 views

### Twin Primes that are Sophie Germain Primes

Suppose $p$ is a prime such that $p + 2$ is also prime, and nothing else is known about $p$.
Is there any reason to think that this affects the probability that $p$ is also a Sophie Germain prime? ...

**6**

votes

**0**answers

225 views

### Generalizing prime numbers to product-indecomposable objects in toposes

Any object $A$ in any topos decomposes as $A\times1$ and $1\times A$, and in $FinSet$ objects with no other product decompositions are "prime numbers". Is there any extension of the theory of ...

**6**

votes

**0**answers

565 views

### Would the following conjectures imply Cramer's conjecture?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, ...

**6**

votes

**0**answers

452 views

### Any published references for this $O(n)$ time, $O(n^\epsilon)$ space identity for the count of primes?

I would like to know if this identity (or trivial equivalents) for $\pi(n)$, the count of primes, is currently published anywhere.
$D_{0,a}(n) = 1$
$D_{1,a}(n) = \lfloor n\rfloor-a-1 \ \ \ \ \ \ \ \ ...

**6**

votes

**0**answers

334 views

### Primes of the form $x^2+ny^2$ such that when you swap x and y you get another prime

Hello, Im looking at primes of the form $x^2+ny^2$ for $n>1$ where we can swap $x$ and $y$ and get another prime, I have found many such pairs for many values of n, and i wanted to know if there ...

**6**

votes

**0**answers

574 views

### “probabilistic” density of primes?

A certain set $\cal P$ of primes is defined by two assumedly independent conditions:
The first condition on a prime $p$ can be characterized in terms of the type of splitting of $p$ in certain Galois ...

**5**

votes

**0**answers

139 views

### Does the Maynard-Tao Theorem apply to general tuples of linear forms?

In the paper http://arxiv.org/pdf/1311.5319v1.pdf the author states the following theorem, which he attributes to Maynard and Tao.
For any integer $m > 2$, there exists an integer
$k = k(m)$ such ...

**5**

votes

**0**answers

207 views

### Primes for which 2 is a primitive root

I am writing a paper in which I keep referring to primes p for which 2 is a primitive root mod p and so I want to give a name for these primes. Is there a name for these primes in the literature ...

**5**

votes

**0**answers

226 views

### Should I expect to see numbers this smooth?

I have a sequence $N_k$ of numbers whose growth I wish to determine, or at least
approximate nicely. When I look at the ratios of consecutive members,
I find some interesting simplifications ...

**5**

votes

**0**answers

234 views

### $n\varphi(n)\equiv 2\pmod{\sigma(n)}$ as a primality test

It is known from Subbarao, "On two congruences for primality" that $n>22$ is a prime iff $$n\sigma(n)\equiv 2\pmod{\varphi(n)},$$ where $\varphi(n)$ is Euler's function and $\sigma(n)$ is sum of ...

**5**

votes

**0**answers

292 views

### How many ways can a number be Fortunate?

An integer $m$ is Fortunate if it can be written as $q-P$, where $P$ is a primorial and $q$ is the smallest prime greater than $P+1$. It is conjectured that Fortunate numbers are always prime.
It ...

**5**

votes

**0**answers

241 views

### Picking out an odd subset

I want to know whether the following property holds:
There exists a constant C such that for any big positive integer N and any nonempty subset M of {1,...,N} there exists a positive integer ...

**4**

votes

**0**answers

284 views

### About sign changes of Li(x)-π(x)

Given a constant $C$, which are the best known upper bounds for the number of sign changes
of the function
$$
f: \mathbb{N} \rightarrow \mathbb{R}, \ \ x \mapsto {\rm Li}(x)-\pi(x)
$$
in the range ...

**4**

votes

**0**answers

72 views

### On a weighted sum in a lemma for sieve methods

I'm reading James Maynard's paper "Small gaps between primes".
Lemma 6.1 (p.14) in this paper confused me. This lemma was taken from
Goldston-Graham-Pintz-Yildirim's paper "Small gaps between ...

**4**

votes

**0**answers

205 views

### Relative Densities

Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory.
How can I count ...

**4**

votes

**0**answers

298 views

### AKS Algorithm Pseudoprimes

The AKS algorithm is based on the following fully deterministic primality check:
Let input $n>1$ and $a \in \mathbb{N}$ such that $(a,n)=1$. Then $n$ is prime if and only if
$$\tag{1}(x+a)^n ...

**4**

votes

**0**answers

303 views

### Estimate on radical of $2^n \pm 1$

Not sure if this belongs to MO or not.
Are there any lower bound on radical of $2^n \pm 1$ (Recall that radical of integer $rad(k)$ is a product of primes which divide integer $k$)?
As an example If ...

**4**

votes

**0**answers

144 views

### smallest k such that highest prime factor of m(m+1)…(m+k-1) is > n if m > n.

I am fascinated by this entry OEIS A213253 which lists the smallest $k$ such that highest prime factor of $m(m+1)\dots(m+k-1)$ is $> n$ if $m > n$.
The article has references to the algorithm ...

**4**

votes

**0**answers

307 views

### Recursivity of the primes

As is well-known, with the finite set of the first $n$ primes $p_1,\dots ,p_n$ one can find all primes exactly (i.e. without false positives) with the Eratosthenes Sieve in the interval ...

**4**

votes

**0**answers

282 views

### Generalization of Tamarkin’s ARO 1993, final round, problem 10/8: part II

Let us use the notations of my previous question about Tamarkin's problem.
Let $\ell\in\left\lbrace 0,1,...,p\right\rbrace$.
An element $f\in \mathbb Z^{\mathbb Z}$ is said to be ...

**4**

votes

**0**answers

348 views

### Number of $k$-partitions of $n$ into odd prime parts

Browsing through OESIS I have found that if $p_p(n)$ denotes the number of partitions of $n$ into prime parts then $p_p(n) = O(e^{\frac{2 \Pi}{\sqrt{3}}\sqrt{n/\log n}})$.
I am interested in the ...

**4**

votes

**0**answers

499 views

### Are there an infinite number of prime Euclid numbers?

A number defined as the product of first $n$ prime numbers $+1$ is called $n$th Euclid number. Are there any survey on the progress for answering the following question: are there an infinite number ...

**3**

votes

**0**answers

135 views

### Can the following quantitative version of Chen's theorem be obtained?

The theorem of the Chinese mathematician Chen Jingrun is currently one of the best results with respect to the binary Goldbach problem. It asserts that every even integer $n$ is in the sumset $P + ...

**3**

votes

**0**answers

173 views

### Logarithms of ratios of squarefree numbers

Let $M \geq 1$, and $N=2^M$. Let $a_1, \dots, a_N$ be the set of all the numbers that you get when forming all square-free products of the first $M$ primes.
For example, for $M=2$ and $N=4$ you get ...

**3**

votes

**0**answers

164 views

### Generating function for the characteristic function of prime numbers

What do we know about the generating function of $\chi(n)$ (A010051)
$$
f(x) = \sum_{n=0}^\infty \chi(n)x^n = \sum_{p\text{ prime}} x^p
$$
for $\chi(n)$ the characteristic function of the primes:
...

**3**

votes

**0**answers

138 views

### Number of Inverse Pairs Modulo Prime $p$

Is there a result which gives a lower bound on the number of inverse pairs $(a, a^{-1})$ modulo prime $p$ lying in the interval $[1,t]$, where $t < p$?

**3**

votes

**0**answers

297 views

### Linear independence over Q of logarithmic powers of prime numbers

I denote $p_k$ the $k^{th}$ prime number ($p_1=2$, etc...)
Clearly, for any $n\in \mathbb{N}^*$, $(\log p_k)_{1\leq k\leq n}$ is linearly independent over $\mathbb{Q}$.
My question concerns a ...

**3**

votes

**0**answers

465 views

### Paul Erdős and Ramanujan Primes

It's easy to find Ramanujan's proof of Ramanujan primes:
Ramanujan's Proof
Wikipedia mentions that Paul Erdős also had a proof:
Wikipedia article on Bertrand's Postulate
Does anyone know the ...

**3**

votes

**0**answers

541 views

### Least Prime Factor in a sequence of 2n consecutive integers

I was thinking about consecutive integers and I wondered if anyone had done work exploring whether a sequence of $2n$ consecutive integers (i.e. 101,102,103,...,100+2n) always contains at least one ...

**2**

votes

**0**answers

116 views

### Analytic varieties for the primes and the twin primes

I am wondering what real and complex analysis say
about the primes and twin primes.
According to Wikipedia
analytic variety is defined locally as the set of common zeros of finitely many analytic ...

**2**

votes

**0**answers

253 views

### A question concerning the strange arithmetic derivation

This question is related to Strange (or stupid) arithmetic derivation. The original question whether an unbounded sequence of iterates exists is still unanswered.
$$n=\prod_{i=1}^{k}p_i^{\alpha_i} ...

**2**

votes

**0**answers

177 views

### Efficient ways to count primes satisfying Zhang's theorem

The theorem of Yitang Zhang states that there exist a finite $k \in \mathbb{N}$ such that there exist infinitely pairs of primes $(p,q)$ such that $|p - q| \leq k$. The statement that $k$ can be taken ...

**2**

votes

**0**answers

111 views

### Steps required to recognise a $z$-smooth number

I am currently reading section 5 of Pomerance's paper The Number Field Sieve and I have a few questions about smooth numbers.
A number $x\in\mathbb Z_{\ge1}$ is called $z$-smooth if every prime ...

**2**

votes

**0**answers

296 views

### On the primitive prime divisors of $q^n-1$

Let $q=p^\alpha$ be a prime power.
We call $r$ a primitive prime divisor of $q^n-1$ where $r\mid (q^n-1)$ but $r\nmid (q^i-1)$ for each $1\leq i\leq n-1$. The set of all primitive prime divisors of ...

**2**

votes

**0**answers

117 views

### Two products over primes

For $k \in \mathbb{N}$ define
$$ f(k) = \prod_{\text{p prime}}\left(1+\frac{1}{p^k(p^k+1)}\right)$$
$$ g(k) = \prod_{\text{p prime}}\left(1+\frac{1}{p^k(p^k-1)}\right)$$
By the product for zeta ...

**2**

votes

**0**answers

82 views

### Symmetric dominance regions surrounding a Gaussian prime

Let $z=a + b i$ be a complex number which is a Gaussian prime,
on neither the $x$- nor the $y$-axis.
So $a^2+b^2$ is a prime.
Construct a region $D(z)$ surrounding $z$ which is the
largest ...

**2**

votes

**0**answers

212 views

### Something Diophantine

Hi there,
recently I came across the following divisibility question, and I wondered if much
can be said about it.
Let $p$ and $q$ be different primes, and suppose $p^n + q^r$ divides $p^{2m} - 1$, ...

**2**

votes

**0**answers

288 views

### Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...

**2**

votes

**0**answers

323 views

### Prime generating algorithm

If I want an algorithm that outputs any $n$ distinct prime numbers, is there anything faster than Atkins' Sieve $O(n/log(log(n))$ ?

**2**

votes

**0**answers

304 views

### How small can intervals be and still contain a prime times a power of 2?

There was a question on MathOverflow which has since disappeared,
that was on sums of at most M B-smooth numbers. It asked
several questions related to how many could be found in the
interval ...

**2**

votes

**0**answers

258 views

### Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...