All Questions
130 questions
5
votes
0
answers
262
views
Primes generated by cyclotomic polynomials
Let $p$ be an odd prime, and let $f=\Phi_p$ be the $p$-th cyclotomic polynomial. Denote by $S_p$ the set of primes $q$ such that there exists a sequence of primes $p_1,\dots, p_g$ such that $p_1=f(1)=...
5
votes
1
answer
311
views
Is there a statement in Presburger arithmetic about primes this simple heuristic fails for?
I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:
Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary ...
- 3,319
5
votes
1
answer
737
views
Smallest prime factor of numbers
The literature refers to smooth integers as \begin{equation}\Psi(x,y):=\#\{n\le x:P_1(n)\le y\},\end{equation} where $P_1(n)$ is the largest prime factor of $n$. There are lots of results studying $\...
user344548
4
votes
0
answers
335
views
The number of continuously increasing primes gaps in the interval $[2,n]$ is less than $\log n$
A prime gap is the difference between two successive prime numbers. The $n$-th prime gap, denoted $g_n$ or $g(p_n)$ is the difference between the $(n+1)$-st and the $n$-th prime numbers. Using my ...
- 1,776
0
votes
1
answer
292
views
Factorization trees and (continued) fractions?
This question is inspired by trying to understand the lexicographic sorting of the natural numbers in the fractal at this question:
Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , ...
- 3,074
0
votes
0
answers
75
views
Existence of smooth integers in every residue class with large modulus
Let us say that a positive integer $x$ is $y$-power smooth, if the largest prime power divisor of $x$ is at most $y$. In what follows, let $C$ be any real number larger than $1$ and, for an integer $x$...
- 1,663
1
vote
2
answers
390
views
Solving a recurrence relation for the prime counting function?
I have found some number sequence $c_n = 1+b_n$ for $n \ge 0$, where $b_n = $ A307977(n).
I am trying to solve the following recurrence relation for the prime counting function:
$$\forall n \ge 3: \pi(...
- 3,074
5
votes
0
answers
131
views
Taking integer values of a sequence of Beurling primes
Let $P=(p_j)_{j=1}^\infty$ be an increasing sequence of real numbers with $1<p_1$ and $\lim_{j\to\infty}p_j=\infty$. As mentioned in [1], Beurling proved that if the multiplicative group $N_P$ ...
- 51
6
votes
2
answers
805
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 25.4k
5
votes
1
answer
340
views
About an asymptotic behavior in number theory
Where can I read about the asymptotic behavior (with $N$ tending to infinity) of the sum of the fractional parts obtained from dividing $N$ by all prime numbers up to $N$ divided by the number of ...
25
votes
1
answer
911
views
Reference request for a proof of the two-square Theorem
One can show (see below for a sketch of a proof) that every odd prime number $p$
can be written in exactly $(p+1)/2$ different ways as
$$p=a\cdot b+c\cdot d$$
with $a,b,c,d\in\mathbb N$ satisfying $\...
- 17.9k
4
votes
1
answer
601
views
Reference for a proof of Euclid's Theorem for the infinitude of primes
I would be curious to have a reference for the following proof
of Euclid's Theorem on the infinitude of primes:
Using Legendre's formula (also called de Polignac's formula) for
$p$-adic valuations of ...
- 17.9k
2
votes
0
answers
103
views
On equidistribution of primes in positive characteristic
In S. Lang's book "Algebraic Number Theory" (1986), page 317, Theorem 6 states essentially that given $P$ a set of primes, let $\tau:P\longrightarrow J$ be the typical idèle map taking ...
- 675
20
votes
2
answers
4k
views
information-theoretic derivation of the prime number theorem
Motivation:
While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number ...
- 3,871
3
votes
1
answer
419
views
Counting cubic residues mod p
Given a prime $p=3m+1$, $(p-1)/3$ of the residues mod $p$ are cubic residues. So heuristically, for any given integer $k>1$ not a perfect cube, we would expect that about 1/3 of the primes $\equiv1\...
- 9,114
1
vote
0
answers
132
views
Are the binary digits of the sequence of the prime numbers correlated?
Let $p_n\geq 3$ be the $n$th prime number with the binary expansion $p_n = \sum_{k=0}^{\infty} b_{nk}2^k$ ($b_{nk}\in\{0,1\}$). Let's write $q_{nk} = 1-2b_{nk}$.
Question: Is it true that for $k,l\...
- 2,605
26
votes
0
answers
567
views
Elliptic analogue of primes of the form $x^2 + 1$
I have a project in mind for an undergraduate to investigate next quarter -- a curiosity really, but I'm surprised I can't find it in the literature. I do not want a detailed analysis here... but ...
- 13.3k
2
votes
1
answer
305
views
Level spacing statistics for primes
In the preprint "Level Spacing Statistics for Primes", we have found some patterns of prime spacings, which may provide new insights on the distribution of primes:
We would like to know ...
- 149
8
votes
2
answers
1k
views
Question about functions $f: \mathbb{Z}^+ \to \mathbb{Z}^+$ such that $x$ is prime whenever $f(x)$ is prime
Let $f: \mathbb{\mathbb{Z}^+} \to \mathbb{Z^+}$ be a function and suppose
$(\star)$ For all integers $x \geq 3$, if $f(x)$ is prime, then $x$ is prime.
A trivial example of such a function is the ...
- 707
3
votes
1
answer
331
views
Fully explicit Linnik's Theorem
Linnik's Theorem states that there exist absolute constants $c$ and $L$ such that for every $m \in \mathbb{N}$ and every $a$ coprime to $m$, there is a prime $p$ with $p \equiv a \pmod{m}$ and $p < ...
- 1,663
9
votes
2
answers
547
views
Primes between $x$ and $x+x^\theta$
Iwaniec [1] proved that
$$
\pi(x+x^\theta)-\pi(x) < \frac{(2+\varepsilon)x^\theta}{\eta(\theta)\log x},\ x>x_0(\varepsilon,\theta).
$$
with
$$
\eta(\theta)=\frac{15\theta-2}{9}.
$$
(Actually, he ...
- 9,114
14
votes
1
answer
424
views
Unpublished result of Rosser in Sieve Methods book
Erdős and Selfridge (1971) state that the following is "implied by an unpublished result of Rosser" which they claim appears in a forthcoming book on sieve methods by Halberstam and Richert.
...
- 24.8k
9
votes
1
answer
400
views
The difference between consecutive primes in arithmetic progressions
Let $\pi(x)=\sum_{p\leq x}$ denote the prime counting function. A well known result of Baker, Harman, and Pintz on prime gaps states that for $x\geq y\geq x^{0.525}$ we have that
$$\pi(x+y)-\pi(x)\gg \...
- 11.4k
1
vote
1
answer
153
views
Number of distinct near-squares primes dividing an odd perfect number
I'm curious about if the following question is in the literature or what work can be done about it.
Denote the number of distinct primes dividing an odd perfect number $N$ with the arithmetic function ...
3
votes
1
answer
228
views
What fraction of the values of a quadratic polynomial can be prime?
I have an explicit, monic quadratic polynomial $P(x)$ and an integer $m$. Can I bound the number of prime values in $P(0), P(1), \ldots, P(m)$? A reference would be appreciated, if available. An ...
- 9,114
1
vote
0
answers
98
views
Reference request for a result in additive combinatorics
Let $p$ be a prime number and $[p-1]=\{1, 2, \ldots, p-1\}$.
The following proposition is proved: (but I cannot find out where)
Proposition: The non-empty subset sums of $[p-1]$ are equally ...
- 3,866
6
votes
4
answers
900
views
Mathematical induction vis-à-vis primes
One of the most used proof-techniques is mathematical induction, and one of the oldest subjects is the study of prime numbers. Thanks to Euclid, we can consider the primes as a infinite monotone ...
3
votes
0
answers
158
views
What can be said about the primality of Zsigmondy numbers?
I am cross-posting this from math.stackexchange, as it has received upvotes but no comments/answers after a couple months.
Let $\mathcal{Z}(n,a,b)=\frac{\Phi_n(a,b)}{\gcd (\Phi_n(a,b),n)}$ be the $n$-...
- 101
5
votes
2
answers
1k
views
Error term in Mertens' third theorem
Mertens' third theorem states that:
$$\prod_{\substack{
p \leq x \\
\text{p prime}
}} \left( 1 - \dfrac{1}{p} \right) \sim \dfrac{e^{-\gamma}}{\log(x)}$$
Question: what is the best functions (...
- 521
12
votes
1
answer
526
views
Equidistribution of $\{\alpha p\}$ for $p$ in an arithmetic progression
Let $\alpha$ be irrational. A famous theorem of Vinogradov says that $\{ \alpha p\}$ is equidistributed in $[0,1]$ as $p$ runs over all primes.
Let $a,q$ be natural numbers with $\gcd(a,q) = 1$. Then ...
- 21.3k
19
votes
2
answers
2k
views
Who first proved the generalization of Bertrand's postulate to (2n,3n) and (3n,4n)?
In Wikipedia's page for Bertrand's postulate, it is said that its (2n,3n) version was proved by El Bachraoui in 2006. Seems likely that it was first proved way before than that! Can anyone point to ...
- 2,992
9
votes
1
answer
388
views
$π(x+y) - π(x) ≤ c·y/\ln(y)$ for some constant $c$?
(I posted this question on Math SE but it has had no answer for a year now so I would like to ask if anyone here can provide one.)
Thinking about the prime number theorem, I wondered whether it is ...
- 2,912
25
votes
2
answers
4k
views
Primes of the form $x^2+ny^2$ and congruences.
The answer of following classical problem is surely known, but I can't find a reference
For which positive integer $n$ is the set $S_n$ of primes of the form $x^2+n y^2$ ($x$, $y$ integers) ...
- 26k
5
votes
4
answers
821
views
Can one show combinatorially how $\operatorname{lcm}(1, \dotsc, n)$ grows?
Let us write $M(n)$ for $\operatorname{lcm}(1,\dotsc,n)$ for $n$ a positive integer. Asymptotically $M(n)$ tends toward $e^n$. This result uses analytic number theory. (Lcm is least common multiple, ...
- 13k
3
votes
1
answer
247
views
Explicit bounds on number of squarefree numbers coprime to a certain number
We know that the number of squarefree integers $\le x$ that are coprime to $A$ is
$$
Q_A(x) = x \prod_{p|A} \left(1-\frac{1}{p}\right) \prod_{p \nmid A} \left(1-\frac{1}{p^2}\right) + O(\sqrt{x}).
$$
...
- 301
7
votes
1
answer
660
views
Prove: If $P_n$ is $n$-$th$ prime number then $P_{n+m} \ge P_n+P_m$
Let $n > 1$ and $m > 0$ be two integers and $P_n$ be the $n^{th}$ prime.
Prove: $$P_{n+m} \ge P_n + P_m .$$
Can you give a hint, reference, comment, or proof?
- 1,776
26
votes
1
answer
1k
views
What is the status on this conjecture on arithmetic progressions of primes?
The Green-Tao theorem states that for every $n$, there is an arithmetic sequence of length $n$ consisting of primes.
For primes, $p$, let $P(p)$ be the maximum length of an arithmetic progression of ...
- 1,835
3
votes
0
answers
154
views
Reference request for the following results
I am looking for references on the following results. In what follows $\pi(x)$ denotes the prime counting function.
Result 1. For all real $k>1$ there exists $x^k_0 \in \mathbb{R}$ such that for ...
- 31
17
votes
2
answers
2k
views
Is every odd positive integer of the form $P_{n+m}-P_n-P_m$?
I am looking for a comment, reference, remark, or proof of three conjectures as follows:
Conjecture 1: Let $x$ be an odd positive integer. Then there exist two integers $n, m \ge 2$ so that $$x=P_{n+...
- 1,776
6
votes
2
answers
1k
views
$\pi((n+1)^2)-\pi(n^2) \le \pi(n)$ for all $n \ge 370$?
There are some conjectures of the form: There always exist at least $X$ prime numbers between $A$ and $B$. Examples:
Bertrand's postulate: for every $n>1$ there is always at least one prime $p$ ...
- 1,776
5
votes
3
answers
809
views
Positive proportion of logarithmic gaps between consecutive primes
For $x, \lambda > 0$, define
$$S_\lambda(x) := \#\{p_{n+1} \leq x : p_{n+1} - p_n \geq \lambda \log x\} ,$$
where $p_n$ is the $n$th prime number. It is known [1] that an uniform version of the ...
- 113
4
votes
1
answer
507
views
A weaker version of the Brocard's Conjecture
Brocard's conjecture states that: If $p_{k}$ and $p_{k+1}$ are consecutive prime numbers greater than $2$, then between $p_{k}²$ and $p_{k+1}²$ there are at least four prime numbers.
I know that is ...
- 1,197
6
votes
0
answers
149
views
Dickson's conjecture for Beatty sequences
A particular case of Dickson's Conjecture states that for $a_1,q_1,a_2,q_2$ with $(a_1,q_1)=(a_2,q_2)=1$, there are infinitely many $n$ for which $q_1 n + a_1$ and $q_2 n+a_2$ are both prime, provided ...
- 1,990
16
votes
1
answer
4k
views
Order of magnitude of $\sum \frac{1}{\log{p}}$
Question: What is the order of magnitude of the following sum?
$$ \sum_{\substack{p<n\\\text{$p$ prime}}} \frac{1}{\log{p}} $$
Additional information: Since
$$ \sum_{\substack{p<n\\\text{...
- 3,004
1
vote
0
answers
140
views
Alternative Mersenne numbers
Let $\ b\in\mathbb Z,\ $ and $\ |b|>1.\ $ Call
$$ M_b(n)\ :=\ \frac{b^n-1}{b-1} $$
to be $n$-th Mersenne number mod $b$. The necessary condition for $\ M_b(n)\ $ to be a prime is that $\ n\ $ is a ...
- 4,786
8
votes
2
answers
354
views
Let $f \in \mathbb{Z}[x]$. Does $\bar{f}$ have as many roots in $\mathbb{F}_p$ as $f$ has in $\mathbb{C}$ for infinitely many primes $p$?
Let $f \in \mathbb{Z}[x]$ be a nonconstant polynomial. Consider $\bar{f} \in \mathbb{F}_p[x].$ Let $\rho_p$ be the number of distinct roots of $\bar{f}$ in $\mathbb{F}_p$, and let $\rho$ be the number ...
4
votes
2
answers
840
views
Upper bound for the first Hardy-Littlewood conjecture
About the Hardy-Littlewood conjecture by Terence Tao:
Conjecture 2 (Prime tuples conjecture, quantitative form) Let ${k_0 \geq 1}$ be a fixed natural number, and let ${{\mathcal H}}$ be a fixed ...
- 2,576
4
votes
1
answer
291
views
Reference / Survey for finite field analog number theory
It is folklore that many number theoretic results on prime numbers have a simpler-to-prove finite field analog. For example, on the one hand, the proof of the Prime Number Theorem
$$\#\{\text{prime ...
- 43
-2
votes
1
answer
396
views
Published articles in journals about the Firoozbakht's conjecture, whose main goal or focus is the study of this conjecture
I would like to know what articles are in the literature about the known as Firoozbakht's conjecture, see the Wikipedia Firoozbakht's conjecture.
Question. What articles have been published in ...
2
votes
1
answer
1k
views
Sum of the digits in base $p+1$
Definition
Let $W$ be the function , defined as $W(a,b)=r$
given $a,b\in \mathbb{Z_+}$ and $a>1$
Take $m$ to be the integer s.t. $a^{m+1} \ge b > a^{m}$, i.e. $m = \...
- 599