So I made a couple slight modifications to the formula in the previous post and got some pretty cool results.
The original post is here:

The default transformation from p, to the new product (call it p2) leads to *very* large products (even for products of the first 100 primes).

Take for example
a = 6229, b = 10477, p = a*b = 65261233

While the new product the formula generates, has a factor tree that contains our factor (a), the product is huge.

How huge?

So huge I put the whole number in a pastebin here:

Now, that number DOES contain our example factor 6229. I demonstrated that in the prior post.
But first, it's huge, 2972 digits long, and second, many of its factors are huge too.

Right from the get go I had hunch, and did (p2 mod p) and the result was surprisingly small, much closer to the original product. Then just to see what happens I subtracted this result from the original product.

The modification looks like this:

The result is '49856916'
Thats within the ballpark of our original product.

And then I factored it.
1, 2, 3, 4, 6, 12, 23, 29, 46, 58, 69, 87, 92, 116, 138, 174, 276, 348, 667, 1334, 2001, 2668, 4002, 6229, 8004, 12458, 18687, 24916, 37374, 74748, 143267, 180641, 286534, 361282, 429801, 541923, 573068, 722564, 859602, 1083846, 1719204, 2167692, 4154743, 8309486, 12464229, 16618972, 24928458, 49856916

Well damn. It's not a-smooth or b-smooth (where 'smoothness' is defined as 'all factors are beneath some number n')
but this is far more approachable than just factoring the original product.

It still requires a value of i equal to
i = floor(a/2)

But the results are actually factorable now if this works for other products.

I rewrote the script and tested on a couple million products and added decimal support, and I'm happy to report it works.
Script is posted here if you want to test it yourself:

What I'll do next is probably add some basic factorization of trivial primes
(say the first 100), and then figure out the average number of factors in each derived product.

I'm also still working on getting to values of i < a/2, but only having sporadic success.

It also means *very* large numbers (either a subset of them or universally) with *lots* of factors may be reducible to unique products with just two non-trivial factors, but thats a big question mark for now.

@scor if you want to take a look.

  • 0
  • 0
    And my use of parenthesis is excessive, I know, I know.

    I have no explanation for why.))))
  • 2
    @Wisecrack that p2 mod p was going to be quite small is not actually surprising since the mod can never be bigger than the second number.

    If you do a mod with 3 the result will always be one of 0, 1 and 2.

    So in your case the number will always be below p to begin with.

    Other than that I can only look and admire since I have not read enough math to dig into it ;)

    Edit: fixed the result list
  • 0
    @Voxera Trust me whatever "remedial" math you've read likely beats what I've read. But thanks.
  • 0
    @hitko if you want to take a look and check the basic assumptions.
Add Comment