Ranter
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
Comments
-
Wrote a little additional code and apparently all the failures were strictly products that had 3, 5, 7, or 11 as their lowest factor
-
Extended it to the first 2000 primes (first 2 million product of two unique non-trivial factors).
As predicted, only products of 3, 5, 7, and 11 failed the test. All others past.
Nifty.
The implication is the factors that fail to expand into larger products with bigger factor trees, never extend beyond 3, 5, 7, and 11. And consequently all other products would adhere to this solution.
In the case of brute forcing prime factorization, this defacto cuts the search space in half, or at least your *outer* loop is never going to be greater than your lowest factor divided by 2.
Also I haven't really explored the implications of the larger factor tree when you happen to come across the correct i value. Nor if there are earlier points in the search could terminate before beginning factorization.
It's remains entirely impractical at the moment, but it was still a fun little curiosity. -
It's too early for this horseshit lmao
Interested though.
Wouldn't it be interesting if you could find some underlying purpose for prediction based on this -
Nihil757552yI know people from the way-back think this is what you do with a computer,
But honestly mate, if it ain't got/serves an API and/or stores selfies - it's useless :P -
@AvatarOfKaine *singsong voice* it's never too early for MATH!
Hows life Kaine? The missus polishing your knob enough? Getting enough sleep and vigorous exercise? Been eating your leafy greens?
I havent seen you for a minute. What you been up to? -
@Nihil75 "its useless"
I know! Says so in the post. Oh the humanity.
If I'm not careful I might even cause it to rain cats and dogs. -
@Frederick the size of the products tend to grow extremely fast too.
Like too big for modern techniques like ECM to factor quickly.
I'm hoping though that some overlapping properties between the original products and the derived products, might allow for some interesting approaches. -
@Wisecrack settled issues out west
Got my knob polished by 5 different women about 2 years ago
Getting lots of exercise
Considering taking a trip somewhere sooner rather than later to accomplish another task
Overall sick of traveling pointessly and seeing the same content in person and online
Don't eat leafy greens lol -
scor38042y@Wisecrack
Are you self taught?
Like from the very beginning of professional level or from after school years?
I think I have literally witnessed you grow.
Asking for readings.
Making assumptions.
Bringing them up in conversation.
And bit by bit making more and ever more sense.
What are you studying?
What's your learning path?
I think I'm quite impressed, anyway. -
@scor thanks. Rough childhood so I didnt really start learning till a few years ago. Wont waste your time with the whole life story.
Self taught. Just now, very slowly, picking up linear algebra. Would love to explore math and algorithms full time one day but I dont have the means or credentials for university.
Learning path is anyone's guess with the state of the world the way it is.
Gonna just keep grinding and rain- manning by night.
I want to eventually explore statistics. Did you know our ideas of mean, mode, and average have geometric equivalents? And I was thinking those measures of central tendency are all derived from *euclidean* geometry, but what about measures derived from non-standard geometry? Is there any applications there? Any utility or interesting connections to other types of math, or new interpretations of old problems? -
In other news you need to have your beyond compare license returned to you or you'll crack the fucking pro edition !
-
@AvatarOfKaine Iran called and wants you to finish the guidance systems for its missiles. You know the ones that use the super secret ps2 chipsets?
-
@AvatarOfKaine it's a reference to an old pentagon fluff peace spreading FUD about why playstation two's had been export restricted.
it's one of my fondest memories. -
@Wisecrack and of course no knowledge of that here where ps2 were everywhere although there is a faint familiarity now that you mention this ghe 2nd time
-
@AvatarOfKaine they were paranoid iran would some how reverse engineer the chip the emotion engine ran on, and put it into nukes or some crazy-stupid shit like that.
Almost as absurd as making people take their shoes off at the airport because of one lunatic mad at the cost of those little liquor bottles on flights. -
scor38042y@Wisecrack
Well, yes, I've been taught and flabbergasted about such cross functionalities in maths.
Especially in higher education, despite staying in the financial mathematics sphere.
Gosh I wish I could have spent more time with all that.
Then, I lived in Germany that time, where education follows highly typified patterns. I guess one would need a well typified culture to be allowed a properly structured learning environment, if not self imposed. -
@scor
"the financial mathematics sphere."
Very cool. Was it tedious or exciting?
Did you get to solve interesting problems?
"I guess one would need a well typified culture to be allowed a properly structured learning environment, if not self imposed."
Thats good you had that opportunity.
What I do is I just keep going until I bump up against the ceiling of
what I know. Then I ask "what do I need to know to do this next thing?"
And then I go and learn it. Or just enough to get things done.
What kind of systems have you worked on? (if thats not asking too much) -
Made a few additional modifications to what I already posted today and the results have factors that are always either a-smooth or, if not, b-smooth.
The two solutions are :
(p-(((abs(((((p)-(4**i)-9)+1))-((((4**i)-(p)-9)-2)))-p+1)-p)%p))
and
(p-(p%(p-(((abs(((((p)-(4**i)-9)+1))-((((4**i)-(p)-9)-2)))-p+1)-p)%p))))
In addition to being smooth, all the prime factors in the new product are trivial.
I have to write a factorization test to confirm this, but its what I'm seeing.
Reducing from 9**i to 4**i also helped to reduce the precision requirements.
I don't have access to the resources to confirm it holds for the products of more than the first two thousand primes though.
@atheist, @hitko, @Fast-Nop any input on relevance to things like TWIRL and TWINKLE, esp. b-smooth factors? You guys are far and away more familiar with math than I am.
https://en.wikipedia.org/wiki/... -
@Fast-Nop lol, the smiley face gives it away.
"once burned, twice shy" I suppose.
But the results appear real for a change.
I was hoping for someone that had a better understanding of the general number field sieze in relation to smooth numbers and why exactly the latter is relevant to factorization. -
@Wisecrack As for the latter, my guess is that if you want to factorise a large number N and can determine that there is no prime factor greater than B, then you have already excluded the search space between B and sqrt(N). That would help if the two prime factors are several orders of magnitude away from each other.
If you repeat that process and lower B until you fail, then you have a search range where a prime factor could probably be hiding. -
@Fast-Nop "As for the latter, my guess is that if you want to factorise a large number N and can determine that there is no prime factor greater than B, then you have already excluded the search space between B and sqrt(N). "
So, if I'm understanding you correctly, I would be looking for a variation of the formula where [a] was the *smallest* factor in the new larger factor tree? -
hitko31482yApparently DevRant won't allow me to post a comment containing lots of special characters, so here's a link to a paste: https://pastebin.com/1qJ6rrR0
-
@hitko delivers.
Keep in mind too, 9^i his fails for any products of 3, 5, 7, 11.
And 4^i fails for any products of 3 to 19.
Question: is what you're showing here, that the approach fails when theres a sufficient difference between b and a? Laptops currently updating so I cant check your results at the moment. -
hitko31482y@Wisecrack Basically if B is smaller than about 3^A (see previous comment for the exact value), you get a variation of modular exponentiation for prime exponent A, which should hold as long as A is a prime number greater than 3.
If B is instead larger than about 3^A, the absolute value in your formula somehow messes the whole thing up and the equation no longer holds. -
@hitko I just figured out what you did (really only because you told me). Thank you hitko for excising the abs from the code.
Noticed the original exponent (i) has been removed.
What was your thinking on that? And in its original form, do you see any method of lowering the requirement to find a/2?
Say to a/4, or a/8 or some n other than 2? -
@hitko also I'm only passingly familiar with modular exponentiation (because, I'm embarrassed to admit, I just read the wikipedia article.)
If modular expotentiation is easy, but finding the modulus is hard, how does this relate to the original product and the product produced by this--how does it relate to these two products sharing (a) as a common factor? -
hitko31482y@Wisecrack What I did only works because 9^n is the same as 3^(2n), therefore 9^n can be replaced by 3^((2n + 1) - 1), and we know that n=floor(a/2) is equivalent to a=2n+1 when (a) is a prime number. Nothing as simple can be done for floor(a/4) or floor(a/8), and nothing similar works if (a) can be an even number.
The thing with modulo is that (v^x)%c is the same as ((((v%c)*v)%c)*v)%c ... Now, in your case (v) equals 3, which is a prime number, and (c) is also a prime number. Let's assume c=7:
1%7 = 1
(1*3)%7 = 3
(3*3)%7 = 2
(2*3)%7 = 6
(6*3)%7 = 4
(4*3)%7 = 5
(5*3)%7 = 1
(1*3)%7 = 3
...
As you can see, the result is 1 exactly when x=k*(c-1), for any non-negative integer k. If I plug this into your original expression, I get 2*(1) - 2 = 0.
If either c or v aren't prime, you'll get to 1 in fever than c-1 steps, and the result of (v^(c-1))%c probably won't be 1. -
@hitko I'm really glad you revisited this because I was lost still. So what we did was discover a singular exception that works in this case because of the careful selection of numbers? Nifty.
-
"This only works because a = 2n+1"
What if we used something other than a/2?
For example what if we defined our primes as say 3n+1?
What would be the implications of that? How would the math change? -
scor38042yHeya @Wisecrack
Sorry, had not found the time to properly respond to your comment here.
Though you really shall have a look into this prime factor functions and mathematical distinguishing of number areals :
I personally assume it's more discreet in German. So here you go
https://de.wikipedia.org/wiki/... -
@scor Eh bien, mais pour comprendre cet article en Allemand, il faut d'abord avoir appris l'Allemand, et voilà le problème.
Non, probablement pas. Par contre, c'est plus joli. ^^
Related Rants
Heres a fairly useless but interesting tidbit:
if i = n
then
r = (abs(((((p)-(9**i)-9)+1))-((((9**i)-(p)-9)-2)))-p+1+1)
then r%a will (almost*) always return 0. when n = floor(a/2) for the lowest non-trivial factor of a two factor product.
Thats not really the interesting bit though. The interesting bit is the result of r will always be some product with a *larger* factor tree that includes the factor A of p, but not p's other larger factor, B.
So, useless from what I can see. But its an interesting function on its own, simply because of what it does.
I wrote a script to test it. For all two-factor products of the first 1000 primes, (with no repeating combinations, so if we calculated say, 23*31, we skip 31*23), only 3262 products failed this little formula, out of half a million.
All others reliably returned 0 for the following..
~~~
i = floor(a/2)
r = (abs(((((p)-(9**i)-9)+1))-((((9**i)-(p)-9)-2)))-p+1+1)
r%a
~~~
The distribution of failures was *very* early on in the set of factors, and once fixed at the value of 3262, stopped increasing for the rest of the run.
I didn't calculate if some primes were more likely to cause a product to fail or not. Nor the factor trees, nor if the factor trees had any factors in common between products, or anything of that nature.
All in all I count this as a worthwhile experiment.
If you want to run the code yourself, I posted it to pastebin here:
https://pastebin.com/Q4LFKBjB
edit:
Tried wolfram alpha just to see what it says, but apparently not much. Wish it could tell me more.
random
math
primes