Join devRant
Do all the things like
++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatar
Sign Up
Pipeless API
From the creators of devRant, Pipeless lets you power real-time personalized recommendations and activity feeds using a simple API
Learn More
-
@gronostaj
If you can go from p to f w/o initially knowing the initial factors, it's another method to factor a product.
I'm a bit of an idiot savant (well the former more than the latter lol), and I've just basically been throwing every possible iteration and combination of ideas at faster factorization solutions.
If you don't know where to begin, try everything.
And I'm hoping this is the solution, or part of it. -
@Wisecrack Okay, but why is it useful? If you want a number that can be factored quickly, just store the factors.
-
@gronostaj
All combinations of factors?
You're probably unfamiliar but I made a sensational claim a while back (a few) to be able to factor very large numbers quickly. Admittedly I was foolhardy but this is basically the thrust of it.
If you can derive f from p, then *maybe* factoring p can be done in less than exponential time. Of course it likely trades time for memory requirements but I still don't know enough at this point.
Why? Are you familiar with the subject or math? What are you thinking? -
@nitwhiz yes, but does it intrigue you?
Found an exception already, though it may because it is trivial.
47*7
int('100000001000000', 2) =
16448
16448/(2*3) =
2741.3333333333335
(we stop here because we cant divide cleanly)
3 should be the index, but in this case the correct index for 7 in a list of primes is 4 (assuming a 1's based index).
This is the kind of errors that I make that make people think I'm just fucking with them.
Math is hard.
When you wanted to know deep learning immediately
:)) finally a good answer
Math question time!
Okay so I had this idea and I'm looking for anyone who has a better grasp of math than me.
What if instead of searching for prime factors we searched for a number above p?
One with a certain special property. BEAR WITH ME. I know I make these posts a lot and I'm a bit of a shitposter, but I'm being genuine here.
Take this cherry picked number, 697 for example.
It's factors are 17, and 41. It's trivial but just for demonstration.
If we represented it's factors as a bit string, where each bit represents the index that factor occurs at in a list of primes, it looks like this
1000001000000
When converted back to an integer that number becomes 4160, which we will call f.
And if we do 4160/(2**n) until the result returns
a fractional component, then N in this case will be 7.
And 7 is the index of our lowest factor 17 (lets call it A, and our highest factor we'll call B) in our primes list.
So the problem is changed from finding a factorization of p, to finding an algorithm that allows you to convert p into f. Once you have f it's a matter of converting it to binary, looking up the indexes of all bits set to 1, and finding the values of those indexes in the list of primes.
I'm working on doing that and if anyone has any insights I'm all ears.
question
factorization
math
primes