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

learn more… | top users | synonyms

6
votes
0answers
182 views

Can integers be distorted to make primes more regular?

Given a set $P$ of real numbers $\ge 1$, define the gap among different products in $P$ as $$g(P) = \inf \big\{\prod_{i=1}^n p_i^{a_i} - \prod_{i=1}^n p_i^{b_i} \mid p_i\in P;\,\, p_i\ne p_j \,\text{ ...
-7
votes
0answers
76 views

Conjecture about Prime Numbers [on hold]

Conjecture 1. Being P the product of the multiplication of several different prime numbers, and being Np ˂ P any prime number not being prime factor of P; being NL ˂ │P^(1/2)│ any prime number not ...
1
vote
0answers
124 views

Generalization of Little Fermat Theorem for a particular $a$ and perfect shuffles

I'm looking for the smallest $n\in \mathbb{N}$ that solves the following equation: $$2^n=1 \mod m$$ For an odd $m$. I know that Little Fermat Theorem and Euler Totient give me a solution but they ...
-4
votes
2answers
246 views

Brocard's problem [closed]

According to Brocard's problem $$x^{2}=n!+1 \Rightarrow (x+1)(x-1)=n!$$, where $(x+1)/2$ , $(x-1)/2$ are consecutive integers, assume one of them is z, another is (z-1). z and (z-1) have all primes ...
-1
votes
0answers
67 views

Semiprime number theorem with small prime factor

Hardy & Wright, Theorem 437 gives a nice asymptotic for $k$-almost primes less than $x$. Can we say anything if we restrict one of the prime factors of our almost prime to having a small prime ...
3
votes
1answer
79 views

What is the Complexity Class of the “Function Variant” of the Integer Factorization Problem?

I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered. So, ...
2
votes
0answers
98 views

Infinite sums with Mobius Inversion : can we have uniform convergence of inversion formula?

My question is on Mobius inversion formula convergence/properties when used with infinite sums of function. Lets consider (on $\mathbb{R}^{+}$): $$S(x)= \sum\limits_{n=1}^{\infty} f(nx)$$ We call ...
2
votes
1answer
317 views

Can you find squares in this class?

For a problem I am working over, I would like to prove that numbers of the following type are not squares $p(l^4+6l^2m^2-3m^4)$ where $p,l,m$ are integers an $p$ prime. I have already found various ...
7
votes
1answer
365 views

Which kind of subsets of primes one needs to generate a positive ratio of the natural numbers?

Not knowing elementary number theory well, I ask this one, which is not very clear to answer, rather I am looking for some results around this question or known theorems. The problem is the following: ...
1
vote
0answers
41 views

Number of solutions of arithmetic function's equation [migrated]

Say, an equation is given below \begin{equation} 2\pi(x) - \pi(2x)=\omega(x) \end{equation} where $x$ is a positive integer, $\pi(x)$ is the prime-counting function, and $\omega(x)$ is the number of ...
0
votes
0answers
75 views

Polynomial congruences with respect to a large prime (power)

Suppose that $f(x) \in \mathbb{Z}[x]$ is a polynomial of degree $d$ such that for all primes $p$, there exists $x_0 \in \mathbb{N}$ such that $p^2 \nmid f(x_0)$. Further, suppose that $f$ is ...
5
votes
1answer
273 views

A set of integers whose factorial can be written as a product of two factorials

I am trying to collect informations concerning the set $$\mathcal{A}=\left\{n\in\mathbb{N} \mid (\exists k,l\in\{2,3,\dots,n-2\})(n!=k!l!)\right\}.$$ It seems not much is known about the set ...
-3
votes
1answer
266 views

Asymptotic formula for $\prod_{p\leq x} (1-p^{-1})$ [closed]

Does there exists a good asymptotic formula for $$A(x) := \prod_{p\leq x}(1-\frac 1p).$$ By using a heuristic argument one can guess: $$A(x) \sim \frac{1}{2\,\mathrm{ln}(x)}.$$ Here is the ...
1
vote
0answers
135 views

Density of numbers whose prime factors all come from a fixed congruence class

Let $q$ be a positive integer greater than one, and let $a$ be an integer such that $\gcd(a,q) = 1$. Define $$D(a,q) = \{n \in \mathbb{N} : p | n \Rightarrow p \equiv a \pmod{q} \}.$$ Do we know the ...
2
votes
1answer
287 views

Is anything like $\phi(n)>\dfrac n{e^\gamma\log\log n},\ \sigma(n)<e^\gamma n\log\log n$ known/conjectured for the generalizations of these functions?

Is anything like $\dfrac n{\phi(n)}<\dfrac{\sigma(n)}n<e^\gamma\log\log n$ known/conjectured for the generalizations of these functions? Let $n=p_1^{a_1}\cdots p_t^{a_t}$ be the canonical prime ...
7
votes
2answers
539 views

Most dense subset of numbers that avoids arbitrarily long arithmetic progressions

The famous Green-Tao theorem says that there exist arbitrarily long sequences of primes in arithmetic progression. I am wondering: How dense can a subset $S \subset \mathbb{N}$ be and still avoid ...
2
votes
0answers
86 views

Best constant for Maier's theorem?

Maier proved that, for fixed $\lambda>1,$ $$ \limsup_{x\to\infty}\frac{\pi(x+\log^\lambda x)-\pi(x)}{\log^{\lambda-1}x}>1 $$ and in particular $$ \limsup_{x\to\infty}\frac{\pi(x+\log^\lambda ...
8
votes
2answers
701 views

What is known about primes of the form x^2-2y^2?

David Cox's book Primes of The Form: $x^2+ny^2$ does a great job proving and motivating a lot of results for $n>0$. I was unable to find anything for negative numbers, let alone the case I am ...
2
votes
1answer
266 views

$n^3 | \sum_{i=1}^{n-1}\binom{n}{i}^2$ => $n | \sum_{i=1}^{n-1}\binom{n}{i}$?

For $n\in \mathbf{N}$ is $$n^3 \text{ divides } \sum_{i=1}^{n-1}\binom{n}{i}^2=\binom{n}{1}^2+\cdots +\binom{n}{n-1}^2$$ impling $$n \text{ divides } ...
0
votes
0answers
84 views

logarithmic integral question

Define: $\operatorname{li}(x)=\int_{0}^{x}\dfrac{1}{\log(t)}\operatorname{d}t$. When does the following statement fail? With $\theta = 1 + \frac{1}{\operatorname{li}(x)}$, for $x \ge x_0$, ...
0
votes
0answers
141 views

Does the Euler product converge at $s=1$ for the Dirichlet $L$ function?

For the Riemann Zeta function, the Euler product converges on $\{Re(s)=1\}$ except at $s=1$.The zeta series diverges everywhere on $\{Re(s)=1\}$. But the $L$ series converges on $\{Re(s)>0\}$. What ...
16
votes
1answer
746 views

Primes that are sums of two squares with constraints on the squares

It is well known that there are infinitely many primes of the form $a^2+b^2$ (namely all primes congruent to $1$ modulo $4$). On the other hand, Euler raised the problem as to whether there are ...
5
votes
1answer
346 views

Generating primes with floor of a polynomial $[p(n)]$

Is there a polynomial $p(x)$ with real coefitients and degree at least one that $[p(n)]$ for everey natural number like $n$ be a prime? If yes, what is such a polynomial $p(x)$ and if no, how to ...
10
votes
0answers
291 views

Word complexity of primes mod 4

For an infinite binary word $w$, the word complexity $f_w(n)$ is defined as the number of different subwords of length $n$. The asymptotic behavior of this function is an important parameter of the ...
4
votes
2answers
601 views

How to calculate the sum of remainders of N?

I'm trying to sum the remainders when dividing N by numbers from 1 up to N $$\sum_{i = 1}^{N} N \bmod i$$ It's easy to write a program to evaluate the sum if N is small in O(N) but what if N is large ...
4
votes
0answers
261 views

Is there a hidden symmetry in the prime numbers distribution?

Under Goldbach's conjecture, let's consider once again the map $r_0\colon n\mapsto r_{0}(n)$ such that $r_{0}(n)$ is the smallest non negative integer $r$ such that both $n-r$ and $n+r$ are prime. ...
1
vote
2answers
580 views

Has this formula about prime gaps already been conjectured and/or proven?

While playing around with prime gaps, I found out that the following formula seems to be a rather good approximation of the ratio $\dfrac{p_{b}-p_{a}}{b-a}$ where $a<b$ are positive integers: ...
1
vote
0answers
429 views

Is $ a^2b^2-ab-ap$ a perfect square for suitable $a,b\in \mathbb{Z}^+$?

Consider the expression $$ a^2b^2-ab-ap\qquad (a,b\in \mathbb{Z}^+), $$ where $p\equiv1\pmod{4}$. Question. For every prime $p\equiv1\pmod{4}$ do there exist $a,b\in\mathbb{Z}^+$ such that ...
2
votes
1answer
237 views

Prime Number Theorem on APs under various conjectures

I'm trying to find the best asymptotic expansions for $\pi(x; a, q)$ in various states: Unconditionally we have \begin{equation} \pi(x; a, q) = \frac{\operatorname{li(x)}}{\phi(q)} + O\left(x ...
2
votes
0answers
368 views

A “Take a Square Root When You Can” conjecture related to the prime factorization

I would tend to think that the following has already been investigated. But as implied from the title, I have no idea how to even start looking for it. Let $P_n$ denote the sum of the squares of ...
1
vote
0answers
46 views

closed form for a series with binomials and primes

does the series $\sum_{n=0}^\infty p^n \binom{x}{p^n}$ have a closed form ? ($p$ prime) this is a special case of $\sum_{n=0}^\infty p^n \left(\sum_{k=p^n}^{p^{n+1}-1}a_k\binom{x}{k}\right)$ with the ...
2
votes
1answer
511 views

Conjecture on the square root of the sum of the squares of the prime factors of a number

Let $A_{n}$ denote the square root of the sum of the squares of the prime factors of $n$. For example, $A_{60}=\sqrt{2^2+2^2+3^2+5^2}\approx6.48$. I have recently made the following observations: ...
10
votes
1answer
616 views

Divergence of a series similar to $\sum\frac{1}{p}$

Suppose we start with $k$ primes $p_1,p_2,\ldots ,p_k$ (not necessarily consecutive) and a residue class for each prime $r_1,r_2,\ldots ,r_k$. We denote the least integer not covered by the arithmetic ...
7
votes
3answers
537 views

Is $n = p-q$ equivalent to Goldbach's Conjecture?

One open conjecture is that every even integer greater than two is the difference of two primes. (Some superficial discussion here.) Goldbach's conjecture states that every even integer greater than ...
5
votes
1answer
548 views

Any way to prove Prime Number Theorem using Hyperbolic Geometry? [closed]

The prime number theorem says that the density of prime numbers is inverse as the number of digits of $n$: $$\displaystyle \frac{\{1 \leq k \leq n : \text{ prime } \}}{n} \approx \frac{1}{\log n}$$ ...
2
votes
2answers
406 views

Prime divisors of $p^n+1$

Let $p$ be a rational prime and $n$ be a positive integer. It can be easily deduced from Zsigmondy's theorem that $p^n+1$ has a prime divisor greater than $2n$ except when $(p,n)=(2,3)$ or ...
5
votes
1answer
365 views

Ruth-Aaron triples, etc

A Ruth-Aaron pair is two numbers $(n,n+1)$ such that their sum of prime factors is equal, counting repeated prime factors. (The name refers to Hank Aaron's 715 homeruns surpassing Babe Ruth's 714!) So ...
3
votes
0answers
418 views

Two (strictly related) proofs by induction of inequalities

This is a question I originally asked on MSE, receiving no answer, even with a bounty (which expired) on it. Therefore I am crosslinking in order to prevent duplication of effort: see here for the ...
3
votes
1answer
269 views
4
votes
1answer
199 views

Prime labelling of graphs

A prime labeling of a graph is an injective function $f: V(G) \to \{1, 2, ..., |V(G)|\}$ such that for every pair of adjacent vertices $u$ and $v$, $\text{gcd}(f(u), f(v)) = 1$ (labels of any two ...
1
vote
1answer
133 views

Cardinality of the prime divisor set of a k-power sum

Let $a_{1},\dots,a_{n}$ be positive natural numbers ($n>2$) such that $a_{i}\neq a_{j}$ if $i\neq j$. I want to prove that $$ \left\lvert \left\{ p \text{ prime} \; : \; p \mid \sum_{i=1}^n ...
12
votes
1answer
529 views

Is there a known primitive recursive upper bound on the nth “Zhang prime”

(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.) In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...
2
votes
1answer
382 views

Have there been any new developments in the Firoozbakht conjecture? [duplicate]

Let $(p_{n})_{n∈ℕ}$ be the sequence of consecutive primes. In P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, 1995, page 185, the author says: A new conjecture by F. ...
4
votes
0answers
133 views

The divisors of $p-1$ and high-degree residues modulo $p$

Here is a somewhat more explicit version of a question that I asked a while ago. Suppose that $p$ is a prime of the form $p=2n(n+1)+1$, with a positive integer $n$. Can every odd prime divisor of ...
0
votes
0answers
73 views

Lucasian Primality Criterion for Specific Class of $k \cdot 2^n-1$

Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and $x$ are nonnegative integers . Conjecture Let $N=k\cdot 2^n-1$ such ...
2
votes
0answers
96 views

counting irreducible factors

In How hard is it to compute the number of prime factors of a given integer? a question was asked on computing number of prime factors of an integer. Suppose we have a polynomial $f(X)\in \Bbb Z[X]$ ...
4
votes
1answer
184 views

References to proofs of upper and lower bounds on the number of coprimes in an interval?

On the first page of the article "When the sieve works", the authors present upper and lower bounds for $S(T,T+x;\mathcal{E})$; the number of integers in the interval $(T,T+x]$ that are coprime to all ...
2
votes
0answers
117 views

Siegel Walfisz Theorem for algebraic number fields

Is there a generalization of the Siegel Walfisz to algebraic number fields? This has been done for the prime number theorem in the prime ideal theorem.
0
votes
0answers
118 views

E- and A-algorithms for finite arithmetic prime progressions and other sets

(EDIT from scratch). Let $\ \mathbf a := (a_1\ \ldots\ a_n)\ $ be an increasing non-constant arithmetic progression of odd positive numbers. The goal here is to resolve efficiently one of the two ...
3
votes
1answer
355 views

Sum of two squares and implication of Bunyakovsky conjecture

Bunyakovsky's conjecture states that a polynomial with integer coefficients takes infinitely many prime values at integers, unless this is impossible for trivial reasons. Let $a_1(x), a_2(x), a_3(x), ...