# 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,024
questions

5
votes

0
answers

208
views

### A possible variant of Zagier's one-sentence proof for Fermat's sum of two squares theorem?

Is it possible to modify Zagier's one-sentence proof of Fermat's sum of two squares theorem (see here) to prove certain non-trivial cases of Jacobi's four-square theorem (see here)?
Let $p$ be a prime ...

1
vote

0
answers

69
views

### Effective Erdős–Kac theorem

I have some number $N$ and some integer $k>0$. I want to know what fraction of numbers up to $N$ have more than $k$ prime factors. (In my application, with repetition, but the $\omega$ version is ...

-1
votes

0
answers

96
views

### Is it possible to have square-free order(s) in $\mathbb{Z}^\times_N$?

Suppose, $N=p\cdot q$ is the product of two safe primes $p=2p'+1$ and $q=2q'+1$ for some odd primes $p'$ and $q'$.
Let, $p_0,p_1,\ldots,p_m\ll p',q'$ be a few odd primes chosen uniformly at random ...

0
votes

1
answer

100
views

### Could I possibly exploit distinct odd primes raised to 6 to solve Exact Three Cover, when reducing it in Subset Sum?

I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if there are $...

0
votes

0
answers

94
views

### Relation between elements with fixed exponent over different $\mathbb{Z}^\times_p$

A primitive root $h$ of $n$ is a generator of the cyclic modulo multiplicative group $\mathbb{Z}^\times_n$.
Suppose, $\mathbb{P}_{\langle 2\rangle,N}=\{p_i <N\mid \langle 2\rangle=\mathbb{Z}^\...

2
votes

1
answer

106
views

### Discovering patterns in data and methodologies used

I feel really dumb asking this but are there examples of any type of data where once a pattern/structure is discovered, the pattern is usually simple but the methodology used to discover that pattern ...

4
votes

0
answers

130
views

### Is there a statement in Presburger arithmetic about primes this simple heuristic fails for?

I came up with the following conjecture while thinking about ways to formulate some heuristics about primes:
Conjecture: Given a statement $s$ in Presburger arithmetic, using an additional unary ...

5
votes

1
answer

688
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 \...

1
vote

0
answers

84
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

1k
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

62
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

65
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

57
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<...

2
votes

0
answers

107
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 ...

11
votes

2
answers

513
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 $...

5
votes

2
answers

554
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 ...

2
votes

0
answers

83
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

171
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

151
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

131
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])$ ...

7
votes

1
answer

300
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

439
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 ...

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

190
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 ...

1
vote

1
answer

290
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
$$
...

0
votes

0
answers

107
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 ...

1
vote

1
answer

290
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, ...

10
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:
$...

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|}
\...

7
votes

0
answers

251
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) \...

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$ ...

5
votes

2
answers

604
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?

8
votes

1
answer

625
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 ...

0
votes

1
answer

260
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 \ = ...

5
votes

1
answer

554
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 $\...

10
votes

1
answer

315
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 $...

3
votes

1
answer

709
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

428
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 [(...

1
vote

1
answer

229
views

### Prime divisors of $p^n-1$, primitive prime divisors

Let $p,q,t_1,t_2$ be distinct prime numbers and let
$$k=\frac{p^{qt_1t_2}-1}{p^q-1}.$$
Suppose that $\gcd(k,qt_1t_2)=1$. Is there any reason that $k$ is divisible by at least $7$ distinct prime ...

0
votes

1
answer

229
views

### A question about the prime counting function

I was playing around with the prime counting function and came across something that seemed correct to me, maybe it's already been proven but I don't know so I decided to ask here.
maybe a stupid ...

1
vote

2
answers

375
views

### Solving a recurrence relation for the prime counting function?

I have found some number sequence $c_n = 1+b_n$ for $n \ge 0$, where $b_n = $ A307977(n).
I am trying to solve the following recurrence relation for the prime counting function:
$$\forall n \ge 3: \pi(...

9
votes

2
answers

2k
views

### Can every integer be written as a sum of squares of primes?

This question is mainly inspired from a different problem I was working on.
Is there a value of $k$ such that, for each $n\in \mathbb N$, the equation
$$\sum_{i=1}^{k}x_i^2=n$$
is solvable in $x_1,\...

4
votes

1
answer

251
views

### Density of primes $p$ where $p-1$ has a prime factor exceeding $p^{2/3}$

Fouvry proved* that primes $p$ such that the greatest prime factor, $q$, of $p-1$ is greater than $p^{2/3}$ have positive density in the primes. (The sequence is A073024 in the OEIS.)
Are there any ...

2
votes

0
answers

124
views

### Limit of scaled infinite sum with Dirichlet characters modulo 4: is it zero?

I am trying to get an asymptotic formula such as
$$ L_4(s, n) \sim L_4(s) + \rho_n(s)\Lambda_n + \frac{\alpha(s)}{\sqrt{n}} + \frac{\beta(s)}{\sqrt{n\log n}}+\cdots$$
where $L_4(s, n)$ is the first $n$...

3
votes

2
answers

391
views

### If $p_1$ and $p_2$ are prime numbers, then either $p_1$ divides $\sum_{i=1}^{p_1-1} i^{p_1p_2-1}$ or $p_2$ divides $\sum_{i=1}^{p_2-1} i^{p_1p_2-1}$?

I feel like it's true as for small cases I couldn't find counterexample.
In general, whether it's true that if we have prime number, $p_{1}, p_{2},\dotsc, p_{k}$ and $n=p_{1}p_{2}p_{3}\dotsb p_{k}$ ...

2
votes

0
answers

115
views

### On the integer of the form p^a q^b closest to a given integer N

If we give ourselves a number having only one prime factor $p$ and a given natural integer $N$, we know how to give the integer of the form $p^k$ closest (and less than) to this integer $N$ it's ...

6
votes

2
answers

1k
views

### Prime gaps within which every "small" prime appears as a factor: Are there only finitely many? Is this the last one?

For a bounded range of positive integers $n,n+1,\ldots,m,$ call a prime number "small" if it does not exceed $\sqrt m,$ so that if one is trying to factor all of these numbers into primes, ...

3
votes

1
answer

235
views

### Prime gaps that are "relatively" bigger than all later prime gaps: Is this in OEIS?

This OEIS entry is about
Primes (lower end) with record gaps to the next consecutive prime: primes p(k) where p(k+1) - p(k) exceeds p(j+1) - p(j) for all j < k.
I'm wondering about a different ...