Questions tagged [prime-numbers]

Questions where prime numbers play a key-role, such as: questions on the distribution of prime numbers (twin primes, gaps between primes, Hardy–Littlewood conjectures, etc); questions on prime numbers with special properties (Wieferich prime, Wolstenholme prime, etc.). This tag is often used as a specialized tag in combination with the top-level tag nt.number-theory and (if applicable) analytic-number-theory.

Filter by
Sorted by
Tagged with
1 vote
1 answer
184 views

Comparing densities of different gapped primes (twin, cousin, sexy...) [closed]

In this experiment, I have checked how many times different gapped primes occur out of the first 10000, 100000, 1000000 first primes. Please view the following as ($X$:$Y$) where $X$ represents the ...
4 votes
0 answers
209 views

What is the complexity class of this problem without Cramer's conjecture?

The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
1 vote
0 answers
202 views

Construction of weight function to satisfy condition on given functional

Consider the following function : $$F(z) = \omega(z){\sin^2\left(\frac{c\Gamma(z)}{z}\right)}$$ Here, $\omega(z)$ is a weight we are going to consider The following two conditions should meet for $\...
1 vote
0 answers
150 views

Numbers whose digits, in order, display prime factors

There's a post in CodeGolf which asks for code to find numbers whose digits contain their prime factors without rearrangement. The author suggests the mathematical definition is "Determine if ...
4 votes
3 answers
765 views

Goldbach conjecture and the representation number

Let $g(2n)$ be the number of representations of $2n=p+q$ with primes $p$ and $q$. Many people have asked whether $g(2n) \ge 2$ when $2n = p+q$ for some primes $p$ and $q$. That is, does $g(2n) \ge 1$ ...
8 votes
6 answers
1k views

How many solutions are there to the equation $x^2 + 3y^2 \equiv 1 \pmod{p}$?

Let $p$ be a prime. How many solutions $(x, y)$ are there to the equation $x^2 + 3y^2 \equiv 1 \pmod{p}$? Here $x, y \in \{0, 1, \ldots p-1\}$. This paper (https://arxiv.org/abs/1404.4214) seems like ...
0 votes
1 answer
247 views

How differently would we model the distribution of primes if prime gap is larger?

Cramer's conjecture based on his random model provides prime gaps are bound by $O(\log^2p_n)$ where the gap is between $(n+1)$th and $n$th prime. How differently would primes be modeled if gaps of $O(...
0 votes
0 answers
91 views

On a generalised result of Mertens

Let $\varphi$ be the Euler totient function, $N_k$ denote the product of the first $k$ primes and define $$f(k, r) = \frac{(N_k)^r}{\varphi((N_k)^r) \log \log ((N_k)^r)}.$$ where $r \in \mathbb{N}$. ...
10 votes
1 answer
532 views

Does every geometric progression contain a small remainder modulo a large prime?

The exact question I am interested in is the following. Fix a small $\varepsilon\in(0,1)$ and an integer $q\ge 2$ (you may assume that $q$ is prime if it helps though I believe it shouldn't matter too ...
0 votes
1 answer
87 views

What are the complexity classes of these problems about divisibility and coprimality?

The problems 'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?' 'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
6 votes
1 answer
341 views

Prove or disprove that $\sup_{n\in\mathbb{N}}\left|\sum_{\substack{d|n \\d<Q}}\mu(d)\right|\sim\pi(Q)$

To begin, let us set $$A_Q(n):=\sum_{d|n \\ d<Q}\mu(d)$$ If we fix $Q$ and let $n$ vary, we get a very surprising amount of cancellation. For instance, the trivial bound \begin{align*} \mathbb{E}_{...
0 votes
1 answer
101 views

Are there any solutions to this congruence system

Let $p,q_i,i=1,2,..m$ be odd primes with integer $m>2$ Does this system of congruences have any solutions? $\prod_{i=1}^m(q_i-1)\equiv2(p^2)$ $\prod_{i=1}^mq_i\equiv2(p^3)$
9 votes
1 answer
353 views

On the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo $p^2$

Let $p$ be an odd prime. It is well-known that $$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$ I'm curious about the behavior of the permanent $\text{per}[i^{j-...
3 votes
2 answers
785 views

Density of the set of numbers whose sum of digits is prime

Let $A$ be the set of numbers whose sum of digits is prime (http://oeis.org/A028834). I would like to know if $A$ has zero natural density, that is, if $$\lim_{n \to +\infty} \frac{A(n)}{n} = 0,$$ ...
3 votes
0 answers
108 views

Generalizing Mersenne prime search to cyclotomic prime

The Mersenne prime $M_p=2^p-1$ can be expressed as $M_p=\Phi_p(2)$ where $\Phi_m(x)$ is a cyclotomic polynomial. It seems useful to generalize the Mersenne prime search to more general cyclotomic ...
0 votes
1 answer
133 views

Search for gaps between primes where each composite is divisible by increasing integers (2, 3, 4, ...)

Almost every text of number theory contains in its first chapters something similar to the following: For any integer n, the factorial n! is the product of all positive integers up to and including n....
1 vote
0 answers
81 views

An upper bound for $\,m_k=\min\,\{m\in N:\,mp_k+1\;\;is\;prime\}$

For each prime $p_k$ one can define $$m_k=\min\,\{m\in N:\,mp_k+1\;\;is\;prime\}$$ Some computations suggest that $$m_k=O\Big(\frac{2\sqrt k}{\log k}\Big)$$ Is this estimate confirmed by analytic ...
10 votes
0 answers
201 views

Does the diophantine equation $\,\prod_{k=1}^n(p_k^{x_k}-1)=y^2\,$ have always at least a solution for $\,n\gt2\,$?

P.G.Walsh proved in this paper that the diophantine equation $\,(2^{x_1}-1)(3^{x_2}-1)=y^2\,$ has no solution in positive integers $\,x_1$, $\,x_2\,$ and $\,y$. If we generalize the previous equation ...
-1 votes
1 answer
236 views

A number theoretical identity of exponential sum

I try to understand a number theoretical identity used by Jan-Christoph Schlage-Puchta in this answer. He defined the function $$S(\alpha)=\sum_{n\leq N}\Lambda(n) e(n\alpha)$$ where $\Lambda(n)$ is ...
2 votes
0 answers
54 views

Asymptotic growth of the collection of Miller-Rabin pseudo-primes witnessed by a set

Consider a set $S$ of positive integers[*]. Define $P(S)$ as the set of numbers $N$ for which elements of $S$ are "witnesses" for the Miller-Rabin test for primality of $N$. Explicitly $P(S)=...
0 votes
1 answer
158 views

Mapping from prime pairs to non prime pairs

Inspired by MSE post, I propose the following generalization: Is the following statement always true? Consider $n$ and $m$ are non negative Integers. Let $p$ and $q$ are prime with $q=p+6n+2$ then ...
8 votes
1 answer
714 views

An alternative to continued fraction and applications

This post is inspired by the Numberphile video 2.920050977316, advertising the paper A Prime-Representing Constant by Dylan Fridman, Juli Garbulsky, Bruno Glecer, James Grime and Massi Tron Florentin, ...
1 vote
1 answer
351 views

Primality test for numbers of the form $4k+3$

Can you prove or disprove the following claim: Let $n$ be a natural number of the form $4k+3$ , and let $c$ be the smallest odd prime such that $\binom{c}{n}=-1$ , where $\binom{}{}$ denotes a Jacobi ...
0 votes
1 answer
184 views

Are there some results which count $\sum_{p\in [x/2,x]} \log p$ or $\sum_{p\in [x,y]} \log p$ for for $x$ and $y$ positive and real?

I have seen the prime number theorem and on the of versions I know is that $\sum_{p\leq x} \log p=O(x)$ (I am counting over primes here and in the rest of the post). Are there any similar results for ...
2 votes
0 answers
289 views

Proving that the Riemann zeta function is zero free on Re=1 using the prime number theorem

Is $\frac{-\zeta'(s)}{\zeta(s)}+\frac{-s}{s-1}$ an analytic continuation, holomorphic for $Re\ s > 0,\ s\neq 1$, of $f(s)=s\int_{1}^{\infty}\frac{\psi(x)-x}{x^{s+1}}\mathrm{d}x$? If so: Let $s_{0}$ ...
2 votes
0 answers
94 views

How far ahead do we have to look after $p_n$ to be sure we find another prime $q$ such that $(p_n+q)/2$ is also prime?

If Goldbach's conjecture is true, given a prime $p_n$ is surely possible to find another prime $q$ such that $\frac{p_n+q}2$ is also prime. But I ask: how far ahead do we have to look after $p_n$ to ...
2 votes
0 answers
219 views

Is this limit zero?

Define $e(\theta)=e^{2\pi i\theta}, \theta\in [0,1]$, $P_n=\{p_1,p_2,...,p_n\}$ are the first $n$ primes, $\|f\|_1=\int_{[0,1]}|f(\theta)|d\theta$. Problem 1. is it true for all fixed $m\in \mathbb{N^...
1 vote
1 answer
569 views

If $\gcd(x,y)=1$ find necessary and sufficient condition(s) such that $\gcd (x-1,y-1)>1$

Let, $xy=n^{\underline k} = n(n-1)(n-2)\cdot\dotsm\cdot (n-k+1)$ and it is given that $ \gcd(x,y)=1$ with one of $x$, $y$ is odd, another is even. When is $\gcd (x-1,y-1)=z>1$? In other words, what ...
7 votes
2 answers
827 views

Prime numbers in a sparse set

Is there any set $X$ which is a density 0 subset of $N^*$ and we already know that there are infinitely many primes in it, beside examples which come from $x^2+y^4$(or its proof)? Problem1: In ...
0 votes
0 answers
134 views

A conjectural limit involving primorial and factorial

It is well known that the abc conjecture implies that the there are only finitely many solutions to Brocard problem, as shown by Overholt in Overholt, Marius (1993), "The diophantine equation $n! ...
-1 votes
1 answer
108 views

Does one have $2r_{0}(n)\lesssim k_{0}(n)(\log n)^{1+1/k_{0}(n)}$?

Under Goldbach's conjecture, I'm trying to find an upper bound for $r_{0}(n):=\inf\{r>0,(n-r,n+r)\in\mathbb{P}^{2}\}$ that would generalize Cramer's conjecture. Denoting by $k_{0}(n)$ the quantity ...
0 votes
0 answers
73 views

Order of growth of the error term of the log-exponent of the average prime gap

Disclaimer: I might have already asked this question or a very similar one but couldn't find it if it is so. Hope it will be judged somehow interesting anyway. Assuming Goldbach's conjecture, let's ...
10 votes
0 answers
263 views

On the infinity of $\{p\in \mathbb {N}:\exists n\in\mathbb{N}~p| \left \lfloor{r^n}\right \rfloor\}$

I've already asked this same question on MSE here, but didn't get much help, so I will try on this site as well. For which $r\in\mathbb{R}$ is the set $\mathscr{P}_r=\{p \in \mathbb{P}:\ (\exists n\...
1 vote
1 answer
149 views

On the maximal power of $2$ that divides a colossally abundant number

Let $n>36$ be some colossally abundant number. Then $n$ must have a prime factorisation of the form $2^{a_1}3^{a_2}\cdots {p_i}^{a_i}$, where $a_{1} \geq a _{2} \geq \cdots \geq a_i \geq 1$. What ...
12 votes
3 answers
559 views

Is $\Bigl\{ n \sum_{k=2}^{n-1} \frac{1}{k}\Bigr\}$ unique $\forall n \in \Bbb{N}, n>1$

If we define $$f(n) = \Bigl\{ n \sum_{k=2}^{n-1} \frac{1}{k}\Bigr\}$$ is it true that $f(n) \ne f(m)$ whenever $n \ne m, \forall m,n \in \Bbb{N}$ (where the curly braces denote the fractional part)? I ...
2 votes
0 answers
109 views

A conjectured upper bound for the mean value of prime divisors inside prime gaps

In 1969 C.A. Grimm stated this interesting conjecture: the prime gap $\,G_n=\{x\in N:p_n\lt x\lt p_{n+1}\}\,$ contains at least $\,\#G_n=(p_{n+1}-p_n)-1=g_n-1\,$ distinct prime divisors, that is if $\,...
2 votes
0 answers
399 views

Sequences with high densities of primes: how to boost them to get even more and larger primes

I propose a methodology to help find large prime numbers with a much higher probability than picking up random numbers and testing them for primality. This would help speed up prime number generators ...
1 vote
0 answers
138 views

Equation $\,\ N^d\pm 1\ =\,\ p_m\cdot\ldots\cdot p_n$

Notation: $\ p_0=2,\ p_1=3,\ p_2=5, \ldots\ $ -- the increasing sequence of all primes. (The following questions, once I've formulated them, remind me of Chebyshev). A very special case of a power $\...
4 votes
1 answer
377 views

Mertens formulas aren't enough for prime number theorem

For the primes it's true that $$ \sum_{p \le x}\frac{1}{p} = \ln\ln x + M + O(1/\ln x) $$ where, $M$ is suitable constant, and, moreover, the prime number theorem gives that $$ \lim_{x\to\infty}\frac{\...
5 votes
1 answer
240 views

Does $0<k<n$ imply $p_{n+k}<\left(1+\frac{1}{k}\right)^k p_{n}$ for large enough $n$?

Disclaimer: a stronger version of this question was first asked on MSE: https://math.stackexchange.com/questions/3896547/does-p-nk1-frac1kk-p-n-whenever-0kn/3896842#3896842 and on a French math forum ...
7 votes
2 answers
608 views

How to use the Prime Number Theorem in order to prove Selberg's Formula?

I`m reading Melvin B. Nathanson's "Elementary Methods in Number Theory" and I can't think of a way of deducing Selberg's formula (9.3) from the prime number theorem. This is one of the tasks ...
4 votes
1 answer
366 views

A question on bi-character of finite abelian group

Setting: $G$ is a finite abelian group and any bicharacter on $G$, where a bi-character on $G$ is a map $b:G \times G \to \mathbb{Q}/\mathbb{Z}$ such that $$b(x+y,z)=b(x,z)+b(y,z),b(x,z+y)=b(x,z)+b(x,...
26 votes
1 answer
3k views

A surprising conjecture about twin primes

Just for fun, I began to play with numbers of two distinct ciphers. I noticed that most of the cases if you consider the numbers $AB$ and $BA$ (written in base $10$), these have few common divisors: ...
4 votes
1 answer
395 views

Quadratic progressions with very high prime density

In my previous MO question (see here), I solved the case for arithmetic progressions $f_k(x)=q_k x+1$. The solution is this: The list of sequences $f_k(x)$, each one corresponding to a specific $k$, ...
6 votes
3 answers
983 views

Does this 'alternating' Euler product converge for all $\Re(s) > 0$?

Does the following 'alternating' Euler product, with $p_n$ the $n$-th prime number, converge for $\Re(s)>0$ ? $$\displaystyle \prod_{n=1}^\infty \left( \dfrac{1}{1-\frac{1}{p_{n}^{s}}} \right)^{(...
4 votes
1 answer
523 views

Asymptotics for $\prod(1-\frac{1}{p})$ over all primes $p\leq x$ with $p \equiv 3 \bmod 4$

Let us define the following functions: \begin{equation*} \small A(x)=\prod_{\substack{p\leq x\\ p\equiv 3 \bmod 4}} \Big(1-\frac{1}{p}\Big), \mbox{ } \mbox{ } B(x)=\prod_{\substack{p\leq x\\ p\...
4 votes
1 answer
280 views

Question on an analytic number theory paper

My question is just a ``I don't understand what goes on in X of paper Y" so I don't know if I can post it; on the other hand it is research. I posted it in stackexchange but it received no ...
1 vote
0 answers
185 views

Generalized Thomas Ordowski conjecture at OEIS sequence A002326

OEIS is the online encyclopedia of integer sequences, Here is the link to the sequence $A002326$: https://oeis.org/A002326 For $n\geq 0$, the $n$th term in the sequence is defined as: $a(n)$ equals ...
0 votes
1 answer
174 views

Explanation of unexpectedly large offset of the first occurrence of five consecutive zeroes in the sequence of second-to-last bits of primes

Assuming that $x$ is a real number, the function $f_n(x)$ is defined as follows: the value of $f_n(x)$ is equal to the number of bits before the first occurrence of $n$ consecutive zero bits in the ...
68 votes
1 answer
3k views

Iterations of $2^{n-1}+5$: the strong law of small numbers, or something bigger?

I've discovered what I believe is a quite remarkable sequence (A318970), defined by $$n_1 = 3,\qquad n_{k+1} = 2^{n_k-1}+5\quad(k\geq 1).$$ Here are the first four terms with their prime ...

1
10 11
12
13 14
41