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,022
questions
-1
votes
0
answers
94
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
98
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 $...
- 101
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 ...
- 2,979
5
votes
1
answer
687
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,218
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 ...
- 1,758
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), ...
- 232
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 ...
- 283
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$, ...
- 675
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<...
- 151
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 ...
- 151
11
votes
2
answers
512
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 $...
- 17.5k
5
votes
2
answers
553
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 ...
- 1,218
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 ...
- 151
4
votes
0
answers
163
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}$$
...
- 17.5k
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])$ ...
- 1,412
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 ...
- 597
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 ...
- 12.1k
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 ...
- 24.2k
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
$$
...
- 139
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, ...
- 23
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:
$...
- 171
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|}
\...
- 597
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) \...
- 71
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, ...
- 2,462
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$ ...
- 51
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?
- 886
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}$ , ...
- 2,462
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 \ = ...
- 19.5k
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 $\...
- 251
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 $...
- 4,638
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 ...
- 2,462
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 [(...
- 2,462
1
vote
1
answer
228
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 ...
- 886
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 ...
- 61
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(...
- 2,462
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,\...
- 781
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 ...
- 8,984
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,088
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 ...
- 41
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, ...
- 11.9k
3
votes
1
answer
234
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 ...
- 11.9k
3
votes
0
answers
232
views
The number of continuously increasing primes gaps in the interval $[2,n]$ is less than $\log n$
A prime gap is the difference between two successive prime numbers. The $n$-th prime gap, denoted gn or $g(p_n)$ is the difference between the $(n+1)$-st and the $n$-th prime numbers. Using my ...
- 1,086
4
votes
1
answer
240
views
Irreducible integral polynomials having roots module primes in arithmetic progressions
Let $f(x)$ be an irreducible polynomial with integer coefficients. One can show (see Exercise 7.2 in this paper of Lenstra) that if $f(x)=0$ has a solution mod $p$ for all but finitely many primes $p$...
- 6,084