thecrazyt / factorization-maps

Generating and using factorisation maps for fast factorisation.

factorization-maps

Generating and using factorization maps for fast factorization.

How to interpret output?

0000000000000000000000010000000000000000000000000000000000000000 0000000000010000000000000000000000000000000000000000000000000000 0000000100000000000000000000000000000000000000000000000000000000 0000010000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0001000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0010000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0100000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000 1000000000000000000000000000000000000000000000000000000000000000

To make it short:

Each column is x(1 starts from left).

Each row is y(1 starts from top).

Each 1 means its divideable by that number.

Currently its just a PoC and no input is possible.

The current number factorized is 24.

You can read from the map that the number is divideable by 24,12,8,6,4,3,2,1. (x read from top to down)

Future use would be to generate maps for 2^n (where n is the bit-width of the maximum possible number).

Currently those maps would be quite big, i'm looking for a way to make them smaller (or somehow find an even better way)

I'm not using a known algorithm, because i want to discover a new way of doing it.

factorization-maps's Issues

Offtopic - pi

Just came across this one ...
If you type this into wolfram alpha:

4((1/2)!^2)

The result is PI .
Maybe has to do with stirling formula or something similar(that is normaly only an approximation)

Sin/Taylor Series

Need to investigate if this leads to something:

for p=prime number:

Since sin(pi) is zero, and every multiplication with "0" equals "0", the formula checks if "p" is divideable through any "n" (for 2 <= n < p).

SIN can be written as Taylor Series:

Note:

• the Taylor Series is only an approximation that can contain errors
• simplier formula without sin:
• of course one could use modulus in a formula, but that shurely cannot be reduced

Not so shure about this, but maybe every prime number could be somehow related to PI.

Edit:
(actually ... NO since PI can be used as constant and the sin-formula outputs 0 for every p/n = natural number)

A small note to myself

Maps are way too big.
Although factorization_numbers_test.jl proofs that it can be made even smaller its still too big.

Currently i'm thinking about another way.
At the moment I store redundant information.

Another idea that came into my mind is the following:
Because I'm checking against (x*y) & 2^n I store redundant information.

For example (xy) & (2^1) is the same as (2xy) & (2^2).
And thats one reason why those maps look so similar.
What this also means ... is that (xy/2) & 2^1 should be the same as (x*y) & 2^2.
Somehow this makes me believe it might be possible to reduce the current usage dramatically.
(maybe by a floating point number that gets increased)
Sadly i currently have no time to think about this in detail (yet).

Generate smaller primes from big primes

Sadly does not seem to allways work.

True:
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*3*4*5*6
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5-1*2*2*3*4*5
https://www.wolframalpha.com/input/?i=prime%281001%29-2*3*4*5*6*7
https://www.wolframalpha.com/input/?i=prime%281001%29-2*3*4*5*6*7-2*3*3*4*5*6
https://www.wolframalpha.com/input/?i=prime%281001%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5
https://www.wolframalpha.com/input/?i=prime%281001%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5-1*2*3*3*4*5

False:
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5-1*2*3*3*4*5
https://www.wolframalpha.com/input/?i=prime%281001%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5-1*2*2*3*4*5

-1?
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*4*5-1*2*3*4*4*5
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*3*4*5*6-1*2*2*3*3*4*5
https://www.wolframalpha.com/input/?i=prime%281000%29-2*3*4*5*6*7-2*3*4*4*5*6