All Questions
130 questions
6
votes
4
answers
898
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 ...
- 12.9k
5
votes
1
answer
310
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 ...
- 16.6k
5
votes
0
answers
261
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)=...
CommunityBot
- 1
6
votes
2
answers
804
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 ...
- 44.4k
4
votes
2
answers
730
views
Looking for paper: Weil's original 1952 "Sur les formules explicites de la théorie des nombres premiers"
I am looking for a source (preferably online) for Weil's original 1952 paper on the explicit formula. I am aware of an english translation available here, but would like to have access to the original ...
- 5,407
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
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 ...
- 12.9k
3
votes
1
answer
330
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 < ...
- 105k
7
votes
1
answer
652
views
Fermat-quotient of "order" 3: I found $68^{112} \equiv 1 \pmod {113^3}$ - are there bigger examples known?
(I've taken this from MSE, it seems to be more appropriate here)
I'm rereading an older text on fermat-quotients (see wikipedia) from which I have now the
Question for
$$ b^{p-1} \equiv 1 \pmod{ ...
- 34.3k
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 $\...
- 105k
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
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,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 $\...
- 105k
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(...
- 1,126
5
votes
2
answers
388
views
How much do these interval collections cover?
As usual any related references are appreciated.
Let $p \lt q$ be distinct primes, and for all such pairs, let $m=pq$ and let $\cal{C}$ be the collection $(m-p,m)$ of open intervals. Does (the union ...
- 34.3k
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 ...
- 869
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) ...
- 25.7k
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
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\...
- 4,713
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 ...
CommunityBot
- 1
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 ...
- 869
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 ...
- 50.6k
7
votes
4
answers
1k
views
Reference for the expected number of prime factors of n larger than n^alpha is -log alpha
Let $0 < \alpha < 1$ be a constant. The expected number of prime factors of a "random" integer near $n$ which are greater than $n^\alpha$ is $-\log \alpha$.
It's my understanding that (...
- 11.4k
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 ...
- 118k
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 ...
- 6,969
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
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
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 ...
- 1,451
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 \...
- 5,089
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
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
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.
...
- 43.7k
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
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{...
- 105k
1
vote
0
answers
139
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
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?
- 105k
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
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 ...
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
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}).
$$
...
- 105k
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
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 ...
- 105k
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 ...
- 105k
2
votes
0
answers
313
views
On the Chowla and twin prime conjectures
I'm reading https://terrytao.wordpress.com/tag/chowlas-conjecture/ and at some point it is mentioned that, the twin prime conjecture is a variant of Chowla's conjecture that $\sum_{n\leq x} \lambda(n)\...
- 1,019
0
votes
1
answer
204
views
On $(\prod_{\substack{1\leq s\leq X\\s\text{ semiprime}}}s)(\sum_{\substack{1\leq s\leq X\\s\text{ semiprime}}}\frac{1}{s})$ as $X\to\infty$
Few weeks ago an user from Mathematics Stack Exchange answered my question On an inequality that involves products and sums related to the sequence of semiprimes (asked May 26). It seems that for ...
- 12.8k
1
vote
1
answer
177
views
Arithmetic progressions, given a prime
I have recently become interested in reading a little more on certain directions regarding primes in arithmetic progressions (AP). I would appreciate specific paper references (with the journal and ...
- 63.9k
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, ...
- 105k
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 (...
- 18.7k
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 ...
4
votes
1
answer
332
views
Estimating certain short Kloosterman sums
Recall that for the classical Kloosterman sum
$$ K(a,b,p^t):= \sum_{x \in (\mathbb{Z}/ p^t \mathbb{Z})^* } \psi \left(\frac{ax+bx^{-1}}{p^t} \right),$$
where $\psi(x)=e^{2\pi ix}$, $a,b,t$ are natural ...
- 12.3k