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
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 ...
Mathew's user avatar
  • 71
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 ...
Charles's user avatar
  • 8,994
-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 ...
Somudro Gupto's user avatar
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 $...
The T's user avatar
  • 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}^\...
Somudro Gupto's user avatar
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 ...
AtypicalAnorexic's user avatar
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 ...
Command Master's user avatar
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 \...
Marcos Cramer's user avatar
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 ...
Geoffrey Irving's user avatar
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), ...
Felixson's user avatar
  • 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 ...
user1747134's user avatar
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$, ...
Sophie M's user avatar
  • 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<...
user2284570's user avatar
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 ...
user2284570's user avatar
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 $...
Roland Bacher's user avatar
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 ...
Marcos Cramer's user avatar
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 ...
Ben's user avatar
  • 151
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 ...
Anton Rechenauer's user avatar
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}$$ ...
Roland Bacher's user avatar
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])$ ...
Jeff H's user avatar
  • 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}\...
Jonathan Trousdale's user avatar
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 ...
Pruthviraj's user avatar
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 ...
Tito Piezas III's user avatar
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 ...
joro's user avatar
  • 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 $$ ...
Jamal Farokhi's user avatar
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 ...
Zachary Hoelscher's user avatar
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, ...
Felix Fowler's user avatar
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: $...
Craw Craw's user avatar
  • 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|} \...
Pruthviraj's user avatar
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) \...
Aurel-BG's user avatar
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, ...
mathoverflowUser's user avatar
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$ ...
Anon12345's user avatar
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?
Pablo Spiga's user avatar
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 ...
Carl-Fredrik Nyberg Brodda's user avatar
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}$ , ...
mathoverflowUser's user avatar
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 \ = ...
Stefan Kohl's user avatar
  • 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 $\...
alidixon222's user avatar
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 $...
Nilotpal Kanti Sinha's user avatar
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 ...
mathoverflowUser's user avatar
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 [(...
mathoverflowUser's user avatar
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 ...
Pablo Spiga's user avatar
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 ...
Egehan Eren's user avatar
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(...
mathoverflowUser's user avatar
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,\...
Sayan Dutta's user avatar
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 ...
Charles's user avatar
  • 8,994
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$...
Vincent Granville's user avatar
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}$ ...
Raj Pratap Singh's user avatar
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 ...
Azoth's user avatar
  • 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, ...
Michael Hardy's user avatar
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 ...
Michael Hardy's user avatar

1
2 3 4 5
41