Looking for someone to test a new factorization script I wrote.

https://pastebin.com/Td2XTKe6

Tested against a set of products from all primes under 1000. Worked even on numbers up to 87954921289

Worked for about 66% of the products tested.

Obviously I'm cheating a little bit because I'm checking for four conditions n%a == 0, n%a == 1, n%b == 0, and n%b == 1

It appears it is possible to generate the series from just the product, and then factor each result. The last factor in each each set of factors becomes x, and we do p%x and check for zero.
if it works, we've found our answer.

Kind of wonky but basically what its doing is taking p, tacking on a 0 to the right, and then tacking p to the right of *that*.

So if you had a product like

314

The starting number we look at is

3140314

The middle digit becomes i, and the unit digit becomes j.

Don't know why it works more often then not, and don't know if it would really be any faster.

Just think it's cool.

It's so trivial it *shouldn't* work, but it does.

Sooo... I will prolly dl it. But what then?

Floor() and ceil() on a cpu?
Putting this on a gpu would be better.

I don't get a single word

@Ranchonyx manually call the script, with any positive factors a and b.

If it says it found an Ns (a number swap) it means theres at least one trivial transformation that leads to fast factorization of the product.

The format is

NINJ

So if your product is 986, the first number this system tries is
9860986

Although I only tested it for products with two unique nontrivial factors, up to the 997th prime, or all the products under one million.

This just finds I ans J combinations that work.

For the actual factoring we do the same substitutions, and attempt to generate chains of trivial factors for each iteration of IJ.

If we found a combination that works, then the last factor in any given chain, will be one of the actual factors of our product.

Anyway did it run? And did it work at all for you?

@-ANGRY-STUDENT- I barely got decimal to work and still havent added that to the script to do larger numbers.

You are more than welcome to translate it. All it does is text swapping and iteration.
Should be trivial for a shader.

But actually you bring up something interesting. Was looking at conways constant, which gives the next number in a look-and-say sequence. And I thought, what if factorization isnt a factoring problem, but simply a text transformation problem?

You can actually look at the problem as run length encoding a "image" made of a "palette" of factors.
Each factor, 2, 3, 5, etc, becomes a color.

On a standard "image" (an untransformed product), the palette space of possible colors is huge.
This transforms the product from a large color space to a smaller one, composed of, at most five or six factors from what I've seen.
(Although when I write the actual factorizer, I'll collate the list of all trivial factors in the factor trees).

And because this is possible, we can actually precompute a list of bases that are the product of a combination of these trivial factors. And what that will enable you to do is change the product to another number that is of this special base, and consequently transform the factorization from a division problem into a simpler problem, as outlined in an earlier post.

Basically, you know those rules for quick division? "If it ends in 0 its divisible by 2 and five?"
You can actually derive those rules yourself using a certain change of base formula. So for every product we might try, we dont need to know the rules for every possible factor beneath it..

We only need to know the rules for determining if a product is a multiple of
2*2, 2*3, 2*3*5.. etc

Also from what I saw, the factor chain was always smooth, i.e. just one example, if 2 and 5 were present, 3 would always be present. So that reduces what we have to look for.

Wouldnt even have considered this before had you not commented.

What is the use case for this?

@iSwimInTheC faster bruteforcing.

Thats about it.

It varys considerably in timing but the bulk of numbers return pretty quickly. The second largest set of numbers return in about half the time it would take to bruteforce the lowest factor.

If this works its plausible theres other product transformations that are more efficient, or algorithms to better determine the variables I and J.

Lets say varying *any* two digits in a product works (instead of the middle and unit digit in the template), but the set of possible solutions is some percentage of the lowest factor of p (with a nontrivial factor A).

So searching each ends up being depth first.

But if we search *across* the digits at a shallow depth, some are bound to return an answer faster than others.

Thats just one example though.