All Questions
Tagged with nt.number-theory prime-numbers
1,808 questions
6
votes
2
answers
804
views
Must Mersenne numbers be divisible by arbitrary large primes with exponent one?
Let $M_n$ denote the Mersenne numbers $M_n=2^n-1$.
As $n$ varies, must $M_n$ be divisible by arbitrary large prime $p$
with exponent one, i.e. $p \mid M_n, p^2 \nmid M_n$?
In other words, must the ...
- 44.4k
2
votes
0
answers
108
views
Largest prime determinant of a binary matrix
Given an integer $n$, I want to prove the existence of an $n\times n$ binary matrix (with 0,1 entries), whose determinant is a prime number. What is a lower bound on the largest determinant that I ...
- 3,549
3
votes
0
answers
266
views
Conjectured primality test for numbers of the form $N=4 \cdot 3^n-1$
This is a repost of this question.
Can you provide proof or counterexample for the claim given below?
Inspired by Lucas-Lehmer primality test I have formulated the following claim:
Let $P_m(x)=2^{-m}\...
- 2,661
0
votes
0
answers
62
views
On base $b$ digits of $n\#$ (primorial)
Related to
normal numbers.
Let $n\#$ denote the primorial, the product of the first $n$ primes.
Q1 For all bases $b>1$, do the base $b$ digits of $n\#$ occur
with equal asymptotic frequency $\...
- 25.4k
16
votes
3
answers
2k
views
Are 0 and 1, respectively, the least and most used digits among primes?
In order to write the first 25 primes (2 to 97), 46 digits are necessary, nine of each of the digits 2, 3, and 7, fewer of all the others. Thereafter, at least for a while, the digit 1 is used more ...
- 4,589
10
votes
4
answers
1k
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 ...
- 44.4k
4
votes
2
answers
737
views
On finite products of $\frac{p+4}{p+2}$ with $p$ prime
Let us consider factorizations of rational numbers greater than one. For integers $a>b>0$, clearly
$$\frac ab =\prod_{n=b}^{a-1}\frac{n+1}n.$$
In view of Question 476578 and Max Alekseyev's ...
- 884
35
votes
9
answers
9k
views
Why is integer factoring hard while determining whether an integer is prime easy?
In 2002, the discovery of the AKS algorithm proved that it is possible to determine whether an integer is prime in polynomial time deterministically. However, it is still not known whether there is an ...
- 39.9k
5
votes
1
answer
811
views
A consequence of Firoozbakht's conjecture?
This is a question out of curiosity, while looking at the Firoozbakht's conjecture. It might not be research related, but as usual, I am not really sure if a question ever is research related or not, ...
- 3,064
4
votes
1
answer
403
views
Möbius square root function: existence of multiplicative and bounded function
With $\mu$ being the Möbius function, there exist infinite possibilities of square roots. For example, for each $n$ such that $\mu(n)\neq 0$ there is a choice: if $\mu(n)=-1$, we can choose to define $...
- 651
9
votes
2
answers
794
views
Why do these finite group Dedekind matrices seem to have integer spectrum when specialized to the order of group elements?
Let $p$ be a prime and let $f_p$ be the permutation on the set $\{1,2,\cdots,p-1\}$ which is given by taking inverses in $\mathbb{Z}/(p)$:
$$x \bmod(p) \mapsto \frac{1}{x} \bmod (p)$$
So for instance, ...
- 38.6k
6
votes
2
answers
631
views
Rate of convergence of the prime zeta function P(2)
For an application in statistical group theory, we need explicit upper and lower bounds that an expert in number theory (I am not one) may know how to prove.
Question 1: What are "good" bounds $f_1(x)...
- 103
1
vote
0
answers
152
views
On lacunary series connected with prime number theory
Consider the following lacunary sum with parameter $x$:
$$S(x)=\sum_{n=5}^{\infty}\sin^2\left(\frac{x\Gamma(n)}{n}\right).$$
As we can see for $x=\frac{\pi}{2}$
the sum becomes$$\sum_p\cos^2\left(\...
- 4,713
2
votes
1
answer
379
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|}
\...
- 599
2
votes
1
answer
159
views
Primality of divisor sums
Let $k \geq 2$ be an integer. Put $[k] = \{1, \cdots, k\}$. Let $\mathcal{P} = \{p_1, \cdots, p_k\}$ be a set of $k$ primes. For every subset $S \subseteq [k]$ put $d_S = \prod_{j \in S} p_j$. The ...
- 34.3k
12
votes
1
answer
2k
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:
$...
- 3,691
4
votes
0
answers
145
views
Bounding an expression equivalent to Mertens function
Cross-posted from MathStackExchange, where the question is bountied but has not received any comment or answer)
Some months ago, I derived the following formula for the Merten's function $M(n)$ using ...
- 189
1
vote
0
answers
78
views
Partial sums of Möbius function and Euler characteristic of a simplicial complex for closed sets of a topology on the prime powers?
In A cell complex in number theory by Anders Björner, 2011 a number theoretic cell complex is described which has the property that the Euler characteristic is related to the Mertens function:
$$M(n) =...
- 3,064
0
votes
0
answers
123
views
Explicit upper bounds on the number of primes up to the square of the $n^\text{th}$ prime number $p_n$
I'm looking for explicit upper bounds on the number of primes up to the square $m=p_n^2$ of the $n^\text{th}$ prime number.
Such estimates can rely on the knowledge of the exact number of primes up to ...
- 727
0
votes
0
answers
353
views
On a Duality between Riemann-weil explicit formula and Abel- Plana summation of trigonometric prime counting function:
Consider the analytic function $g(x)$
Now define
$f(x)=g(x)\frac{\sin^2\left(\frac{π\Gamma(x)}{2x}\right)}{\cos^2\left(\frac{π}{2x}\right)}$
Such that
$|f(x+it)|=o(e^{2πt})$
uniformly for every $x$...
- 790
21
votes
4
answers
1k
views
Are there open problems for primes which are known for probable primes?
Define "probable prime" (PP) to be natural $n>1$ satisfying $2^{n-1} \equiv 1 \pmod{n}$ or $n=2$.
Probable primes are the union of the primes and base two pseudoprimes.
This definition is much ...
- 25.4k
8
votes
0
answers
150
views
Can P-recursive functions assume only prime values?
A function $f\colon \{0,1,\dots\}\to \mathbb{R}$ is P-recursive if
it satisfies a recurrence $$
P_d(n)f(n+d)+P_{d-1}(n)f(n+d-1)+\cdots+P_0(n)f(n)=0,\ n\geq 0, $$
where each $P_i(n)\in \mathbb{R}[n]$ ...
- 50.8k
1
vote
1
answer
78
views
Minimum value of a function involving the divisor counting function
Fix any positive integer $n\in\mathbb{Z}^+,$ and consider the function $f_n : \mathbb{Z}^+\setminus\{n\}\to\mathbb{Z}^+$ given by $$f_n(t)=\sigma_0(n)+\sigma_0(t)-2\sigma_0(\gcd(n, t)),$$ where $\...
- 63.9k
3
votes
0
answers
153
views
On a theorem by Iwaniec about binary quadratic polynomials representing infinitely many primes
In Theorem 1.1 (i) of http://matwbn.icm.edu.pl/ksiazki/aa/aa24/aa2451.pdf, Iwaniec showed that a certain type of quadratic polynomial $P(x,y)$ represents infinitely many primes, where $(x,y) \in \...
- 333
1
vote
2
answers
383
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
$$
...
- 1
1
vote
0
answers
99
views
On the existence of a sequence of prime numbers satisfying a recursion relation
I am interested in the following question. I will be grateful for any reference, comment, or solution.
Let $p_1\geq 5$ be a given prime number. Does there exist an infinite sequence of prime numbers $...
- 391
8
votes
2
answers
393
views
Can exist a positive integer number $x$ such that $a_1=x$ and $a_n=2a_{n-1}+1$ are not prime for all $n \ge 1$?
Using my computer, I found that the most of positive integer number $x$ such that $a_1=x$ and $a_n=2a_{n-1}+1$ is prime number after a few iterations. But exist some positive integer numbers, my ...
- 39.9k
20
votes
3
answers
3k
views
What is the simplest proof that the density of coprime pairs does not go to zero?
By density of coprime pairs, I mean the proportion of pairs integers between $1$ and $x$ which are coprime.
This is known to be asymptotically $1/\zeta(2)$.
I want something much weaker, namely that ...
- 7,831
11
votes
0
answers
436
views
Can we rule out the possibility that $\sqrt[3]{2}$ is small modulo every prime?
Consider a prime $p$ such that the polynomial $X^3-2$ splits into linear factors over $\mathbb{F}_p$: $X^3-2 = (X-\alpha_p)(X-\beta_p)(X-\gamma_p)$. It seems reasonable to expect that (identifying $\...
- 12.9k
2
votes
0
answers
191
views
The exponential sum over primes on average
In https://academic.oup.com/blms/article-abstract/20/2/121/266256?redirectedFrom=fulltext Vaughan shows the following bounds for the $L^1$-mean of the exponential sum over primes $$\sqrt x\ll \int _0^...
- 1,381
4
votes
1
answer
258
views
Density of numbers where a large prime factor satisfies a congruence
I am looking for an upper bound on the number of integers $n<x$ such that $n$ has a prime factor $p>\log(x)^{(1+\delta)}$ such that $p \equiv a \mod b$. Where $a,b$ are fixed and coprime and $0&...
CommunityBot
- 1
4
votes
2
answers
730
views
Looking for paper: Weil's original 1952 "Sur les formules explicites de la théorie des nombres premiers"
I am looking for a source (preferably online) for Weil's original 1952 paper on the explicit formula. I am aware of an english translation available here, but would like to have access to the original ...
- 5,407
2
votes
0
answers
182
views
Integers as polynomials in infinite variables
This question is more of a request for reference or ideas than else. Forgive (or correct) if there are imprecisions or blatant mistakes.
The main idea is that the unique factorization theorem for $\...
- 29
3
votes
0
answers
317
views
Prime Hadamard matrices
Assume that $n$ is a sufficiently large number. Is there a Hadamard matrix $H_{4n \times 4n}=(h_{ij})$ with the last row and the last cloumn $J$ (thet is, for every $k$, $h_{k,4n}=1$ and $h_{4n, k}=1$)...
- 696
19
votes
2
answers
2k
views
For what subsets S of (Z/nZ)* is there a Euclidean proof that there are infinitely many primes whose residues lie in S?
For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof ...
CommunityBot
- 1
4
votes
1
answer
266
views
Prime omega function values on a product of prime powers predecessors
Let $p_1, ... , p_n, ...$ be the prime numbers in order. Define
$$
P_n = \prod_{k=1}^n p_k^q
$$ It is known that $\omega(P_n) = n$ where $\omega(\cdot)$ is the little prime omega function. For a given,...
- 14.6k
3
votes
1
answer
188
views
Is there a uniform family of polynomials $f_p(x) =x^2 + a(p)x + b(p)$ such that $f_p(x)\in \mathbb{Z}[x]$ is irreducible and irreducible mod $p$?
Let $p\in\mathbb{Z}$ be a positive prime number.
Is there a "uniform" family of polynomials $f_p(x) =x^2 + a(p)x + b(p)$ of degree two such that $f_p(x)\in \mathbb{Z}[x]$ is both irreducible ...
- 704
3
votes
2
answers
465
views
Least number coprime to a given integer
For a positive integer $n$ let $$f(n):=\min\{m\in \mathbb N: m>1, \gcd(m,n)=1\} .$$
Equivalently, $f(n) $ is the smallest prime not dividing $n$.
Is there any upper bound literature for this? It is ...
- 20.8k
3
votes
2
answers
2k
views
What is the importance of Polignac’s conjecture?
The twin-prime conjecture (also known as Polignac’s conjecture, 1846) states that there are infinitely many twin primes (pairs of primes that differ by 2; for example, 3 and 5, 5 and 7, 11 and 13, and ...
CommunityBot
- 1
2
votes
0
answers
411
views
On two "versions" of abc conjecture
Let $a,b,c$ be coprime nonzero positive integers such that $a+b=c$. The ABC conjecture states that for any $\varepsilon>0$, we have $$c < C_{\varepsilon}\operatorname{rad}(abc)^{1+\varepsilon}.$$...
- 365
-1
votes
1
answer
147
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 ...
11
votes
2
answers
1k
views
Do consecutive integers have a big prime factor?
Let us say that three consecutive positive integers $(m-1,m,m+1)$ have a big prime factor if the largest prime factor $p$ of $N=(m-1)m(m+1)$ satisfies $e^p>N$.
I ckecked that it is true for all $m&...
CommunityBot
- 1
0
votes
0
answers
75
views
Existence of smooth integers in every residue class with large modulus
Let us say that a positive integer $x$ is $y$-power smooth, if the largest prime power divisor of $x$ is at most $y$. In what follows, let $C$ be any real number larger than $1$ and, for an integer $x$...
- 1,663
1
vote
0
answers
195
views
Conjectural values of some determinants involving Legendre symbols (II)
Let $p$ be an odd prime, and let $(\frac{\cdot}p)$ denote the Legendre symbol. Motivated by the evaluation of the determinants
$$\det\left[\left(\frac{j+k}p\right)\right]_{1\le j,k\le(p-1)/2}\ \ \text{...
CommunityBot
- 1
20
votes
2
answers
1k
views
Median largest-prime-factor
Let $P(n)$ denote the largest prime factor of $n$. For any integer $x\ge2$, define the median
$$
M(x) = \text{the median of the set }\{P(2), P(3), \dots, P(x) \}.
$$
Classical results of Dickman and ...
- 1,446
13
votes
1
answer
1k
views
About the number of primes which are the sum of 3 consecutive primes (OEIS A034962)
I made some numerical simulations about the number of primes which are the sum of 3 consecutive primes (OEIS A034962), that is for instance:
$$5+7+11=23$$
$$7+11+13=31$$
$$11+13+17=41$$
$$17+19+23=59$$...
- 365
4
votes
4
answers
913
views
Let $X$ be a positive integer. Then $\pi{(X+\ln^2{X})}-\pi{(X-\ln^2{X})}>\ln{X}$?
The prime-counting function is the function counting the number of prime numbers less than or equal to some real number $x$. It is denoted by $\pi{(x)}$. Using my computer I found that for any ...
- 7,182
4
votes
0
answers
335
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 $g_n$ or $g(p_n)$ is the difference between the $(n+1)$-st and the $n$-th prime numbers. Using my ...
- 12.9k
3
votes
1
answer
401
views
Probability of finding a prime number between $x-\ln(x)$ and $x+\ln(x)$
Using my computer, I found that in the interval $[1, N]$ the probability of finding a prime number between $x-\ln(x)$ and $x+\ln(x)$ is greater than constant $c$ where $N=10^2, 10^3,...,10^{9}$, $x$ ...
- 105k
2
votes
0
answers
157
views
Conjecture: $x^4+1$ is never Wieferich prime
Related to this question and Alexander Kalmynin's answer.
For natural $n$ define $J(n)=(2^{n-1}-1) \bmod n^2$
and if $n$ is power of two define $J(2^n)=1$ (this is artificial, just to
avoid triviality ...
- 25.4k