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
4 votes
1 answer
590 views

Geometric mean of prime factors of all numbers up to n

Through numerical calculations I have discovered that for any natural number $n \geq 2$, the geometric mean of the prime factors of all natural numbers $\leq n$ can be approximated well by $1.6653 \...
10 votes
2 answers
778 views

Is there a two-variable prime-representing polynomial (in the sense of Jones-Sato-Wada-Wiens)?

In the math.se question Proof of no prime-representing polynomial in 2 variables, Alon Amit asks if Ribenboim's claim that a prime-representing polynomial (a Diophantine polynomial in which the ...
9 votes
1 answer
2k views

What keeps asymptotic Goldbach's conjecture out of reach of current technology?

Despite the rather recent progress in prime number theory (see the proof of the ternary Goldbach conjecture by H.A. Helfgott, and the striking result of Yitang Zhang improved by Tao, Maynard and ...
11 votes
2 answers
497 views

Jacobi symbols for two-square sums of primes

Given a prime $p\equiv 1\pmod 4$, Fermat's two-squares theorem discovered by Girard states that there exists two integers $A,B$ such that $p=A^2+B^2$. For all primes up to $10^7$ the integers $A$ and $...
2 votes
0 answers
105 views

How to know if a random natural number is a probable semiprime?

Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
0 votes
0 answers
78 views

Obstacles to computing $\pi(n)$ in $O(n^{2/3-\epsilon})$ time

Edit: Apologies, as mentioned in the comments I failed to notice the analytic algorithms that take $O(n^{1/2+\epsilon})$ time, so this question doesn’t make much sense. It’s possible there is a ...
12 votes
2 answers
987 views

Prime differences and zero multiplicity

Concerning gaps between consecutive primes, Paul Erdős conjectured that: $$\sum_{p_n < x} (p_n -p_{n-1})^2 = O(x \log x)$$ Let's call this hypothesis EH. Assuming the Riemann hypothesis (RH), ...
1 vote
0 answers
57 views

Primality testing by reversible computation using the prime number theorem

Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
1 vote
0 answers
64 views

Tuples of natural numbers with no mutual divisibility and large reciprocal sums

Standard apology in case this is something simple, as I'm not a number theorist. Let $E_1, \dots, E_n$ be disjoint finite sets of natural numbers, such that for any $a_1 \in E_1, \dots, a_n \in E_n$, ...
2 votes
0 answers
56 views

How to check that a number probably/likely has a divisor having a specific bit length/in range?

Given a randomly generated $\alpha\in\Bbb N$ where $\alpha$ is large thus hard to factor (no small prime composites). How to check that a divisor $F\in\Bbb N$ with a specific bitlengh $n\in\Bbb N∧n<...
7 votes
1 answer
621 views

Fermat-quotient of "order" 3: I found $68^{112} \equiv 1 \pmod {113^3}$ - are there bigger examples known?

(I've taken this from MSE, it seems to be more appropriate here) I'm rereading an older text on fermat-quotients (see wikipedia) from which I have now the Question for $$ b^{p-1} \equiv 1 \pmod{ ...
24 votes
1 answer
888 views

Reference request for a proof of the two-square Theorem

One can show (see below for a sketch of a proof) that every odd prime number $p$ can be written in exactly $(p+1)/2$ different ways as $$p=a\cdot b+c\cdot d$$ with $a,b,c,d\in\mathbb N$ satisfying $\...
10 votes
1 answer
306 views

Fixpoints of $m\longmapsto \mathrm{rad}(\phi(m^2))$ under iteration

Given a strictly positive integer $m$ let $\alpha(m)=\mathrm{rad}(m\phi(m))$ be the radical (product of all distinct prime divisors) of the product of $m$ and of Euler's totient function $\phi(m)=m\...
2 votes
0 answers
87 views

Primes of the form $a+b^k$ for $k=(a \bmod 2),\ldots,n$?

Procrastinal problem: Given $n$, one can ask for integers $a,b>1$ of different parities such that $a+b^k$ is prime for $k=(a\bmod 2),\ldots,n$. A few examples are: $2+4995825^k$ is prime for $k=0,\...
6 votes
1 answer
373 views

Arithmetic properties of positively reduced $2\times 2$-matrices

Call a $2\times 2$ matrix with coefficients in $\{0,1,2,3,\ldots\}$ positively reduced if any row or column reduction (given by replacing a row/column by itself minus the other row/column) produces at ...
1 vote
1 answer
211 views

Primes of the form $p_{i_1}p_{i_2}\cdots p_{i_n}+2k$

Let $S_{n,k}$ be the set of all numbers that can be written as the product of $n$ odd primes plus $2k$. Are there integers $n>1$ and $k>1$ such that $S_{n,k}$ contains finite number of primes?
5 votes
2 answers
530 views

Representing natural numbers as sums of distinct prime powers

I am investigating whether every natural number $n > 18$ can be represented as a sum $p_1^{m_1} + \dots + p_k^{m_k}$, where $p_1, \dots, p_k$ are distinct primes, and $m_1, \dots, m_k$ are distinct ...
0 votes
1 answer
1k views

Alternative proofs of Euclid-Euler theorem

What are some alternative methods of proof for the necessity direction of the above theorem, ie $n$ an even perfect number $\Rightarrow n$ is of form $2^{a-1} (2^a - 1)$ where $2^a - 1$ is a Mersenne ...
2 votes
0 answers
82 views

Bateman-Horn-type generalization of the Goldbach conjecture

The Bateman-Horn conjecture is a generalization of the twin prime conjecture that roughly states that given a set $S=\{f_1, \dots, f_m\}$ of irreducible polynomials with integer coefficients, there ...
4 votes
0 answers
159 views

Effective bound for odd numbers expressed as sums of three primes

I am interested in the representation of odd numbers greater than five as sums of three primes, inspired by Harald Helfgott's seminal proof of the ternary Goldbach conjecture and the nuanced findings ...
2 votes
0 answers
150 views

Electrostatic potential energy of point-charges at primes up to $x$

Given a positive real (or integral) number $x$ we consider the electrostatic potential energy of equal point charges at all primes up to $x$ given by $$E(x)=\sum_{p_1<p_2\leq x}\frac{1}{p_2-p_1}$$ ...
2 votes
0 answers
127 views

Prime splitting in the division field of an elliptic curve

Let $E/\mathbb{Q}$ be an elliptic curve with good reduction at two distinct primes $p, \ell$. Suppose the mod $\ell$ Galois representation associated to $E$ is surjective. Let $K=\mathbb{Q}(E[\ell])$ ...
3 votes
2 answers
629 views

Goldbach conjecture and the difference of two primes

The Goldbach conjecure is not yet proved. But, when an even number is represented as a sum of two primes, is there any knwon result about the difference of the two primes? That is, if $2n$ is a sum of ...
7 votes
1 answer
296 views

Rational prime factors in the components of powers of Gaussian primes

Let $\pi=a+bi\in \mathbb{Z}[i]$ be a Gaussian prime with $a$ and $b$ nonzero, and $b$ even. For odd rational primes $p=\pi\bar\pi$ and $q\neq p$, define $\pi^{\frac{1}{2}\left(q-\left(\frac{-1}{q}\...
4 votes
0 answers
438 views

There are infinitely many prime which have arbitrary large gap in their digits in particular base expansion

Consider $m$ and $r$ is any fixed positive integer and $t$ is a variable $(t=0,1,2,3,...)$. Below, $[a]$ denotes the greatest integer function of $a$ (or floor function). Claim 1 : There exists a ...
12 votes
1 answer
1k views

Power of primes

$n$ is a natural number $>1$, $\varphi(n)$ denotes the Euler's totient function, $P_n$ is the $n^\text{th}$ prime number and $\sigma(n)$ is the sum of the divisors of $n$. Consider the expression: $...
11 votes
1 answer
546 views

Near-Legendre Conjecture

Ingham has shown that there is a prime between $n^{3}$ and $(n+1)^{3}$ for large enough $n.$ Legendre's conjecture about the existence of primes between consecutive perfect squares is of course open....
2 votes
0 answers
121 views

On the elliptic curve $X^3+6d^2X-7d^3 = Y^2$ and the ellipse $p^2+3q^2-d = 0$?

From the ellipse $p^2+3q^2 - d = 0$ we can find a solution to the equation, $$a^3+b^3+c^3 = (c+m)^3$$ if we solve the elliptic curve, $$E:=X^3+6d^2X-7d^3 = Y^2$$ More details can be found in this MSE ...
2 votes
2 answers
187 views

On the primality of $j(n)=\varphi(p_n+1-n)+1$ when $j(n) \equiv 19 \pmod {100}$

Related to Power of primes. Let $p_n$ denote n-th prime and $\varphi$ the totient function. For natural $n$, define $j(n)=\varphi(p_n+1-n)+1$. For $n$ up to $10^9$ if $j(n) \equiv 19 \pmod {100}$ then ...
8 votes
1 answer
847 views

On the least prime in arithmetic progressions

My question concerns the least prime (denoted $p(a, q)$) in the arithmetic progression $a \pmod q$ where $a$ and $q$ are coprime. Quite a time ago Linnik demonstrated that $$p(a, q) \ll q^L$$ for some ...
1 vote
1 answer
289 views

Is there any way to estimate this functions: $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?

Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that: $$ f(n)=\sum_{d\mid n}d\varphi(d) $$ and $$ ...
1 vote
1 answer
289 views

Goldbach conjecture reformulation [closed]

As thought, the question below is a reformulation of the goldbach conjecture. $ S = \{K - ap \mid a \geq 3, p \text{ is prime} < K/2 \} $, where $ a $ is an odd integer greater than or equal to 3, ...
0 votes
0 answers
106 views

Convergence of a series related to counting distinct prime factors

I am here to ask whether the following series is convergent for all real $z$. I am also asking whether this is everywhere real analytic. I conjecture that it is convergent for all real input, or at ...
6 votes
1 answer
419 views

How to define a fractal from the lexicographic sorting on the prime factorization of natural numbers?

Consider on the natural number the lexicographic ordering on the prime factorization: If $m = p_1^{a_1}\cdots p_r^{a_r},n = q_1^{b_1}\cdots q_s^{b_s}$ then we define: $$m \vartriangleleft n :\iff [(...
2 votes
0 answers
285 views

Representation of 2 in sum of powers of positive-negative digits with some base

Define:A set $\mathcal{C}(t)$, a positive integer $n$ is in the $\mathcal{C}(t)$ if $x^t \pmod{n}$ describes a bijection from the set $\{0,1,...,n-1\}$ to itself. Example table: \begin{array}{|c|c|} \...
10 votes
1 answer
622 views

Independence between the number of prime factors of $n$ and $n+2$

I am interested in having an upper bound for the cardinality of $\#\left\{n\leq x\,:\quad\omega(n)=k, \omega(n+2)=\ell\right\}$ for $k,\ell\geq 1$, where $\omega(n)=\sum_{p\vert n}1$ counts the number ...
7 votes
0 answers
246 views

A question about prime numbers, totient function $ \phi(n) $ and sum of divisors function $ \sigma(n) $

This question was previously posted to MSE here. I noticed something with the totient function $ \phi(n) $ and sum of divisors function $ \sigma(n) $ when $n > 1$. It seems than : $ \sigma(4n^2-1) \...
5 votes
2 answers
598 views

On the number of distinct prime factors of $p^2+p+1$

Is it true that, for each positive integer $c$, there exists a prime number $p$ such that $p^2+p+1$ is divisible by at least $c$ distinct primes?
4 votes
0 answers
513 views

Is the integer factorization into prime numbers normally distributed?

Edit: Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking. Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...
5 votes
0 answers
126 views

Taking integer values of a sequence of Beurling primes

Let $P=(p_j)_{j=1}^\infty$ be an increasing sequence of real numbers with $1<p_1$ and $\lim_{j\to\infty}p_j=\infty$. As mentioned in [1], Beurling proved that if the multiplicative group $N_P$ ...
8 votes
1 answer
663 views

The tightest prime zipper

Define a prime zipper as an increasing function $f(n)$ mapping $\mathbb{N}$ into $\mathbb{N}$ with the property that, for every $n \ge 1$, there is at least one prime within the inclusive interval $[ ...
2 votes
2 answers
574 views

Is it true that there always exists a positive integer $n$ such that $p \mid \lfloor k^n\cdot\alpha\rfloor$?

Let $k,M$ be positive integers such that $k−1$ is not squarefree. Prove that there exist a positive real number $\alpha$, such that $\lfloor\alpha\cdot k^n\rfloor$ and M are coprime for any positive ...
8 votes
1 answer
619 views

Arithmetic sequences and Artin's conjecture

(Sorry if this is a naive question; it is not my area!) Consider the following strengthening of Artin's conjecture on primitive roots (and Dirichlet's theorem) for the case of $n=2$: every arithmetic ...
10 votes
1 answer
314 views

Does the mean ratio of the largest prime factor in prime gaps to the lower bound of the gap converge?

Posting in MO since this questions has been unanswered in MSE for 3 months. Let $p_n$ be the $n$-th prime and $q_n$ be largest among all the prime factors of the composite numbers between $p_n$ and $...
0 votes
1 answer
256 views

Factorization trees and (continued) fractions?

This question is inspired by trying to understand the lexicographic sorting of the natural numbers in the fractal at this question: Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , ...
1 vote
0 answers
69 views

Is there an upper bound on the number of partitions of a finite set of primes into 3 sets the products of 2 of which sum to the product of the third?

Is there an upper bound on the number of partitions of a finite set $S$ of prime numbers into 3 sets $A$, $B$ and $C$ for which the following holds?: $$ \prod_{p \in A} p \ + \ \prod_{p \in B} p \ = ...
3 votes
1 answer
705 views

Is $1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n}$ , where $\pi$ denotes the prime counting function and $p_n$ denotes the $n$-th prime?

Is $$1 = \sum_{n=1}^{\infty} \frac{\pi(p_n^2)-n+2}{p_n^3-p_n},$$ where $\pi$ denotes the prime counting function and $p_n$ denotes the $n$-th prime? Context: This question came out as a result in ...
6 votes
1 answer
1k views

A question about the Möbius Function

$\newcommand\bmod{\mathbin\%}$I have been playing around with the Möbius Function and primorials and I am finding results that I am not yet able to understand which I suspect are very elementary. Here'...
5 votes
1 answer
516 views

Smallest prime factor of numbers

The literature refers to smooth integers as \begin{equation}\Psi(x,y):=\#\{n\le x:P_1(n)\le y\},\end{equation} where $P_1(n)$ is the largest prime factor of $n$. There are lots of results studying $\...
0 votes
0 answers
238 views

On a Duality between Riemann-weil explicit formula and Abel- Plana summation of trigonometric prime counting function:

Consider the analytic function $g(x)$ Now define $f(x)=g(x)\frac{\sin^2\left(\frac{π\Gamma(x)}{2x}\right)}{\cos^2\left(\frac{π}{2x}\right)}$ Such that $|f(x+it)|=o(e^{2πt})$ uniformly for every $x$...

1
2 3 4 5
41