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


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.

  • 0
    What's the use case for this?
  • 0

    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.
  • 0
    @Wisecrack Okay, but why is it useful? If you want a number that can be factored quickly, just store the factors.
  • 0

    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?
  • 4
    I knew it was you after reading the first three words of this rant
  • 0
    @nitwhiz yes, but does it intrigue you?

    Found an exception already, though it may because it is trivial.


    int('100000001000000', 2) =


    16448/(2*3) =


    (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.
  • 1
    hardly following
  • 1
    Yo wisecrack. You tryin to bruteforce math?
  • 1
    @M1sf3t 不不不不不不不不不不不不不不不不不不不不不不不不不不不不不不

    I'm with you
Add Comment