All Questions
Tagged with nt.number-theory prime-numbers
1,808 questions
118
votes
5
answers
33k
views
How did Cole factor $2^{67}-1$ in 1903?
I just heard a This American Life episode which recounted the famous anecdote about Frank Nelson Cole factoring $N:=2^{67}-1$ as $193{,}707{,}721\times 761{,}838{,}257{,}287$. There doesn't seem to be ...
- 156k
103
votes
4
answers
37k
views
Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture
Yitang Zhang recently published a new attack on the Twin Primes Conjecture. Quoting Andre Granville :
“The big experts in the field had
already tried to make this approach
work,” Granville said....
- 1,063
93
votes
3
answers
6k
views
A little number theoretic game
I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number $n$, the other player can only reply in two different ways: They can ...
- 861
82
votes
3
answers
20k
views
Czelakowski's claimed proof of the Twin Prime Conjecture
It seems like the article "The Twin Primes Conjecture is True in the Standard Model of Peano Arithmetic: Applications of Rasiowa–Sikorski Lemma in Arithmetic (I)" by Janusz Czelakowski ...
- 1,083
79
votes
6
answers
11k
views
Does Zhang's theorem generalize to $3$ or more primes in an interval of fixed length?
Let $p_n$ be the $n$-th prime number, as usual:
$p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, etc.
For $k=1,2,3,\ldots$, define
$$
g_k = \liminf_{n \rightarrow \infty} (p_{n+k} - p_n).
$$
Thus the twin ...
- 79.9k
78
votes
1
answer
5k
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 ...
- 15.5k
69
votes
2
answers
4k
views
Function that produces primes
For any $n\geq 2$ consider the recursion
\begin{align*}
a(0,n)&=n;\\
a(m,n)&=a(m-1,n)+\operatorname{gcd}(a(m-1,n),n-m),\qquad m\geq 1.
\end{align*}
I conjecture that $a(n-1,n)$ is always ...
- 4,938
69
votes
4
answers
14k
views
Is a "non-analytic" proof of Dirichlet's theorem on primes known or possible?
It is well-known that one can prove certain special cases of Dirichlet's theorem by exhibiting an integer polynomial $p(x)$ with the properties that the prime divisors of $\{ p(n) | n \in \mathbb{Z} \}...
- 118k
69
votes
1
answer
4k
views
Iterations of $2^{n-1}+5$: the strong law of small numbers, or something bigger?
I've discovered what I believe is a quite remarkable sequence (A318970), defined by
$$n_1 = 3,\qquad n_{k+1} = 2^{n_k-1}+5\quad(k\geq 1).$$
Here are the first four terms with their prime ...
- 34.3k
66
votes
3
answers
6k
views
Chebyshev polynomials of the first kind and primality testing
Can you provide a proof or a counterexample for the claim given below ?
Inspired by Agrawal's conjecture in this paper and by Theorem 4 in this paper I have formulated the following claim :
Let $...
- 2,661
65
votes
6
answers
14k
views
What is the simplest proof that the density of primes goes to zero?
By density of primes, I mean the proportion of integers between $1$ and $x$ which are prime. The prime number theorem says that this is asymptotically $1/\log(x)$.
I want something much weaker, namely ...
- 4,164
62
votes
1
answer
14k
views
Is the Green-Tao theorem true for primes within a given arithmetic progression?
Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes.
Now, consider an arithmetic progression with starting term $a$ and common difference $d$. ...
- 3,699
62
votes
2
answers
3k
views
A conjecture regarding prime numbers
For $n,m \geq 3$, define $ P_n = \{ p : p$ is a prime such that $ p\leq n$ and $ p \nmid n \}$ .
For example :
$P_3= \{ 2 \}$
$P_4= \{ 3 \}$
$P_5= \{ 2, 3 \}$,
$P_6= \{ 5 \}$ and so on.
Claim: $...
- 653
60
votes
6
answers
7k
views
Has decidability got something to do with primes?
Note: I have modified the question to make it clearer and more relevant. That makes some of references to the old version no longer hold. I hope the victims won't be furious over this.
Motivation:
...
- 2,824
56
votes
1
answer
4k
views
A mysterious connection between primes and $\pi$
The Prime Number Theorem relates primes to the important constant $e$.
Here I report my following surprising discovery which relates primes to $\pi$.
Conjecture (December 15, 2019). Let $s(n)$ be ...
- 15.6k
53
votes
5
answers
4k
views
Distribution of square roots mod 1
I was wondering about the distribution of $\sqrt{p}$ mod $1$ this morning, as one does while brushing one's teeth. I remembered the paper of Elkies and McMullen (Duke Math. J. 123 (2004), no. 1, 95–...
- 13.3k
52
votes
4
answers
17k
views
How hard is it to compute the number of prime factors of a given integer?
I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.
...
- 2,416
52
votes
1
answer
6k
views
Are the primes normally distributed? Or is this the Riemann hypothesis?
Forgive my very naive question. I know next to nothing about number theory, but I'm curious about the state of the art on the distribution of primes.
Let $\mathrm{Li}(x)$ be the offset logarithmic ...
- 8,493
49
votes
4
answers
4k
views
Are there primes of every Hamming weight?
Are there primes of every Hamming weight? That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$?
In this case, the Hamming ...
- 593
49
votes
4
answers
4k
views
Strange (or stupid) arithmetic derivation
Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to ...
- 3,004
48
votes
4
answers
3k
views
Twin primes conjecture and extrapolation method
Let $(p_1, p_2)$ be a twin prime pair, where we include $(2, 3)$. If $p_1 \equiv 1$ mod $4$ then we let $t_{(p_1, p_2)} := p_1 ^ 2 / p_2 ^ 2$ otherwise, we let $t_{(p_1, p_2)} := p_2 ^ 2 / p_1 ^ 2$.
...
- 1,305
46
votes
4
answers
8k
views
Why could Mertens not prove the prime number theorem?
We know that
$$
\sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x)
$$
where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy
$$
\sum_{p \le x}\frac{1}{p} = \ln\ln ...
- 5,470
45
votes
3
answers
6k
views
Why such an interest in studying prime gaps?
Prime gaps studies seems to be one of the most fertile topics in analytic number theory, for long and in lots of directions :
lower bounds (recent works by Maynard, Tao et al. [1])
upper bounds (...
- 5,424
43
votes
1
answer
1k
views
Can't one walk to infinity on the prime numbers with finitely many distinct affine steps?
Let $(a_1,b_1), \dots, (a_k,b_k)$ be finitely many pairs of positive
integers, and let $\Gamma$ be the graph whose vertices are the prime
numbers and in which two vertices $p$ and $q$ are connected by ...
- 19.6k
42
votes
2
answers
9k
views
Is Li(x) the best possible approximation to the prime-counting function?
The Prime Number Theorem says that $\lim_{n \to \infty} \frac{\pi(n)}{\mathrm{Li}(n)} = 1$, where $\mathrm{Li}(x)$ is the Logarithm integral function $\mathrm{Li}(x) = \int_2^x \frac{1}{\log(x)}dx$. ...
- 5,530
39
votes
1
answer
2k
views
Prime number races in 2 dimensions
Is the mapping $$f: \ \mathbb{N} \rightarrow \mathbb{Z}[i], \ \ \ n \ \mapsto
\sum_{2 < p \leq n \ {\rm prime}} e^{\frac{p-1}{4} \pi i}$$ surjective?
In 1999, when I was an undergraduate student, ...
- 19.6k
38
votes
3
answers
3k
views
What is the current status of Agrawal's conjecture?
In their famous 'Primes is in P' paper Agrawal, Kayal and Saxena stated the following conjecture:
If for coprime integers $n$ and $r$ the equality $(X-1)^n = X^n - 1$ holds in $\mathbb{Z}_n[X]/(X^r-...
- 463
38
votes
4
answers
7k
views
What did Yu Jianchun discover about Carmichael numbers?
There's a news story going around (see for example [1]; other accounts are even more breathless) about an amateur mathematician, Yu Jianchun, finding an "alternative method to verify Carmichael ...
- 9,114
37
votes
2
answers
3k
views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
- 1,730
37
votes
3
answers
1k
views
Is there a $c > 1$ such that for all $n \ge 1$ the largest integer $\le c^n$ is prime?
Does there exist a real number $c > 1$ such that for every natural number $n > 0$, the number $\lfloor c^n \rfloor$ is prime?
I doubt such a number $c$ is known to exist, since the best similar ...
- 22.3k
37
votes
5
answers
3k
views
Happy New Prime Year!
It happens that next year 2011 is prime, while outgoing 2010 is
highly composite in the sense that the number of its distinct prime factors
is 4, maximal possible for a year $< 2310$.
Let me ...
- 13.5k
36
votes
8
answers
32k
views
What are the connections between pi and prime numbers?
I watched a video that said the probability for Gaussian integers to be relatively prime is an expression in $\pi$, and I also know about $\zeta(2) = \pi^2/6$ but I am wondering what are more ...
36
votes
2
answers
7k
views
Why do primes dislike dividing the sum of all the preceding primes?
I was investigating primes with the property that the sum of the first $n$ primes is divisible by $p_n$. It turns out that these primes are extremely extremely rare. For primes less than $10^9$, I ...
- 5,470
35
votes
9
answers
9k
views
Why is integer factoring hard while determining whether an integer is prime easy?
In 2002, the discovery of the AKS algorithm proved that it is possible to determine whether an integer is prime in polynomial time deterministically. However, it is still not known whether there is an ...
- 2,649
35
votes
1
answer
4k
views
Does the algorithm of the Greeks produce all prime numbers?
Let ${\cal P}$ be the set of prime numbers. Define a subset ${\cal P}'=\{p_1,p_2,p_3,\cdots\}$ of ${\cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${\cal P}$ ...
- 937
34
votes
7
answers
8k
views
Explicit formula for Riemann zeros counting function
I've often seen it stated (in vague terms) that there's a Fourier duality between the set of prime numbers and the set of nontrivial Riemann zeta zeros.
Because there are various explicit formulae ...
- 371
34
votes
3
answers
6k
views
Bringing Number and Graph Theory Together: A Conjecture on Prime Numbers
Some MOers have been skeptic whether something like natural number graphs can be defined coherently such that every finite graph is isomorphic to such a graph. (See my previous questions [1], [2], [3]...
- 9,720
34
votes
2
answers
2k
views
Does iterating a certain function related to the sums of divisors eventually always result in a prime value?
Let define the following function for integers (from 2): $f(x)=\sigma(x)-1$, where $\sigma$ is the sum of the divisors of $x$.
For example $f(6)=6+3+2=11$, $f(5)=5$.
Note that $x$ is a fixed point for ...
- 337
34
votes
1
answer
843
views
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?
It is well-known that any positive rational number can be written as the sum of finitely many distinct unit fractions. This is easy since
$$\frac1n=\frac1{n+1}+\frac1{n(n+1)}\quad\text{for all}\ n=1,2,...
- 15.6k
32
votes
3
answers
8k
views
Ideas in the elementary proof of the prime number theorem (Selberg / Erdős)
I'm reading the elementary proof of prime number theorem (Selberg / Erdős, around 1949).
One key step is to prove that, with $\vartheta(x) = \sum_{p\leq x} \log p$,
$$(1) \qquad\qquad \vartheta(x) \...
- 587
32
votes
1
answer
4k
views
Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $
EDIT, 9 March 2014: when I asked this in 2010, I did not have the courage of my convictions, and so did not ask for an if and only if proof, as Kevin Buzzard quite properly pointed out. Such problems ...
- 25.7k
32
votes
2
answers
2k
views
Generalization of Tamarkin's ARO 1993, final round, problem 10/8: still a conjecture?
This is from the category "problems I cannot believe that are still open". But then again, I don't know whether it is still open; it seems to have escaped the attention of most number theorists and ...
- 33.8k
32
votes
2
answers
2k
views
A Collatz-like problem on prime numbers
Consider the function $f$ on the prime numbers defined by $$ f(p):= \text{ the greatest prime factor of } 2p+1.$$ The iteration of $f$ from any prime $p<10^8$ converges to the cycle $$(3,7,5,11,23,...
31
votes
4
answers
2k
views
A Collatz-like function that bifurcates on primes
This is likely piling one mystery on another, but ...
I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows:
$$
f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is ...
- 151k
30
votes
2
answers
4k
views
What is the crucial difference the Maynard/Tao approach and Goldston-Pintz-Yildirim that extends to prime k-tuples with $k>2$
Suppose $m$ is a positive integer. A quantity of interest is
$$
H_m = \liminf_{n\to\infty} \left(p_{n+m} - p_n \right)
$$
The twin prime conjecture, is, of course $H_1 = 2$, the the prime k-tuples ...
- 1,354
30
votes
3
answers
4k
views
Heuristic argument for the prime number theorem?
Here is a bad heuristic argument for the prime number theorem. Let $n$ be a positive integer and assume that PNT holds up to $n$. Then $n$ itself is prime if and only if for each prime $p<n$ the ...
- 29k
29
votes
4
answers
3k
views
Is there an 11-term arithmetic progression of primes beginning with 11?
i.e. does there exist an integer $C > 0$ such that $11, 11 + C, ..., 11 + 10C$ are all prime?
- 4,164
29
votes
7
answers
7k
views
Asymptotic density of k-almost primes
Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is
$$\pi_k(x)\sim\frac{x(\log\log x)^{k-1}}{(k-1)!\...
- 9,114
29
votes
6
answers
5k
views
Infinitely many primes of the form $2^n+c$ as $n$ varies?
At the time of writing, question 5191 is closed with the accusation of homework. But I don't have a clue about what is going on in that question (other than part 3) [Edit: Anton's comments at 5191 ...
- 41.4k
29
votes
2
answers
3k
views
Is there a Kolmogorov complexity proof of the prime number theorem?
Lance Fortnow uses Kolmorogov complexity to prove an Almost Prime Number Theorem (https://lance.fortnow.com/papers/files/kaikoura.pdf, after theorem $2.1$): the $i$th prime is at most $i(\log i)^2$. ...
- 13.9k