Prime numbers are natural numbers greater than 1 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

19
votes
0answers
543 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) = \sum_{n=...
18
votes
0answers
544 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 ...
17
votes
0answers
319 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 ...
17
votes
0answers
422 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 ...
15
votes
0answers
230 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. ...
14
votes
0answers
178 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 ...
14
votes
0answers
131 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 ...
12
votes
0answers
181 views

Have I discovered an analytic function allowing quick factorization?

So I have this apparently smooth, parametrized function: The function has a single parameter $ m $ and approaches infinity at every $x$ that divides $m$. It is then defined for real $x$ apart ...
12
votes
0answers
103 views

Consecutive prime numerators of harmonic numbers?

Let $$\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}=\frac{a}{b}$$ and let $a$ and $b$ are coprime, $h_{n}=a$. $h_{n}$ is prime for $$n=2,3,5,8,9,21,26,41,56,62,69,79,89,91,122,127,143,...
11
votes
0answers
450 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 ...
11
votes
0answers
253 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 $f(p)=\...
11
votes
0answers
625 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 ...
10
votes
0answers
125 views

Finding $1/x^2 + 1/x^3 + 1/x^5 + \dots $

The following function came up in my work: $$ f(x)=\sum_{p\text{ prime}}\frac{1}{x^p}=\frac{1}{x^2}+\frac{1}{x^3}+\frac{1}{x^5}+\frac{1}{x^7}+\frac{1}{x^{11}}+\cdots. $$ Naturally, this converges for ...
10
votes
0answers
170 views

Are my calculations of a new constant similar to Mill's constant based on $\lfloor A^{2^{n}}\rfloor$ and Bertrand's postulate correct?

As Wikipedia explains in number theory, Mills' constant is defined as: "The smallest positive real number $A$ such that the floor function of the double exponential function $\lfloor A^{3^{n}}\...
10
votes
0answers
180 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
468 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 n^{\frac{1}{k}}\...
9
votes
0answers
91 views

For any $x\in \mathbb{N}$ does there exist $m\in \mathbb{N}$ such that $2x+1+2m, 2x+1+4m$ are both prime?

Could someone please give me a proof (or counter example) for this (I believe it is true): For any $x$ (Whole Number) there exists some $m$ (Also Whole) such that $2x+1+2m$ and $2x+1+4m$ are both ...
9
votes
0answers
362 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
373 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 ...
9
votes
0answers
146 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! + 1$...
9
votes
0answers
127 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 ...
9
votes
0answers
137 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 ...
9
votes
0answers
261 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 t}+\sum_{x\...
9
votes
0answers
122 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 ...
9
votes
0answers
242 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 ...
8
votes
0answers
65 views

Number of primitive roots mod $p$ that are not primitive roots mod $p^2$

Consider the primitive roots of a prime $p$ in the range $1...p$ which are not primitive roots mod $p^2$. Let $n(p)$ be this number. While looking for an answer to this question, it seems that the ...
8
votes
0answers
95 views

Generalizing the growth of sums of two squares

Consider the set $S$ of numbers which are the sum of two (integer) squares, and define $S(n)$ as the number of members of $S$ in $\{1,2,\ldots,n\}.$ It is well-known that $$ S(n) \sim \frac{Kn}{\sqrt{\...
8
votes
0answers
78 views

Differences of Prime Numbers

Let $a<b<c$ be primes such that $c-a$, $c-b$, and $b-a$ are also prime. It is rather simple to show that $(2,5,7)$ is the only triple that satisfies these conditions: Proof Sketch: The case $...
8
votes
0answers
215 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 ...
8
votes
0answers
211 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 ...
7
votes
0answers
83 views

Which prime factors of $8^{8^8}+1$ are known?

We have the partial factorization $$8^{8^8}+1=(2^{2^{24}}+1)\cdot (2^{2^{25}}-2^{2^{24}}+1)$$ The first factor is $F_{24}$. It is composite, but no prime factor is known. A prime factor of the ...
7
votes
0answers
60 views

To what extent can the fondamental theorem of arithmetic be used to give a canonical form to non-integer numbers?

The fundamental theorem of arithmetic gives us a unique way of writing any non-zero integer. For any $n \in \mathbb{Z}^*$, we have a unique decomposition : $$n = (-1)^\epsilon \prod\limits_{i \in \...
7
votes
0answers
218 views

Basic Olympiad number theory problem about prime numbers

I'm learning a basic lesson of number theory and get stuck with this : Find all positive integers $n$ and prime numbers $p$ such that $n^p+3^p$ is a perfect square. I found that if $p \ge 3$, then $...
7
votes
0answers
146 views

Primes $p$ for which $2p \pm 1$ are also primes

Out of curiosity and trouble sleeping, I decided to look at the distribution of primes $p$ for which $2p \pm 1$ are also primes. I looked at the first 25,910,000 primes and counted the number of ...
7
votes
0answers
206 views

Where is The third Gisella prime?

A Gisella prime is a prime number obtained from concatenating the first $n$ natural numbers starting from $2$ and then replace each composite on that concatenation with the concatenation of its prime ...
7
votes
0answers
132 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 ...
7
votes
0answers
86 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 $f^k(n)=\...
7
votes
0answers
192 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 - ...
7
votes
0answers
145 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 ...
7
votes
0answers
226 views

The effect of roots of Dirichlet's $\beta$ function condenses to $\frac12\left(1+ie^{i2\pi\frac{p}4}\right)$

With the help of Raymond Manzoni and Greg Martin I was able to derive an explicit formula for the number of primes of the form $4n+3$ in terms of (sums of) sums of Riemann's $R$ functions over roots ...
7
votes
0answers
926 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
195 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 ...
7
votes
0answers
310 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 ...
6
votes
0answers
68 views

Does every power of two arise as the difference of two primes?

Conjecture: For each $n\in\mathbb N$ there are primes $q<p$ with $p-q=2^n$. Verified for $n\leq 26$: ...
6
votes
0answers
62 views

The Greatest Common Divisor of All Numbers of the Form $n^a-n^b$

For fixed nonnegative integers $a$ and $b$ such that $a>b$, let $$g(a,b):=\underset{n\in\mathbb{Z}}{\gcd}\,\left(n^a-n^b\right)\,.$$ Here, $0^0$ is defined to be $1$. (Technically, we can also ...
6
votes
0answers
199 views

Prime Powers and Differences of Consecutive Cubes

I am wondering if it has been proven that there does not exist a prime $p$ and an integer $r \ge 3$ such that $p^r = (n + 1)^3 - n^3$ for some integer $n$. Note that this is a special case of Beal's ...
6
votes
0answers
57 views

A rash guess about distribution of primes based on meager empirical evidence?

Between the prime numbers $n=1327$ and $n+k = 1327+34 = 1361$ there are $k-1=33$ consecutive composite numbers. If you double those bounding primes, getting $2\times1327=2654$ and $2\times1361=2722$, ...
6
votes
0answers
83 views

Largest prime known to ancients

As is well known, Fermat couldn't check the primality of $F_{5} = 2^{2^{5}} + 1$. This raises an interesting question : what was the largest prime number that was known to ancients (particularly ...
6
votes
0answers
97 views

Twin-prime sieve

My question concerns the following sieve (call it S), which was an exercise in applying some elementary aspects of Brun's sieve while reading Halberstam's text. Using the Chinese Remainder theorem ...
6
votes
0answers
99 views

On the change $u=x^{1+\frac{1}{p_n}}$ in $\log \zeta(s)=s\int_0^\infty\frac{\pi(x)}{x(x^s-1)}dx$, where $p_n$ is the nth prime number

In [1] Wikipedia say that for $\Re s>1$ the Riemann zeta function satisfies $$\log \zeta(s)=s\int_0^\infty\frac{\pi(x)}{x(x^s-1)}dx,$$ where $\pi(x)$ is the prime counting function, and say too ...