Skip to main content

All Questions

Filter by
Sorted by
Tagged with
9 votes
2 answers
1k views

runs of consecutive non squarefree integers

This question gained no attention at Math SE. Call a sequence of $k$ consecutive naturals squary if each one of them is divided by a square > 1. The Chinese Remainder theorem trivially guarantees us ...
Wolfgang's user avatar
  • 13.4k
9 votes
3 answers
980 views

$\omega(p^n - 1)$ as $n \rightarrow \infty$

Although I am also interested in the number of distinct prime factors (not counting multiplicity), today I use $\omega(m)$ to denote the number of (positive) prime factors (with multiplicity) of the ...
The Masked Avenger's user avatar
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 ...
Luca Ghidelli's user avatar
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 ...
joro's user avatar
  • 25.4k
6 votes
1 answer
1k views

Using the decomposition $641 = 5^4 + 2^4$ to factor $F_5$

The question in the title arises from a problem in Stewart's "Galois Theory, Third Edition" (and possibly elsewhere) which has been bugging me for a few days since reading it: Problem 19.5 (p. 224) ...
ARupinski's user avatar
  • 5,191
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 ...
მამუკა ჯიბლაძე's user avatar
4 votes
1 answer
288 views

Is total degree version and $x,y$ degree version of Coppersmith's theorem correct?

The notes here https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf have the note 'Small decryption exponent $d$: so far the best known attack recovers $d$ if it is less than $N^{.292}$. This uses a ...
Turbo's user avatar
  • 13.9k
3 votes
3 answers
382 views

Closed formula for number of ones in a proper factor tree

Edit [2023 Dec 7]: One of my specific wonders, along with that of students, is around when a recursive formula might have – or be expected to have – an explicit or closed formula. What is the ...
Benjamin Dickman's user avatar
3 votes
1 answer
137 views

Subexponential algorithms that apply only one of factoring and discrete logarithm?

Shor (quantum polynomial), Number Field Sieve (subexponential), Pollard rho (square root) all have both factoring and discrete logarithm over $\mathbb F_p^*$ variants. What are the subexponential ...
Turbo's user avatar
  • 13.9k
2 votes
1 answer
450 views

Is there a "small $\omega$" number theorem?

In my studies of how primes jump (search this forum for a link), a question has been raised which may have been studied. Can anyone jump-start my literature search with references regarding the ...
Gerhard Paseman's user avatar
2 votes
0 answers
140 views

Integers with exactly three factor pairs whose successors are relatively prime

I am interested in the following problem, and will appreciate pointers around how it can be solved – partially or fully – and/or indicators around whether it is even tractable: Characterize $N \in \...
Benjamin Dickman's user avatar
1 vote
1 answer
178 views
+50

On a probabilistic integer factorization algorithm given bounds for one prime factor

We got a probabilistic integer factorization algorithm and experimental evidence with large integers given bounds for one factor. Let $D \ge 2$ be real number and let $p,q$ be primes and $N=pq$. ...
joro's user avatar
  • 25.4k
0 votes
0 answers
138 views

A diophantine equation involving partial sums of exponentials similar than the equation in Fermat's Last Theorem

I'm curious about the following diophantine equation from my invention: I don't know if this is in the literature, I wrote it using creativity in an attempt to write a variant of the equation in ...
user142929's user avatar