Prime numbers are natural numbers not divisible by any smaller number other than 1. This tag is intended for questions about, related to, or involving prime numbers.

learn more… | top users | synonyms

21
votes
0answers
417 views

Sheldon Cooper Primes

On the $73^{\text{rd}}$ episode of the Big Bang Theory, Dr. Sheldon Cooper, an astrophysicist portrayed by Jim Parsons $(1973 - \stackrel{\text{hopefully}}{2073})$ revealed his favorite number to be ...
20
votes
0answers
190 views

Can a number be equal to the sum of the squares of its prime divisors?

If $$n=p_1^{a_1}\cdots p_k^{a_k},$$ then define $$f(n):=p_1^2+\cdots+p_k^2$$ So, $f(n)$ is the sum of the squares of the prime divisors of $n$. For which natural numbers $n\ge 2$ do we have ...
14
votes
0answers
396 views

Divergence of the Derivative of the Prime Counting Function

On the one hand, the Prime Counting Function $\pi_0(x)$ maybe be written $$ \pi_0(x) = \operatorname{R}(x^1) - \sum_{\rho}\operatorname{R}(x^{\rho}) \tag{1} $$ with $ \operatorname{R}(z) = ...
13
votes
0answers
72 views

What other prime numbers have been ruled out as counterexamples to the Feit-Thompson conjecture?

Given distinct primes $p$ and $q$, $$\frac{p^q - 1}{p - 1}$$ is never a divisor of $$\frac{q^p - 1}{q - 1}.$$ Or so we believe. If $p = 2$, then it's clear that no odd prime $q$ can make a ...
13
votes
0answers
437 views

Sorting of prime gaps

Let $g_i $ be the $i^{th}$ prime gap $p_{i+1}-p_i.$ If we re-arrange the sequence $ (g_{n,i})_{i=1}^n$ so that for any finite $n$ the gaps are arranged from smallest to largest we have a new sequence ...
13
votes
0answers
167 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
11
votes
0answers
113 views

Product of primes mod n

Let $n$ be an odd composite number. I'm trying to compute $$ f(n)=\prod_{n/2<p<n}p\pmod n $$ where $p$ ranges over the primes in the indicated region. Can this be done (significantly) faster ...
10
votes
0answers
128 views

Curious representation of primes

I found the following problem on the internet, and my initial intuition turned out to be entirely incorrect. The question asked what is the smallest prime $r$ that does not have a representation of ...
10
votes
0answers
354 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 1

I was reading "The Prime Numbers and Their Distribution" by Gérald Tenenbaum and Michel Mendès France, the section about Cramér's Model, and I couldn't prove a couple of results. I would like to start ...
10
votes
0answers
328 views

A question about the divisibility of sum of 2 consecutive primes.

Well as I was curious about the sum of $2$ consecutive primes, after proving that the sum for the odd primes always has at least 3 prime divisors, I came up with this question: Find the least ...
10
votes
0answers
180 views

Continued fraction with prime reciprocal entries

We know that the reciprocals of the primes form a divergent series. We also know that a necessary and sufficient condition for a continued fraction to converge is that its entries diverge as a series. ...
10
votes
0answers
220 views

An infinitude of “congruence condition” primes?

Background: Several special classes of primes can be written as primes that satisfy some additional constraint $f(p)\equiv 0\pmod p$; for instance, Wilson primes are congruence primes with ...
9
votes
0answers
151 views

Showing that the Prime Number Theorem is Plausible.

I have started to work through the course notes titled "Integers, Polynomials and Finite Fields" by Kenneth Davidson to keep me busy this summer, and there is a question in here This is an ...
9
votes
0answers
512 views

Understanding Ramanujan's approach in his proof of Bertrand's Postulate

I've been reading through Ramanujan's proof of Betrand's Postulate and I'm not clear why he didn't state his proof in terms of $\varphi(2x) - \varphi(x)$ What would be wrong with this approach for ...
9
votes
0answers
440 views

Why does this identity equal the number of primes?

Can someone explain why this identity gives the number of primes? I don't understand it. $D_{0,a}(n) = 1$ $D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} \binom{k}{j}\sum_{m=a+1}^{\lfloor ...
8
votes
0answers
335 views

Two (strictly related) proofs by induction of inequalities.

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
8
votes
0answers
103 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
8
votes
0answers
119 views

Primality of $n! +1$

I came across with a problem where I was required to examine primality of $n! +1$ (17! + 1 was the actual number). Although Wilson's Theorem could be manipulated for determining primality of $n! + ...
8
votes
0answers
176 views

Intuition behind Erdős proof of the infinitude of prime numbers

Suppose by contradiction that there are finitely many primes, namely $p_1, p_2,...,p_k$, where $k$ is a natural number. Now consider another natural number $n$, and all natural numbers $m \leq n$. ...
8
votes
0answers
251 views

Why are minima of $(k \bmod 4)$-Prime $\zeta$ functions $|P_x(r,t)|$ more frequent for $\frac\pi2\leq t \leq \pi$?

I got these plots when I evaluate the sum of truncated $(k \bmod 4)$-Prime $\zeta$ function, i.e. $$ P_x(r,t)=P_{x;4,1}(-ir\cos t)+P_{x;4,3}(-ir\sin t)=\sum_{x\geq p\;\bmod\;4=3} p^{-ir\cos ...
8
votes
0answers
110 views

Asymptotics of the lower approximation of a pair of natural numbers by a coprime pair

When we are working, for instance, in combinatorics or graph theory, sometimes we can have the following situation. For each number $m$ from an infinite set $\mathbb M\subset\mathbb N$ we can ...
8
votes
0answers
198 views

How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes?

Is there an easy way to compute the following question: How many numbers of the form $p_1^2 p_2 p_3$ are there less than $10^{15}$ for $p_1$, $p_2$, $p_3$ distinct primes? The only thing that ...
8
votes
0answers
226 views

Weak version of Fortune's conjecture

Let $p\#=2\cdot3\cdot5\cdots p$ denote the primorial and $N(x)$ the smallest prime greater than or equal to $x$. Then Fortune's conjecture is that $N(p\#+2)-p\#$ is prime for all $p$. (Heuristic: to ...
7
votes
0answers
146 views

What is known about the sum $\sum\frac1{p^p}$ of reciprocals of primes raised to themselves?

Consider the following series: $$\sum_{p\in\mathcal{P}}\frac{1}{p^p}$$ where $\mathcal{P}$ is the set of all prime numbers: $\mathcal{P}=\{2,3,5,7,11,13,\ldots\}$. My question is: Is this a ...
7
votes
0answers
141 views

A problem about $e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$

Let $\alpha_i\in [0,1),\; i\in \{1,\cdots,N\}$ for some positive integer $N$, such that $$e^{2\pi i \alpha_1}+e^{2\pi i \alpha_2}+\cdots+e^{2\pi i \alpha_N}=0$$ and if for any non-empty proper subset ...
7
votes
0answers
107 views

For primes $P_1$ and $P_2$, exists a prime $P_3$ that both $P_i + 6P_3$ is a prime

I was thinking about twin primes and I came to ask this question: If we have two distinct primes $P_1$ and $P_2$ which are both greater than $3$, then does there always exist a prime $P_3$ such that ...
7
votes
0answers
110 views

Is this a recurrence for the characteristic sequence of composite numbers?

The characteristic sequence of composite numbers is equal to 1 if $n$ is not a prime number and equal to 0 if $n$ is a prime number, starting: $$1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1,...$$ where the ...
7
votes
0answers
609 views

The prime number theorem and the nth prime

This is a much clearer restatement of an earlier question. In section 1.8 of Hardy & Wright, An Introduction to the Theory of Numbers, it is proved that the function inverse to $ x ⁄ \log⁡ x$ is ...
7
votes
0answers
179 views

Prime numbers, analysis of polylogarithms

Can any interesting results concering prime numbers be obtained using the analytic properties of the polylogarithm, similar to how analytic methods are used on the zeta function to obtain results ...
6
votes
0answers
69 views

A bound on the nth prime.

Is there any combinatorial argument to show that the nth prime $p_n = \mathcal{O}(n^k)$ for fixed $k$ ? There is a problem in the book by Apostol to find upper bounds on $p_n$, the Prime Number ...
6
votes
0answers
203 views

Relatives of Heegner numbers?

It is well known that Euler's lucky numbers are related to the Heegner numbers, where \begin{align} &n^2+n+p\\ \end{align} gives primes for $n=0,\dots,p-2$ if and only if its discriminant ...
6
votes
0answers
87 views

An Impossible Sequence of Prime Powers

Let $x_1,x_2,\ldots$ be a sequence of positive integers that satisfies the recurrence relation $$x_{n+1}=2x_n(x_n-1)+1$$ for all positive integers $n$. It seems impossible that every term in this ...
6
votes
0answers
75 views

Applying iterated function on the sum of the squares of the prime factors of $30$

Let $f(n)$ denote the sum of the squares of the prime factors of $n$ with multiplicity. For example, $f(60)=f(2\cdot2\cdot3\cdot5)=2^2+2^2+3^2+5^2=42$. Denote the iterated function ...
6
votes
0answers
71 views

To solve for $x,y,n$ in non-negative integers , $\dfrac{x!+y!}{n!}=p^n$ , $p$ a given prime

Let $p$ be a given prime , then how do we find non-negative integers $(x,y,n)$ $\space$ , such that $\dfrac{x!+y!}{n!}=p^n$ ?
6
votes
0answers
138 views

Coprime multiplicative orders modulo infinitely many primes

Is it true that there are infinitely many primes $p$ such that the multiplicative orders of $2$ and $3$ are coprime $\pmod{p}$? By this I mean their order in $(\mathbb{Z}/p\mathbb{Z})^*$. If the ...
6
votes
0answers
77 views

Statement about Woodal primes.

A Woodal number is an integer of the form $n 2^{n}-1$. A Woodal prime is an integer that is both a prime and a Woodal number. Let $p$ be a prime of the form 1 mod 4. Then $p 2^{p} -1$ is never a ( ...
6
votes
0answers
145 views

Density of products of a certain set of primes

I have an infinite set S of prime numbers with relative density 0 (that is, $\lim_ns_n/p_n=\infty$ with $S=\{s_1,s_2,\ldots\}$ and $s_1 < s_2< \cdots$). I would like to find the size (in some ...
6
votes
0answers
140 views

Number of primefactors in $ f(n,W) = \prod_{k=1}^W (p_k^n -1) \text{ where } p_k=Prime(k) $

I'm reviving an old fiddling, although I do not yet really see its benefit. Beginning with the eulerproduct for the zeta-function in the representation $\small \zeta(n)=\prod {1\over 1-p^{-n} } = ...
6
votes
0answers
256 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
5
votes
0answers
35 views

Why are there palindromic subsequences at random among this sequence?

So I was thinking about the Goldbach conjecture and I rephrased it to myself as the following: Prove that every number lies halfway between two primes (or is itself prime.) Which is equivalent. ...
5
votes
0answers
33 views

Given $h(\mathcal{O}_{\mathbb{Q}(\sqrt{d})}) = 1$, what is the longest possible run of inert primes in that ring?

Say $\mathcal{O}_{\mathbb{Q}(\sqrt{d})}$ is a unique factorization domain. A couple of primes will ramify, the rest will either split or be inert. For example, in ...
5
votes
0answers
75 views

Possibly New Prime Conjecture

I was in the midst of proving a conjecture when I came across an observation that led me to forming a potentially new conjecture. The conjecture goes as follows: Any given sum of twin primes ...
5
votes
0answers
108 views

Is the Wikipedia article on the proof for Bertrand's Postulate correct?

I was checking out the Wikipedia article on the proof of Bertrand's Postulate. For Lemma 4, the argument is made for $x\ge 3, x\#<2^{2x-3}$ Here's the proof by induction: $n = 3$: $n\# = ...
5
votes
0answers
140 views

Primes as sum of squares.

If $p_{i}$ and $p_{j}$ are two primes of the form $4k+1$ , with $p_{j} > p_{i}$, show that if $p_{j} \neq$ sum of two squares $p_{i}$ is also not equal to sum of two squares. It is well ...
5
votes
0answers
53 views

More primes of the form $6k-1$ than $6k+1$

Let $a_n:= $ number of primes of the form $6k-1$ and $\le n$ and $b_n:= $ number of primes of the form $6k+1$ and $\le n$. I was playing with my computer and noticed that $a_n\ge b_n$ for ...
5
votes
0answers
165 views

Does this prime generating way generate all the prime numbers?

I've thought of the following algorithm to find the entire list of prime numbers: Take a prime number $p$ to your list. $1.$ Multiply all the numbers in your list and call the number you get ...
5
votes
0answers
59 views

Renyi entropy of prime gaps

Denote with $p_n$ the $n$-th prime number and let $$ h_N(d) = |\{ n : p_{n+1} < N, p_{n+1} - p_n = d \}| $$ be the number of times that prime gap $d$ happens for primes less than $N$. Let $H = ...
5
votes
0answers
115 views

Are $ut + 1$ and $ut + t + 1$ both prime for some t for any $u$?

Conjecture : For any natural number $u$, there is a natural number $t$ such that $ut + 1$ and $ut + t + 1$ are both prime. So we get a solution of the equation $$au - b(u+1) = -1$$ with prime ...
5
votes
0answers
161 views

How to list the prime factorised natural numbers?

Today I set out to invent a two character numeral system designed to make factorization trivial. Indeed, it lets one factor non-trivial numbers with over thousand digits within 30 seconds per hand - ...
5
votes
0answers
296 views

Logical consequence of Euclid's theorem

Are there any far reaching non-trivial consequences of Euclid's infinitude of primes where theorems make use of it? Wikipedia does not have the list of applications of this theorem, rather modern ...