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.
2,020
questions
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 ...