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$ ...
Ofir Gorodetsky's user avatar
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&...
Gerry Myerson's user avatar
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 ...
Max Alekseyev's user avatar
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 "...
Dan Piponi's user avatar
  • 8,086
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 ...
Ofir Gorodetsky's user avatar
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 ...
Dave Benson's user avatar
  • 11.6k
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 ...
GH from MO's user avatar
  • 98.2k
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 ...
Thomas Bloom's user avatar
  • 6,608
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 ...
Ofir Gorodetsky's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.9k
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-...
I. J. Kennedy's user avatar
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.
GH from MO's user avatar
  • 98.2k
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}{\...
GH from MO's user avatar
  • 98.2k
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 ...
Fedor Petrov's user avatar
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)). ...
Ofir Gorodetsky's user avatar
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 ...
Max Alekseyev's user avatar
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 ...
Pace Nielsen's user avatar
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=...
Roland Bacher's user avatar
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)-...
Alessandro Languasco's user avatar
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 ...
Will Sawin's user avatar
  • 135k
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 ...
GH from MO's user avatar
  • 98.2k
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_{...
Will Sawin's user avatar
  • 135k
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. ...
Noam D. Elkies's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
Dave Benson's user avatar
  • 11.6k
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 ...
GH from MO's user avatar
  • 98.2k
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+\...
GH from MO's user avatar
  • 98.2k
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-...
KConrad's user avatar
  • 49.6k
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 ...
Dave Benson's user avatar
  • 11.6k
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}...
GH from MO's user avatar
  • 98.2k

Only top scored, non community-wiki answers of a minimum length are eligible