Hacker News Reader

Comment by 7373737373 | Hacker News Reader

If (efficiently) searching for a disproof requires fast (prime) factorization, are there connections to other open problems?

View on HN

In this case efficiently searching for an example n does not require fast factorization. We are search for a number n such that σ(n)/(n ln(ln (n))) is large. That mean we want σ(n) large, and that means n will have to have lots and lots of small factors.

So your comment is relevant, but in this case, it doesn't provide new insight.

I just checked how one could implement the search, finding all the divisors for σ(n) can be done with a prime factoring algorithm and then calculating the number of their combinations. But that's just one way.

You can make that more efficient by noting that you need σ(n) to be large, so if you know that, for example, the smallest factor of n is more than ln(n)^4 then you already know this won't be a counter-example. So general purpose factoring doesn't really help in this search, even though, as you say, it's one (naive and simple) approach.

It will work for small n, but it will quickly become infeasible.

I see it now, thanks!

Oh yes. The Riemann Hypothesis is connected to just about everything; lots of statements have been shown to either follow from it or be equivalent to it.

I think you could just generate candidate counter-examples by multiplying factors, rather than the other way around.

Yes! I was just in the middle of doing this in a sage notebook!

Good thinking :)

I have to think some mathematician had already done this for like every pattern they could think of but ya never know. Never hurts to try... As long as you don't delude yourself that is.

update: Okay so the tricky thing here is that in order to naively generate the divisors (and sum over them), you'd have to consider butt-tons of combinations of prime factors, including many, many, many repeated ones.

So finding divisors given a list of factors scales very rapidly.

It's really fun to take shots at these hard problems. It's like any way you attack them they're hard, even when you don't intuitively expect it.

Yes. In fact, if we ever manage to build a quantum computer with a non-trivial amount of qubits, we can expect exponential improvement in the performance of any prime number-related numerical research.

Reply on news.ycombinator.com