All Questions
19 questions
4
votes
0
answers
266
views
How dense are quotients of smooth numbers?
As usual, call a positive integer $y$-smooth if it has no prime factors greater than $y$. Write $S(x,y)$ for the set of $y$-smooth integers $\leq x$. Write $R(x,y)$ for the set of quotients $\{a/b: a,...
- 20.2k
7
votes
0
answers
270
views
How dense are (very but not extremely) smooth numbers? Can they be found in most (not very) short intervals?
An integer is said to be $y$-smooth if it has no prime factors $>y$. Let $y$ be "medium sized", meaning $(\log x)^{1+\epsilon} < y < \exp((\log x)^{2/3})$ or so. (Why this range of ...
- 20.2k
1
vote
0
answers
128
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 ...
- 9,114
2
votes
0
answers
70
views
Twin prime distribution centering twice a semiprime
What is the conjectured distributional behavior of semiprimes $pq$ ($p$ and $q$ are primes) having the property $2pq+1$ and $2pq-1$ are primes?
- 13.9k
1
vote
0
answers
65
views
Distribution of number of prime factors of $p^k\pm1$
What is the behavior of number of prime factors of integers of form $p^k\pm1$ where $p$ is a fixed odd prime or $2$ and $k$ varies over positive integers?
- 13.9k
1
vote
0
answers
96
views
Smooth number pairs satisfying a congruence
Let $\mathcal P=\{p_1,\dots,p_{2t}\}$ be $2t$ primes between $2^\ell$ and $2^{\ell+1}$ and fix an exponent bound $a\in\mathbb Z_{\geq2}$.
Fix $N\in\mathbb N$ whose prime factors $p$ satisfy $p>2^{\...
- 13.9k
1
vote
0
answers
52
views
Probability of factor of particular size
What is the probability that an integer $a$ picked uniformly in $[t/2,t]$ has a factor in $[t^{\alpha},2t^{\alpha}]$ where $\alpha\in(0,1)$? I am interested when $\alpha=1/3$ but if there is a general ...
- 1,826
3
votes
0
answers
323
views
If $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then is one of its prime factors always greater than $17$? [closed]
Is it true that if $p^2 - q^2$ is a perfect square where $p$ and $q$ are primes $> 5000$ then it has a prime factor greater than $17$?
Note: This question was asked in MSE but did not receive an ...
- 5,470
20
votes
1
answer
2k
views
Circle $x^2 + y^2 = n!$ doesn't hit any lattice points for any $n$ except for $0$, $1$, $2$ and $6$ or does it?
I stumbled across the following problem in high school:$$
x^2 + y^2 = n!
$$
I tested it within my laptop capabilities, watched a 3b1b video Pi in prime regularities, where he explains how to find the ...
- 343
0
votes
1
answer
431
views
Reason Coppersmith fails here?
Take classic problem of finding $P,Q$ in balanced semi-prime $N=PQ$.
$P$ has a binary expansion and so does $Q$. We can set the binary $0/1$ variables to be $x_1$ through $x_{\lceil\log P\rceil}$ and $...
- 13.9k
1
vote
1
answer
144
views
Factoring with partial information on gaps
If $N=PQ$ is a semi-prime with $P=N^{\frac12 +\delta}$ and $Q=N^{\frac12-\delta}$ then if we know $\delta\in(0,\frac12)$ to a reasonable precision we can factor $N$ quickly. What precision (number of ...
- 13.9k
2
votes
0
answers
127
views
Coppersmith's method to quadrivariate degree $2$ polynomials that behave as bivariate?
We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...
- 13.9k
7
votes
1
answer
382
views
$\log \log p / \log \log n$, where $p|n$, gets equidistributed in [0,1] (for almost all $n$)
According to Hardy-Ramanujan/Erdős-Kac we know that usually there are $\sim\log\log n$ prime numbers in a factorization. But if you pick up a natural number at random, and you factor it, what is the ...
- 1,384
0
votes
1
answer
184
views
Upper bound for tuple of exponents of prime factorization
Let $a(n)$ be the $k$-ary tuple of the exponents of the prime factorization of $n$. For example,
$$a(5184)=a(2^{6}⋅3^{4})=(6, 4), a(65536)=a(2^{16})=(16).$$
Formally, let $p_{1}^{a_{1}}, p_{2}^{a_{2}...
- 25
2
votes
1
answer
332
views
Upper bound for product of exponents of prime factorization
Let $p(n)$ be the product of the exponents of the prime factorization of $n$. For example,
$$p(5184)=p(2^{6}\cdot 3^{4})=24,\qquad
p(65536)=p(2^{16})=16.$$
Is $p(n) = O(\log^{k}(n))$ for some constant ...
- 25
3
votes
1
answer
519
views
How much space between these smooth numbers?
In looking at OEIS sequence A063539, $1,8,12,16,18,24,27,30,32,36,40,45,...$ I noticed that the first 1000 members were less than 4000, and thought there were no large gaps between them. What (if ...
- 13k
7
votes
1
answer
1k
views
Results on the largest prime factor of $2^n+1$
A work of Cameron Stewart (the paper has appeared in Acta Mathematica), proving a conjecture of Erdos, Stewart shows that
the largest prime factor of $2^n-1$ is at least
$n \times \exp\Big( \frac{\...
- 267
5
votes
1
answer
214
views
Dynamics of the distribution of prime factorization types in increasing intervals
I've tagged this as reference request as surely this question must be very well investigated, I just don't know how to look for it. Most likely the perfect answer will be in form of a keyword for ...
- 18.4k
2
votes
1
answer
2k
views
Can infinite polynomials be expressed as a product of its linear factors?
Background:
In the 1700s, Euler solved the Basel Problem, which was to solve $\sum_{n=1}^\infty\frac{1}{n^2}$ in closed-form. Euler showed that it was equal to $\frac{\pi^2}{6}$ by first expressing $\...
- 487