Questions tagged [prime-numbers]

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.

1,820 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
69
votes
0answers
2k 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 ...
40
votes
0answers
1k 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 ...
33
votes
0answers
513 views

Can we remove any prime number from this strange process?

This is a little algorithm I made today, which may appear to be quite complex, so I will start with an example. Questions are at the end of the post. The process goes as follows: Start with the ...
26
votes
0answers
715 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 ...
24
votes
0answers
411 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. ...
23
votes
0answers
747 views

Does the average primeness of natural numbers tend to zero?

Note 1: This questions requires some new definitions, namely "continuous primeness" which I have made. Everyone is welcome to improve the definition without altering the spirit of the question. Click ...
23
votes
0answers
545 views

Determinant of a matrix that contains the first $n^2$ primes.

Let $n$ be an integer and $p_1,\ldots,p_{n^2}$ be the first prime numbers. Writing them down in a matrix $$ \left(\begin{matrix} p_1 & p_2 & \cdots & p_n \\ p_{n+1} & p_{n+2} & \...
22
votes
0answers
667 views

Stronger versions of Wilson's Theorem

Problem Let $c \in \mathbb{N}$ $;$ $\exists$ a prime $p$ for which: $$p^c \mid (p-1)!+1$$ Does $\exists$ $M$ $\in$ $\mathbb{N}$ $;$ $\forall$ $c \geqslant M$ $;$ $\nexists$ $p$ ...
22
votes
0answers
522 views

Are there infinitely many primes of the form $12345678901234567890\dots$

Related to this question, What is the smallest prime number made of sequential number? are there infinitely many primes of the following form (OEIS A057137)? $1, 12, 123, 1234, 12345, 123456, ...
20
votes
0answers
508 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 from ...
18
votes
0answers
397 views

Does the sum of reciprocals of all prime-prefix-free numbers converge?

Call a positive integer $n$ prime-prefix-free if for all $k \ge 1$, $\lfloor \frac{n}{2^k} \rfloor$ is not an odd prime. (Odd because otherwise the property is trivial, as every integer greater than ...
17
votes
0answers
1k views

Finding a better approximation to a prime number relation

The basis of this problem, and that which allows for the approximations to be made here, can be summarised in one approximation: $$\Biggl(\frac{n^k -{\lfloor n^{\frac{1}{k}} \rfloor}^{k-1}\gcd({\...
16
votes
0answers
202 views

The famous prime race and generalizations

So I was messing around with the famous prime race that comes down to this: We make a list of primes. The list has two rows; the top row is for primes $1\mod 4$ and the bottom row for primes $3\mod 4$...
15
votes
0answers
192 views

Is every finite list of integers coprime to $n$ congruent $\pmod n$ to a list of consecutive primes?

For example the list $(2, 1, 2, 1)$ is congruent $\pmod 3$ to the consecutive primes $(5, 7, 11, 13)$. But how about the list $(1,1,1,1,1,1,1,1,2,3,4,3,2,3,1) \mod 5$? More generally, we are given ...
15
votes
0answers
1k views

Matrix generated by prime numbers

Let $p$ be the vector of dimension $n^2$ consisting of ordered prime numbers i.e. $p= [ 1 \ 2 \ 3 \ 5 \ 7 \ldots]^T$ and $A$ be the matrix of dimension $n\times{n}$ constructed with this vector by ...
15
votes
0answers
190 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,...
15
votes
0answers
908 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 ...
14
votes
0answers
211 views

Why is 2 so troublesome a prime?

I have been asking to myself for a while now why $2$ has such an exceptional behaviour in algebraic number theory. For example, the Kronecker-Weber Theorem proof was completed for all cases but that ...
13
votes
0answers
562 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 exercise ...
13
votes
0answers
675 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 ...
13
votes
2answers
235 views

Sets of Prime Numbers Generated By an Irreducible Monic Polynomial

Given a non-constant integral irreducible monic polynomial $f(x)$, the prime factors of its value at integers $x\in\mathbb{N}$ forms a set $\mathcal{P}(f)$. Is it possible that $\mathcal{P}(f)\cap\...
12
votes
0answers
237 views

Why is counting the number of least prime factors of a sequence of consecutive integers insufficient to resolve Legendre's Conjecture?

I've been thinking a long time about Legendre's Conjecture. A few nights ago, I came across the following argument which is of course too simple to be true. I would greatly appreciate if someone ...
12
votes
0answers
155 views

Is $\sqrt p - \lfloor\sqrt p\rfloor$, $p$ running over primes $1 \pmod 4$ , dense in $[0,1]$?

A result I would like to know is if there are infinitely primes congruent to $1 \pmod 4$, with fractional part in an interval strictly contained in $\left(0, \dfrac 1 4 \right)$. The title question ...
12
votes
0answers
529 views

More elegant $\zeta(s)$ zeros counting function than $N(T)$

The explicit formula expresses the deep connection between the primes $p$ and the non-trivial zeros $\rho$ of $\zeta(s)$. The prime-counting function is given by the following formula giving primes in ...
12
votes
0answers
194 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$: ...
12
votes
1answer
233 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 ...
12
votes
0answers
346 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
203 views

Are $(2,28)$ and $(5,3207)$ the only solutions $(m,n)\in\mathbb{N}^2$?

I noticed something as I was playing around with prime numbers. By denoting $p_i$ the $i^{\text{th}}$ prime number, I discovered the following: $$ \begin{align}\prod_{i=1}^2\left(p_i^{ \ 2}+i\right)&...
11
votes
0answers
319 views

Does Chaitin's constant have infinitely many prime prefixes?

Define $f(n) = \lfloor 2^n \cdot \Omega \rfloor$, that is, $f(n)$ is the first $n$ bits of Chaitin's constant interpreted as a number written in binary. I am trying to figure out if $f(n)$ can have ...
11
votes
0answers
457 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 ...
11
votes
0answers
304 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 ...
10
votes
0answers
319 views

Is $\lfloor \zeta(-n) \rfloor$ only prime for $n=23$?

I searched for primes of the form of $\lfloor \zeta(-n) \rfloor$, where $n \in \Bbb{N}$, for a range of $n \le 10^4$ on PARI/GP and found $\lfloor \zeta(-n) \rfloor$ is only prime for $n=23$. My ...
10
votes
1answer
470 views

A non-composite sequences

Can you provide a counterexample for a claim given below? Inspired by Puzzle 937 I have formulated the following claim: For any $n > 0$ let $B = p_1 \cdot p_2 \cdot .... \cdot p_n$ be the ...
10
votes
0answers
318 views

How many primes does this sequence find?

The sequence in question is: $$S=\left\{\int_0^1\pi(x)\pi(1-x)dx,\int_0^2\pi(x)\pi(2-x)dx,...\right\},$$ where $\pi(x)$ is the prime counting function. I don't know how to check this for an ...
10
votes
0answers
239 views

Is there an elementary argument for $\prod\limits_{p \le n}p < 3^n$ where $p$ is prime.

I was reading Hanson's proof that $\prod\limits_{p^a \le n}p^a < 3^n$ where $p$ is a prime and it occurred to me that there might be a simpler argument for $\prod\limits_{p \le n} p < 3^n$. Am ...
10
votes
1answer
224 views

Considering the equation, $6 + (2k+1)\sum_{n=1}^{2k+1}p_n^{ \ \ 3}(-1)^{n+1} = x^2$.

I noticed that, $$\begin{align}3(2^3 - 3^3 + 5^3) + 6 &= 18^2 \\ \text{and } \qquad 5(2^3 - 3^3 + 5^3 - 7^3 + 11^3) + 6 &= 74^2.\end{align}$$ These equations are of the form, $$6 + (2k+1)\sum_{...
10
votes
0answers
195 views

$\gcd(p_{n-1}, \ n^5 - n^3 + n^2 - n + 1) = 1$ where $p_n = n$th prime.

How can I prove in general that, for all $n\geq 2$: $$ \gcd(p_{n-1}, \ n^5 - n^3 + n^2 - n + 1) = 1 $$ Seems to always be true: ...
10
votes
0answers
343 views

Does the sequence $x_0=12$ , $x_{n+1}=x_n^2+1$ contain a prime?

I wonder whether the sequence defined by $$x_0=12$$ $$x_{n+1}=x_n^2+1$$ for all non-negative integers $n$ contains a prime number. The following table shows from left to right : The index $n$ , the ...
10
votes
0answers
182 views

Can the sum of powers of the first primes be a square?

Let $p$ be a prime and $u\ge 1$ be a positive integer. Define $$\begin{align} S(p,u) &:= \sum_{q\text{ prime, }q \le p} q^u \\ &= 2^u+3^u+\cdots +p^u\end{align}$$ I wonder whether $S(p,u)$ ...
10
votes
0answers
131 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 ...
10
votes
0answers
154 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{\...
10
votes
1answer
160 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 $a&...
10
votes
0answers
718 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 N is either prime or else lies halfway between two primes A and B, where A <...
10
votes
0answers
300 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\...
10
votes
0answers
167 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 ...
10
votes
0answers
527 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}}\...
10
votes
0answers
565 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 ...
9
votes
0answers
258 views

Dissecting the complexity of prime numbers

Each prime number greater than $9$, written in base $10$, ends with one of the four digits $1,3,7,9$. Therefore, each ten can be classified according to which of these four digits, summed to the ten, ...
9
votes
1answer
154 views

Are there further primes of the form $\varphi(n)^{\varphi(\varphi(n))}+1$?

For positive integers $n$ , define $$f(n):=\varphi(n)^{\varphi(\varphi(n))}+1$$ where $\varphi(n)$ denotes the totient function. According to my calculation, for the following positive integers $n$ , ...
9
votes
0answers
142 views

Polynomial detecting congruence conditions

It is well-known that a prime number $p$ is $\equiv 1 \pmod 4$ iff $p=x^2+y^2$ for some integers $x,y$ (except for $p=2$). My question is: is there an irreducible homogeneous polynomial $f \in \Bbb Z[...