44
votes
Accepted
What is the simplest proof that the density of coprime pairs does not go to zero?
I would say that the standard proof is elementary enough, but here is an argument that avoids the Möbius function and the Riemann zeta function.
Let $A_d$ be the set of pairs $(a,b)$ where $a,b\le x$ ...
32
votes
111...11 base p = 111...11 base q
Richard Guy, Unsolved Problems in Number Theory, 3rd Ed., section D10, writes,
The conjecture of Goormaghtigh, that the only solutions of
$$
{x^m-1\over x-1}={y^n-1\over y-1}
$$
with $x,y>1$ and $n&...
30
votes
Proof for new deterministic primality test
The claim does not hold. A counterexample is given by $n=14$, $p=134123250258009499$ and correspondingly
$$N = 2197475332227227631617 = 193 \cdot 12289 \cdot 926510094425921.$$
It can be easily ...
21
votes
Are 0 and 1, respectively, the least and most used digits among primes?
I guess it's OK to reply to a question about an empirical observation with more empirical observations.
Here's a Mathematica histogram of the digits of the first million primes:
Now I make a "...
19
votes
Accepted
On the error term of the Riemann explicit formula
Without any restriction on $x$ and $T$ (aside from $x,T \ge 2$) one has
$$f(x,T) \ll \frac{x}{T}\log^2 x + \log x,$$
which goes back to Landau. A modern reference is Theorem 12.5 in Montgomery and ...
18
votes
111...11 base p = 111...11 base q
I'm guessing that $1+5+25=31=1+2+4+8+16$ is the only example. There are certainly no more small examples, and probabilistically they get rare very quickly. But I only checked the first 80 primes to ...
18
votes
Accepted
Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , where $\pi$ denotes the prime counting function and $p_n$ denotes the $n$-th prime?
The sum is less than $1$. First of all, Mathematica and SAGE independently tell me that
$$\sum_{n=1}^{10000} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}=0.950344\dots.\tag{1}\label{1}$$
We estimate the tail sum ...
16
votes
Accepted
Can we write each positive rational number as $\frac1{p_1-1}+\ldots+\frac1{p_k-1}$ with $p_1,\ldots,p_k$ distinct primes?
This conjecture is true (as is the version for $p-h$ for any $h\neq 0$).
The proof is too long to reproduce here, but the preprint is at https://arxiv.org/abs/2305.02689
EDIT:
Quick summary as ...
16
votes
Accepted
Mertens-like theorem
This lies beyond Mertens, in the sense that this variant actually implies the Prime Number Theorem, as will be explained below, while Mertens' theorem is weaker than the PNT.
I sketch below a complex ...
16
votes
A little number theoretic game
(This is not an answer, but an extensive comment and numerical simulation about Grundy values.)
I believe there is some level of confusion because there are actually two very similar games under ...
15
votes
A little number theoretic game
Edit: I added code to compute the Nim values for the first $N$ positions of this game after the original post, as requested by @Timothy-Chow. Unfortunately my results don't match those given by @Peter-...
15
votes
Accepted
Can every integer be written as a sum of squares of primes?
The answer is yes, and this follows from known results concerning the Waring-Goldbach problem.
15
votes
Geometric mean of prime factors of all numbers up to n
What you experience is the "law of small numbers". The logarithm of the geometric mean in question is
$$\frac{\log n!}{\sum_{m=1}^n\Omega(m)}\sim\frac{n\log n}{n\log\log n}=\frac{\log n}{\...
14
votes
Accepted
For any integer $n>0$, does there always exist a prime $p>n$ such that $p\mid 2^n-1$?
Yes. By Zsigmondy's theorem for $n>6$ there exists a prime divisor $p$ of $2^n-1$ which does not divide $2^k-1$ for $k<n$. For such $p$, $n$ is a multiplicative order of 2 modulo $p$, thus it ...
14
votes
Accepted
For any integer $n>6$, does there always exist a prime $p>n+1$ such that $p\mid 2^n-1$?
Yes (except for $n=12$, as noted by Gerry Myerson). This is due to A. Schinzel, in strong form, see "On primitive prime factors of $a^n−b^n$" (Proc. Camb. Philos. Soc. 58, 555-562 (1962)).
...
14
votes
Accepted
When is $\mathrm{gcd}(k,p^k-1)=1$ true?
It is easier to describe non-good (bad) numbers with respect to a given prime $p$. For each such number $k$, there exists a prime $q$ such that $q\mid k$ and $q\mid (p^k - 1)$. It follows that $k$ is ...
13
votes
Does this number exist?
(This is an extended comment.) There couldn't be anything special about base 10, could there?
Notation: Given two positive integers $m,n$, let $m\oplus n$ be the integer that results from prepending ...
13
votes
What is the simplest proof that the density of coprime pairs does not go to zero?
A purely geometric argument involving no convergent sum (but a simple limit):
Suppose $x=2y$ even for simplicity.
The small square $s=[0,y]^2$ contains $(y+1)^2$ integer points
and the large square $S=...
13
votes
Accepted
Prime differences and zero multiplicity
This problem is connected with the $L^2$ average of primes in short intervals, see Selberg (1942 paper entitled “on the normal density…”). In particular, results on the integral of $\psi(x+h)-\psi(x)-...
12
votes
Accepted
Prime gaps within which every "small" prime appears as a factor: Are there only finitely many? Is this the last one?
As noted by Will Jagy in the comments, this is closely related to the size of prime gaps: Any gap of size at least $\sqrt{m}$ has this property.
In fact, every gap with this property has size at least ...
12
votes
Smallest prime factor of numbers
The number of integers $1\leq n\leq x$ with smallest prime factor exceeding $y$ is usually denoted by $\Phi(x,y)$. It has been studied thoroughly. See, for example, Chapter III. 6 (Integers free of ...
11
votes
Number of points on a surface modulo p
For $s \geq 6$ this is elementary as one can use the Weil bound for Jacobi sums, which predates Weil. By orthogonality of characters, we can express the number of points as $$ \frac{1}{ (p-1)^2} \sum_{...
11
votes
Accepted
Arithmetic sequences and Artin's conjecture
It's plausible that there are infinitely many primes $p \equiv 1 \bmod 4$
of which $2$ is a primitive residue. However, this is false for
$p \equiv \pm 1 \bmod 8$, because $2$ is a quadratic residue.
...
11
votes
Accepted
On the number of distinct prime factors of $p^2+p+1$
Yes. At first, there exist $c$ distinct primes $q_1,...,q_c$ which divide some $m_i^2+m_i+1$ for $i=1,\ldots,c$ respectively (induction on $c$: if you found $c-1$ such primes, take $m_c$ being equal ...
11
votes
On the number of distinct prime factors of $p^2+p+1$
There is the following theorem of Halberstam, "On the distribution of additive number-theoretic functions. III." Let $\omega(n)$ be the number of prime factors of $n$. Given any irreducible ...
11
votes
Accepted
Jacobi symbols for two-square sums of primes
The first observation follows from the law of quadratic reciprocity. Indeed, assume that $p\equiv 1\pmod{8}$ and $p=A^2+B^2$. Let $A'$ denote the odd part of $A$. Then $p\equiv B^2\pmod{A'}$, and ...
11
votes
Prime differences and zero multiplicity
It is not know that RH implies EH, or that EH implies RH. Let us denote
$$S(x):=\sum_{p_n < x} (p_n -p_{n-1})^2.$$
Assuming the Lindelöf hypothesis, Yu (1996) proved that $S(x)\ll_\varepsilon x^{1+\...
9
votes
Mertens-like theorem
I'll use the same notation $S_1(x)$ and $S_2(x)$ as in Ofir's answer and give more details behind some of the estimates and rely on a different approach to the Prime Number Theorem (no use of zero-...
9
votes
Unusual clump of small prime numbers?
This happens earlier at 18444 to 18450, and again from 21109 to 21115. It doesn't seem very special. If you want 37 as well, try 138411 to 138417.
This seems very much in line with Wojowu's naïve ...
9
votes
Accepted
Does the Riemann hypothesis predict a bound for this prime-counting function?
The Riemann hypothesis is equivalent to the following statement:
$$f(x)=\mathrm{li(x)}-\frac{x}{\log x}+O(\sqrt{x}),\qquad x\geq 2.$$
Note that
$$\mathrm{li(x)}=\mathrm{li(2)}+\frac{x}{\log x}-\frac{2}...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
prime-numbers × 2020nt.number-theory × 1736
analytic-number-theory × 668
reference-request × 150
prime-number-theorem × 99
goldbach-type-problems × 72
computational-number-theory × 70
co.combinatorics × 69
sequences-and-series × 66
prime-gaps × 60
algebraic-number-theory × 56
polynomials × 53
arithmetic-progression × 52
asymptotics × 50
factorization × 49
riemann-zeta-function × 41
divisors-multiples × 41
sieve-theory × 41
conjectures × 40
diophantine-equations × 38
algorithms × 37
riemann-hypothesis × 37
elementary-proofs × 37
integer-sequences × 33
prime-constellations × 29