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,023
questions
0
votes
0
answers
42
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 ...
- 8,984
-1
votes
0
answers
95
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 ...
-1
votes
3
answers
1k
views
Which even numbers are known to be both prime gaps and the sum of 2 primes?
Goldbach's conjecture asserts that every even integer greater than $3$ is the sum of two primes, while de Polignac's one says every even positive integer is a prime gap infinitely often. My question ...
- 4,618
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,\...
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 $...
- 60.4k
3
votes
1
answer
347
views
The smallest solution to $2^{2k}-1=\text{powerful}$
Integer is powerful if all the exponents in its factorization are at least $2$.
Every powerful integer can be written in the form $a^2 b^3$.
For odd $k$, define $F(k)=2^{2k}-1=(2^k-1)(2^k+1)$.
This ...
- 2,758
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 ...
- 39k
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
3
votes
1
answer
274
views
Fully explicit Linnik's Theorem
Linnik's Theorem states that there exist absolute constants $c$ and $L$ such that for every $m \in \mathbb{N}$ and every $a$ coprime to $m$, there is a prime $p$ with $p \equiv a \pmod{m}$ and $p < ...
- 99.2k
19
votes
6
answers
36k
views
Pascal triangle and prime numbers
Back in the days when I was in high school, I developed a big interest about number theory specifically prime numbers and prefect numbers, I used to stay awake all night long with a bunch of sketch ...
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 \...
- 99.2k
10
votes
2
answers
783
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 ...
- 8,984
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 ...
CommunityBot
- 1
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 $...
- 11.9k
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
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), ...
- 99.2k
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
7
votes
1
answer
628
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{ ...
- 30.7k
24
votes
1
answer
893
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 $\...
- 99.2k
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\...
- 99.2k
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,\...
- 99.2k
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 ...
- 17.5k
1
vote
1
answer
212
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?
- 4,618
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 ...
- 99.2k
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
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 ...
CommunityBot
- 1
4
votes
0
answers
167
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 ...
CommunityBot
- 1
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}$$
...
- 5,632
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])$ ...
- 99.2k
3
votes
2
answers
640
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 ...
- 6,932
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}\...
- 137k
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 ...
CommunityBot
- 1
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:
$...
CommunityBot
- 1
11
votes
1
answer
547
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....
- 294
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 ...
- 2,979
8
votes
1
answer
849
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,446
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
$$
...
- 30.7k
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
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 ...
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
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
10
votes
1
answer
625
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 ...
- 342
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) \...
CommunityBot
- 1
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?
CommunityBot
- 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, ...
- 2,462