**9**

votes

**3**answers

739 views

### Bound the error in estimating a relative totient function

Let $n=p_1^{e_1}\cdots p_k^{e_k}$ be an integer with $k$ prime factors. We know that the number of integers less than $n$ and coprime to it is
$$\Phi(n)=n-\sum_i\frac n{p_i}+\sum_{i \lt j}\frac n{...

**9**

votes

**0**answers

800 views

### Would the following conjectures imply $\lim\inf_{n\to\infty}p_{n+k}-p_{n}=O(k\log k)$?

Assume Goldbach's conjecture. Then for every $n\ge 2$ there exists at least one non-negative integer $r\le n-2$ such that both $n+r$ and $n-r$ are primes. Let's write $r_{0}(n):=\inf\{r\le n-2, (n-r,n+...

**13**

votes

**2**answers

644 views

### Odd-bit primes ratio

Say that a number is an odd-bit number if
the count of 1-bits in its binary representation is odd.
Define an even-bit number analogously.
Thus $541 = 1000011101_2$ is an odd-bit number,
and $523 = ...

**4**

votes

**1**answer

526 views

### Lower bound for a prime gap occurring infinitely often

In his striking paper of may 2013, Zhang showed the existence of an even integer $g\lt 70,000,000$ such that $g$ is a prime gap occurring infinitely often. What is the best unconditional lower bound ...

**19**

votes

**7**answers

3k views

### Asymptotic density of k-almost primes

Let $\pi_k(x)=|\{n\le x:n=p_1p_2\cdots p_k\}|$ be the counting function for the k-almost primes, generalizing $\pi(x)=\pi_1(x)$. A result of Landau is
$$\pi_k(x)\sim\frac{x(\log\log x)^{k-1}}{(k-1)!\...

**33**

votes

**4**answers

2k views

### Are There Primes of Every Hamming Weight?

That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$?
In this case, the Hamming weight of a number is the number of $1$s in ...

**35**

votes

**2**answers

2k views

### A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself

Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...

**8**

votes

**2**answers

2k views

### least prime in a arithmetic progression

Hello
Here I want to consider the simplest arithmetic progression $n\equiv 1\pmod{q}$ where $q$ is a prime. Is it true that we can find a prime $p\leq q^2$ in this arithmetic progression?
This ...

**0**

votes

**1**answer

499 views

### A possible consequence of Dirichlet's theorem about primes in arithmetic progression

EDIT : I copy-paste the beginning of a previous question since Gerry Myerson suggested this question should be self-contained.
"let's consider a composite natural number $n$ greater or equal to $4$. ...

**1**

vote

**3**answers

264 views

### Powers of $2$ and the products of initial odd primes

NOTATION: $O_x$ -- the product of all odd primes $\le x$.
E.g. $O_7=3\cdot 5\cdot 7 = 105$.
QUESTION: Are the three ordered pairs $\ (d\ p)=(1\ 3)\ \ (2\ 3)\ \ (4\ 5)\ $ the only solutions of the ...

**42**

votes

**1**answer

9k views

### Is the Green-Tao theorem true for primes within a given arithmetic progression?

Ben Green and Terrence Tao proved that there are arbitrary length arithmetic progressions among the primes.
Now, consider an arithmetic progression with starting term $a$ and common difference $d$. ...

**66**

votes

**6**answers

8k views

### Does Zhang's theorem generalize to $3$ or more primes in an interval of fixed length?

Let $p_n$ be the $n$-th prime number, as usual:
$p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, etc.
For $k=1,2,3,\ldots$, define
$$
g_k = \liminf_{n \rightarrow \infty} (p_{n+k} - p_n).
$$
Thus the twin ...

**21**

votes

**4**answers

2k views

### Why so difficult to prove infinitely many restricted primes?

I wondered whether there were an infinite number of
palindromic primes written in binary (11, 101, 111, 10001, 11111, 1001001, 1101011, ...)
and quickly discovered that it is unknown
(OEIS A117697).
...

**15**

votes

**4**answers

1k views

### Arithmetic progressions without small primes

The following question came up in the discussion at How small can a group with an n-dimensional irreducible complex representation be? :
Is it known that there are infinitely many primes p for which ...

**22**

votes

**4**answers

1k views

### Small quotients of smooth numbers

Assume that $N=2^k$, and let $\{n_1, \dots, n_N\}$ denote the set of square-free positive integers which are generated by the first $k$ primes, sorted in increasing order. Question: what is a good ...

**17**

votes

**1**answer

1k views

### When is the product $(1+1)(1+4)…(1+n^2)$ a perfect square?

This is a modification of an unanswered problem on the math StackExchange.
When is the product $(1+1)(1+4)…(1+n^2)$ a perfect square?
If $(1+1)(1+4)…(1+n^2)=k^2$ then one possibility is $n=3$, $k=...

**10**

votes

**1**answer

438 views

### Primes dividing $2^a+2^b-1$

From Fermat's little theorem we know that every odd prime $p$ divides $2^a-1$ with $a=p-1$.
Is it possible to prove that there are infinitely many primes not
dividing $2^a+2^b-1$?
(With $2^a,...

**9**

votes

**2**answers

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

**8**

votes

**1**answer

351 views

### Distribution of the number of prime factors

Count the number of prime factors of a number $n$
to include multiplicity,
so that
$$n=24=2^3 \cdot 3 = 2 \cdot 2 \cdot 2 \cdot 3$$
has $4$ prime factors, and
$$n =
6500 =
2^2 \cdot 5^3 \cdot 13 =
2 \...

**7**

votes

**1**answer

1k views

### What would be the consequences of $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log k}$?

The question is in the title: what would be the number theoretic consequences if we managed to establish the conjectured asymptotic equality $\displaystyle{\lim\inf_{n\to\infty}p_{n+k}-p_{n}\sim k\log ...

**6**

votes

**1**answer

1k views

### Number field analogue of the Goldbach Conjecture

Is there a generalization of Goldbachs conjecture for prime ideals in number fields?

**11**

votes

**1**answer

1k views

### Order of magnitude of $\sum \frac{1}{\log{p}}$

Question: What is the order of magnitude of the following sum?
$$ \sum_{\substack{p<n\\\text{$p$ prime}}} \frac{1}{\log{p}} $$
Additional information: Since
$$ \sum_{\substack{p<n\\\text{...

**10**

votes

**2**answers

912 views

### Update for 2015: least prime of form nq+1, with q prime?

I have received a complaint about my 2011 answer
least prime in a arithmetic progression
which, indeed, gives conflicting reports about this:
given a prime $q,$ what can we say about an upper ...

**5**

votes

**1**answer

422 views

### Unexpectedly prime rich cubic polynomial

We got a cubic polynomial which is unexpectedly prime rich.
Let $f(x)=29160 x^3 + 30132 x^2 + 8046 x + 643$ and
$\pi_f(n)$ the number of primes values of $f(x)$ for $x \in [1,n]$.
Let $F(n)=\frac{\...

**7**

votes

**2**answers

458 views

### What is wrong with this deterministic algorithm efficiently generating large primes?

According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k....

**3**

votes

**3**answers

577 views

### Estimate for products of integers that are relatively prime with $N$

Let $N$ be a positive integer. Are there known estimates for the product of all numbers that are smaller than $N$ and relatively prime with $N$? One can assume that $N$ is free of squares, if this ...

**-3**

votes

**2**answers

327 views

### The number of totatives to the nth primorial, in an interval shorter than the nth primorial

(The notation of this question will be improved over the next few days, sorry for the lack of clarity at the moment.)
Can, and if so when can, we determine the amount of natural numbers which are ...

**83**

votes

**4**answers

30k views

### Philosophy behind Yitang Zhang's work on the Twin Primes Conjecture

Yitang Zhang recently published a new attack on the Twin Primes Conjecture. Quoting Andre Granville :
“The big experts in the field had
already tried to make this approach
work,” Granville ...

**102**

votes

**5**answers

6k views

### Gaussian prime spirals

Imagine a particle in the complex plane, starting at $c_0$, a Gaussian integer,
moving initially $\pm$ in the horizontal
or vertical directions. When it hits a Gaussian prime, it turns left $90^\...

**36**

votes

**4**answers

4k views

### Why could Mertens not prove the prime number theorem?

We know that
$$
\sum_{n \le x}\frac{1}{n\ln n} = \ln\ln x + c_1 + O(1/x)
$$
where $c_1$ is a constant. Again Mertens' theorem says that the primes $p$ satisfy
$$
\sum_{p \le x}\frac{1}{p} = \ln\ln ...

**42**

votes

**4**answers

11k views

### How hard is it to compute the number of prime factors of a given integer?

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.
...

**48**

votes

**4**answers

4k views

### Strange (or stupid) arithmetic derivation

Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to ...

**41**

votes

**1**answer

3k views

### Are the primes normally distributed? Or is this the Riemann hypothesis?

Forgive my very naive question. I know next to nothing about number theory, but I'm curious about the state of the art on the distribution of primes.
Let $\mathrm{Li}(x)$ be the offset logarithmic ...

**42**

votes

**1**answer

2k views

### Exploding primes

Suppose every prime $n$ could "explode" once.
An explosion results in $\lfloor \alpha \ln n \rfloor$ particles being
uniformly distributed over the integers in a range $n \pm \lfloor \beta \ln n \...

**31**

votes

**1**answer

3k views

### Integers not represented by $ 2 x^2 + x y + 3 y^2 + z^3 - z $

EDIT, 9 March 2014: when I asked this in 2010, I did not have the courage of my convictions, and so did not ask for an if and only if proof, as Kevin Buzzard quite properly pointed out. Such problems ...

**17**

votes

**3**answers

1k views

### Prime factorization “demoted” leads to function whose fixed points are primes?

Let $n$ be a natural number whose prime factorization is
$$n=\prod_{i=1}^{k}p_i^{\alpha_i} \; .$$
Define a function $g(n)$ as follows
$$g(n)=\sum_{i=1}^{k}p_i {\alpha_i} \,$$
i.e., exponentiation is "...

**18**

votes

**6**answers

2k views

### Question on consecutive integers with similar prime factorizations

Suppose that $n=\prod_{i=1}^{k} p_i^{e_i}$ and $m=\prod_{i=1}^{l} q_i^{f_i}$ are prime factorizations of two positive integers $n$ and $m$, with the primes permuted so that $e_1 \le e_2 \cdots \le e_k$...

**23**

votes

**2**answers

2k views

### What is the crucial difference the Maynard/Tao approach and Goldston-Pintz-Yildirim that extends to prime k-tuples with $k>2$

Suppose $m$ is a positive integer. A quantity of interest is
$$
H_m = \liminf_{n\to\infty} \left(p_{n+m} - p_n \right)
$$
The twin prime conjecture, is, of course $H_1 = 2$, the the prime k-tuples ...

**11**

votes

**7**answers

2k views

### Are there any interesting or lesser known proofs related to Bertrand's Postulate

There are 3 standard proofs of Bertrand's Postulate:
(1) Chebyshev's original proof
(2) Ramanujan's simplification of Chebyshev's proof
(3) Erdos's proof
I recently learned about the very ...

**20**

votes

**2**answers

1k views

### The prime numbers modulo $k$, are not periodic

Consider the sequence of prime numbers: $2,3,5,7, \cdots$. Now reduce this sequence modulo $k$ for some integer $k > 2$. Show the resulting sequence is not periodic. :
EDIT: As noted in the ...

**15**

votes

**1**answer

1k views

### Sums of primes that are themselves prime

I'm not a math expert so this may be a trivial question; if $p_i$ is the $i$-th prime, let:
$$S(n) = \sum_{i=1}^n p_i$$
be the sum of the first $n$ primes and
$$P(n) = | \{1 \leq i \leq n \mid S(...

**12**

votes

**3**answers

898 views

### At what point would an elementary generalization of Bertrand's Postulate be interesting?

I know that in 1952 Jitsuro Nagura was able to show that there is always a prime between $k$ and $\frac{6k}{5}$ for $k > 24$.
At what point would an improvement on Nagura's result be interesting? ...

**7**

votes

**6**answers

1k views

### Sequences equidistributed modulo 1

Let $\alpha$ be any positive irrational and $\beta$ be any positive real. We have the following results.
H. Weyl (1909): The fractional part of the sequence $\alpha n$ is equidistributed modulo 1.
I....

**15**

votes

**1**answer

633 views

### A Collatz-like function that bifurcates on primes

This is likely piling one mystery on another, but ...
I was exploring a function $f(n): \mathbb{N} \mapsto \mathbb{N}$ defined as follows:
$$
f(n) =
\begin{cases}
n^2 & \text{if} \;n \;\text{is ...

**11**

votes

**1**answer

2k views

### The Green-Tao theorem and positive binary quadratic forms

Some time ago I asked a question on consecutive numbers represented integrally by an integral positive binary quadratic form. It has occurred to me that, instead, the Green-Tao theorem may include a ...

**34**

votes

**5**answers

3k views

### Happy New Prime Year!

It happens that next year 2011 is prime, while outgoing 2010 is
highly composite in the sense that the number of its distinct prime factors
is 4, maximal possible for a year $< 2310$.
Let me ...

**22**

votes

**1**answer

689 views

### How big can a set of integers be if all pairs have small gcd?

Suppose $A\subset[1,N]$ is a set of integers. If for any distinct $a,b\in A$ we have $(a,b)\leq M$ then how big can $|A|$ be?
If $M=1$ then $|A|$ is at most $\pi(N)$ since the map $a\mapsto P_+(a)$ (...

**12**

votes

**2**answers

624 views

### Mertens-like sum in arithmetic progressions

I find myself needing a good estiamate for $\sum_{p\le x,\, p\equiv a\mod q} 1/p$, perhaps something like
$$
\sum_{p\le x,\, p\equiv a\mod q} \frac1p = \frac{\log\log x}{\phi(q)} + b(q,a) + O\big(\exp(...

**12**

votes

**1**answer

593 views

### Analytic lower bounds on the first sign change of pi(x) - li(x)?

There have been many results on the first sign change of $\pi(x)-{\mathrm{li}}(x)$: among others, Lehman, te Riele, Bays & Hudson, Demichael, Chao & Plymen, and most recently Saouter & ...

**8**

votes

**1**answer

330 views

### Asymptotic limit of truncated Legendre sieve

Consider the truncated sum
$$
S(x):=\sum_{\substack{{d\mid P(\sqrt{x})}\\{d\leq x}}}\mu(d)/d,
$$
where $P(z)$ is the product of all primes less than or equal to $z$, and $\mu(d)$ is the Möbius ...