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

11
votes
0answers
135 views

Primes in $\lfloor a^{n} \rfloor$

Motivated by the question Is there any result, that says that $\lfloor e^{n} \rfloor$ is never a prime for $n>2$?, take a real number $a>1$ and consider the sequence $\lfloor a^{n} \rfloor$. ...
11
votes
0answers
324 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) = ...
10
votes
0answers
201 views

Irrationality of $\displaystyle\sum_{p\in\mathbb{P}} \frac{1}{2^{p}}$

Let $\mathbb{P}$ be the set of prime numbers, and consider $m=\displaystyle\sum_{p\in\mathbb{P}} \frac{1}{2^{p}}$. Is $m$ irrational? In the following paper, the author recalls several sufficient ...
10
votes
0answers
246 views

Primes as quotients

I ask this question based on a comment of David Speyer in another question. What primes are of the form $$ \frac{p^2-1}{q^2-1} $$ where $p$ and $q$ are prime? The first prime not apparently of this ...
9
votes
0answers
89 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 ...
9
votes
0answers
242 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 ...
9
votes
0answers
268 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 ...
9
votes
0answers
159 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. ...
9
votes
0answers
178 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 ...
8
votes
0answers
246 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
428 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 ...
8
votes
0answers
408 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
180 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
194 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
248 views

Sorting of prime gaps

Let $g_n $ be the $n^{th}$ prime gap $p_{n+1}-p_n.$ If we re-arrange the sequence $ (g_n)$ so that for any finite $n$ the gaps are arranged from smallest to largest we have a new sequence ...
7
votes
0answers
83 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$. ...
7
votes
0answers
89 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 ...
6
votes
0answers
90 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 ...
6
votes
0answers
119 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
393 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 ...
6
votes
0answers
158 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
122 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} } = ...
5
votes
0answers
106 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
131 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
74 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 ...
5
votes
0answers
268 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 ...
5
votes
0answers
222 views

Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$. Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: ...
5
votes
0answers
192 views

The divergence of the series of reciprocals of primes (proof check):

I just wanted to check my attempt at a proof for the divergence of: $$\sum_{n=1}^{\infty} \frac{1}{p_n} \tag{ $\star$ }$$ We begin with assuming that $(\star)$ converges. If $(\star)$ ...
5
votes
0answers
133 views

Primes of the form $\dfrac{n^2-n+4}{2}$ satisfy Hardy-Littlewood analogue?

Let $n,a,b$ be positive integers with $a<b$. Consider primes of the form $f(n)=\dfrac{n^2-n+4}{2}$. Let $C(a,b)$ denote the amount of primes of the form $f(n)$ between (and including) $f(a)$ and ...
5
votes
0answers
156 views

Fastest Primality test using $N-1$ Factorization?

If $N-1$ could be factored easily with several small prime factors, then what is the fastest way to check $N$ for primality? Updated I'm aware of Pocklington primility test which is not good for ...
5
votes
0answers
135 views

Is the application of $\mu$ on $P_x(s)^k$ analogous to the differentiation $\frac{d^k f(\lambda) }{d\lambda^k}\biggr|_{\lambda=0}$?

Let me start with the following on elementary symmetric polynomials: The elementary symmetric polynomials appear when we expand a linear factorization of a monic polynomial: we have the identity ...
5
votes
0answers
70 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 ( ...
5
votes
0answers
208 views

Partial summation of a harmonic prime square series (Prime zeta functions)

I am trying to find the following series: $S=\displaystyle\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\dfrac{1}{p_ip_j},A\leq p_1 < p_2 < \dots < p_n \leq B, \lbrace A,B\rbrace \in \mathbb{N}$ ...
5
votes
0answers
135 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 ...
5
votes
0answers
150 views

Proof of infinitude of primes whose reversal in base 10 is also prime

Is there any proof of infinitude of http://oeis.org/A007500 primes. If you want to generate them here is trivial and naive python program. ...
5
votes
0answers
195 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 ...
4
votes
0answers
45 views

What are major algebraic number theory attempts, results and progressions toward Goldbach's Conjecture?

To my understanding, most progress toward Goldbach's Conjecture has been made in analytic number theory. Progress has often based on sieve, asymptotic estimation or other analytic methods. What are ...
4
votes
0answers
87 views
+50

Differences between large numbers with many factors has little factors

I apologise beforehand for the informality and lack of precision in this question but it is that way because it comes from only an intuition, nothing more than a heuristic argument. Say one has two ...
4
votes
0answers
154 views

Prove modular equivalence related to carmichael function.

Statement if $n=p_1p_2p_3\cdots p_r$ (prime numbers are distinct) and $2 \le a \le n-1$ then prove that $$a^{k\lambda} \equiv \left(1+\sum_{p_i\mid\gcd(a,n)}\left(\dfrac{n}{p_i} \right) ...
4
votes
0answers
53 views

Euler's proof of divergence of sum of reciprocals of primes

On Wikipedia at link currently is: \begin{align} \ln \left( \sum_{n=1}^\infty \frac{1}{n}\right) & {} = \ln\left( \prod_p \frac{1}{1-p^{-1}}\right) = -\sum_p \ln \left( 1-\frac{1}{p}\right) \\ ...
4
votes
0answers
70 views

A question about powers of prime numbers

Can someone help me in this problem? Let $p,q$ be prime numbers with $p < q$. There exists $m \in \mathbb{Z}^+$ for which $1+p+p^2+...+p^m$ is a power of $q$. There exists $n \in \mathbb{Z}^+$ ...
4
votes
0answers
58 views

Is there always a prime number in the form of $4k+1$ between $[n, 2n]$ for every large enough $n$?

Is there always a prime number in the form of $4k+1$ between $[n, 2n]$ for every large enough $n$? I guess it is known as a classical result. Is there any reference for it? Thanks!
4
votes
0answers
71 views

A bound for a certain set of prime numbers.

Let $p_n$ denote the $n^\text{th}$ prime. Find a lower bound for $\left|S\right|$ where $$S = \left\{ q \in \mathbb{N} \mid q \text{ is prime and } p_n - n \leq q \leq p_n + n \right\}. $$ Any good ...
4
votes
0answers
149 views

Understanding Newman's proof of the prime number theorem

I am trying to understand D.J. Newman's proof of the prime number theorem, as presented by D. Zagier. I am not too familiar with analysis, and so there are some things I don't understand. In (III), ...
4
votes
0answers
499 views

Obtain a contradiction

Motivation : The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
4
votes
0answers
251 views

sum of $n^{th}$ powers of prime factors of $x$

Starting with a positive integer $x$, find the sum of the $n^{th}$ powers of the prime factors of $x$, including multiplicities. Then find the sum of the $n^{th}$ prime factors of the result etc. ...
4
votes
0answers
437 views

Convergent sum with primes

If $f(n)$ is a strictly increasing elementary function from the reals to the reals, and $p(n)$ is the $n$'th prime number. Is there any $f(n)$ such that $\sum_{n=1}^\infty\frac{1}{f(p(n))}$ is ...
4
votes
0answers
328 views

Sum of odd prime and odd semiprime as sum of two odd primes?

How to prove that each sum of odd prime and odd semiprime can be written as sum of two odd primes $(p_1+p_2p_3=p_4+p_5)$ ? Since we know that each prime number greater than $3$ is of the form $6k\pm ...
4
votes
0answers
273 views

Prime zeta definition, multiplication by zero

Wikipedia has a page about the prime zeta function which is defined as follows: $$P(s)=\sum_{p\;\text{prime}} \frac1{p^s}$$ I entered this additional definition: Define a sequence: ...
3
votes
0answers
26 views

Is it possible to sum the divergent series with prime coefficients?

This is a follow-up of this question. It is known that the divergent series $$ P := \sum_{n=1}^\infty p_n \qquad \text{where } p_n \text{ is the $n$th prime} $$ cannot be summed by means of (prime) ...