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
318 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
238 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
76 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
124 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$. ...
9
votes
0answers
157 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. ...
8
votes
0answers
184 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 ...
8
votes
0answers
261 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 ...
8
votes
0answers
245 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
168 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
411 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
403 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
177 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
191 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
202 views

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

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 ...
7
votes
0answers
85 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
76 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$. ...
6
votes
0answers
89 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
117 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
157 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
120 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
129 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
73 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
217 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
188 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
367 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 ...
5
votes
0answers
132 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
134 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
205 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
134 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
191 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
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
54 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
497 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
248 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
426 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
324 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
272 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
71 views

The n-envelope problem

This is original problem: You have n number of envelopes, and 100 $1 bills. you have to put these bills in the envelopes in such a way that any amount between 1 to 100 can be reached just by ...
3
votes
0answers
49 views

An Inequality with Prime Numbers

Let $m\geq 8$ be an integer, and let $q$ be the smallest prime that is greater than $m$. Let $p$ be a prime that satisfies $q\leq p<q^2$, and let $p_0$ be the smallest prime such that ...
3
votes
0answers
61 views

Resources about infinite primes of form $n^2 + 1$

Where can one find existing work on the following problem? Prove there are infinitely many primes of the form $n^2 + 1$. Resources about related work would also be appreciated.
3
votes
0answers
33 views

Prime Triangle:: How to find the position(row and column) of prime number in a triangular arrangement

I was working on problem which asks the position of a prime number in a triangular arrangement. If we arrange the all prime up to 10^8 as shown in image we can find the row and column number of a ...
3
votes
0answers
46 views

Solution of a equation in natural number nvolving reciprocal of prime

Let $p$ be a prime and $n$ a natural number . Solve in $\mathbb{N}$ the equation $$\sum_{k=1}^{n}\frac{1}{x^k_k}=\frac{1}{p}$$
3
votes
0answers
89 views

Sum of product partitions of divisors

Let $M(n)$ be the the set of the multiplicative partitions of $n$, and let $D(n)$ be the set of the sum of the multiplicative partitions of the divisors of $n$. eg $M(30)=\{\{30\},\{2,15\},\{3, ...