Post An4mecCd3K4L2LtCgC by futurebird@sauropods.win
(DIR) More posts by futurebird@sauropods.win
(DIR) Post #An4hynGv6jdVO8hP96 by futurebird@sauropods.win
2024-10-16T20:27:18Z
0 likes, 0 repeats
If I give you a big ol’ integer and say “I think this might be a combination of nCr something… but I don’t remember n or r— or maybe it’s just some integer. How do you efficiently test to see if it’s a possible result from that formula?I mean I could make a list up to the needed digits and search, but that isn’t very elegant. Other ideas?425037413705167549733#math #cs #annoying #
(DIR) Post #An4iDvBLyoWiGVJChE by clayote@peoplemaking.games
2024-10-16T20:30:00Z
0 likes, 0 repeats
@futurebird I meanDivide through by that constant and it becomes an ordinary factorization problemFor which there are sieves 'n stuff
(DIR) Post #An4iXhH5Oha0vJQ5qK by futurebird@sauropods.win
2024-10-16T20:33:36Z
0 likes, 0 repeats
@clayote Which constant?
(DIR) Post #An4ibigu4bBOTUPj9c by clayote@peoplemaking.games
2024-10-16T20:34:18Z
0 likes, 0 repeats
@futurebird C...?
(DIR) Post #An4ijFbO6pFoZcQPtQ by richpuchalsky@mastodon.social
2024-10-16T20:35:39Z
0 likes, 0 repeats
@futurebird what is " a combination of nCr something"? Does that mean n times C times r where C is known, or something else?
(DIR) Post #An4irA42aBK5iNbDaC by ineiti@ioc.exchange
2024-10-16T20:37:03Z
0 likes, 0 repeats
@futurebird are n and r also integers? Is C known? I think if they're not prime, and C is not known, you cannot tell if it's a product or not. For example 8 could be 2x2x2, or just 8.Am I missing something?
(DIR) Post #An4k6wrNXjw9Lllhwm by OWOP@mastodon.world
2024-10-16T20:51:10Z
0 likes, 0 repeats
@futurebird TWW: There are forces that shape this world and your place in the moment that you cannot perceive. *My favorite is to add up the integers of the constant and result and check for a rational relationship. I do this with people I meet on the street too. OWOP
(DIR) Post #An4kR2dzkPaB555c4e by dogfox@kpop.social
2024-10-16T20:54:47Z
0 likes, 0 repeats
Is nCr read "n choose r"?@futurebird
(DIR) Post #An4kss72UsmQWgwfKq by futurebird@sauropods.win
2024-10-16T20:59:50Z
0 likes, 0 repeats
@dogfox yes
(DIR) Post #An4l3DLOPi8HGpagCW by futurebird@sauropods.win
2024-10-16T21:01:42Z
0 likes, 0 repeats
@ineiti yes n and r only make sense as integers and n>=r too.
(DIR) Post #An4l6FBzzuKBs8dpey by futurebird@sauropods.win
2024-10-16T21:02:15Z
0 likes, 0 repeats
@richpuchalsky combination as in combinatorics
(DIR) Post #An4lChimqCE05f3fIe by futurebird@sauropods.win
2024-10-16T21:03:20Z
0 likes, 0 repeats
@wallhackio I assumed those would be excluded. but didn’t think to say so.
(DIR) Post #An4lO3wcYXayCQwebQ by dogfox@kpop.social
2024-10-16T21:05:25Z
0 likes, 1 repeats
I see, thanks.This looks like a good place to start: https://math.stackexchange.com/questions/103377/how-to-reverse-the-n-choose-k-formulaLet us know if that leaves questions unanswered.@futurebird
(DIR) Post #An4m0f96gsSga8BunQ by dogfox@kpop.social
2024-10-16T21:12:27Z
0 likes, 0 repeats
I suppose it's cheating to just construct x = xC1?@futurebird
(DIR) Post #An4mXRJf88HfFIl2MS by grob@mstdn.social
2024-10-16T21:18:22Z
0 likes, 0 repeats
@futurebird I am not entirely sure I get this. Wouldn't you be asking for the set {(n, r) ∈ℕ²: nCr = x} ? Otherwise you could always say xC1 = x?
(DIR) Post #An4mYfTXyHLfRxy0Js by futurebird@sauropods.win
2024-10-16T21:18:31Z
0 likes, 1 repeats
@dogfox Yeah. I’m realizing what I really want are ALL the possible ways to write the big integer as nCr — and the closer r is to floor(n/2) the more awesome it is.
(DIR) Post #An4mecCd3K4L2LtCgC by futurebird@sauropods.win
2024-10-16T21:19:41Z
0 likes, 0 repeats
@grob If r=n or 1 that is boring. what about all the other possible answers?
(DIR) Post #An4mofCqjxQBFRmg1A by futurebird@sauropods.win
2024-10-16T21:21:26Z
0 likes, 0 repeats
@eruonna oh no I meant to give an easy and hard example!
(DIR) Post #An4nCdlHlLvDiZKA08 by grob@mstdn.social
2024-10-16T21:25:49Z
0 likes, 0 repeats
@futurebird yes! Very interesting! I have no idea! Dang, I wish I could "follow" threads and see if someone has a solution (because I *will* forget to come back and check)
(DIR) Post #An4o2fU8bH2Q7a719c by pbloem@sigmoid.social
2024-10-16T21:35:13Z
0 likes, 0 repeats
@futurebird This is half an answer, but if r is known, then you can take r! to the other side, and get ir! (with i your integer) which should be the product of successive integers starting at r+1, I think. If r doesn't work, just trying the multiplication should overshoot soon enough.Since r=1 is unsatisfying anyway, you might try this for a few rs near n/2, or look at the factors to find good candidates.
(DIR) Post #An4piYfASFzT4zoH56 by fidgetyhands@wandering.shop
2024-10-16T21:53:58Z
0 likes, 1 repeats
@futurebird You could make a spreadsheet that autofilled nCr values (n increasing along columns and r along rows). Then you could eyeball it or ctrl-F or make a second page in the spreadsheet that compared each cell to your constant.
(DIR) Post #An4rr5zqbZvigdgJcW by richpuchalsky@mastodon.social
2024-10-16T22:17:50Z
0 likes, 0 repeats
@futurebird Oh, the thing linked below. When I took math this had some completely different way of writing it (I forget which one out of the 4 or so common variations):https://www.cuemath.com/ncr-formula/
(DIR) Post #An4s4Jr0OY5RQfqpgO by futurebird@sauropods.win
2024-10-16T22:20:18Z
0 likes, 0 repeats
@fidgetyhands Like an animal.
(DIR) Post #An4s97G6ePdZoWsZXc by futurebird@sauropods.win
2024-10-16T22:21:12Z
0 likes, 0 repeats
@grob Sometime I reply to thread I want to come back to with a hash tag like #futurebirdstuff so I can find it.
(DIR) Post #An4v0xQzarnktElxIm by 4raylee@mathstodon.xyz
2024-10-16T22:53:13Z
0 likes, 0 repeats
@futurebird calculate all the factorials ahead of time. ( up to some n! , there’s probably a heuristic for when to stop.) Multiply the number under question by all the factorials. See if the result after multiplication is itself a factorial. (Given: nCr := n(n-1)(n-2)…(n-k+1) / [ k(k-1)…1 ]
(DIR) Post #An4wCptNYprcvZHIPY by catselbow@fosstodon.org
2024-10-16T23:06:41Z
0 likes, 0 repeats
@futurebird @richpuchalsky Unless I'm mistaken (plausible!) this sounds like another term for binomial coefficients, "n choose r". Is that right? If so, maybe the alternative terminology will help folks think about the problem.
(DIR) Post #An51jss20ZSBUXE2gi by gjm@mathstodon.xyz
2024-10-17T00:08:41Z
0 likes, 1 repeats
@futurebird You don't want to do this by factorizing (which can be expensive).If N = (n choose r) then also N = (n choose n-r), so it's OK only to look at solutions with r <= n-r or equivalently n >= 2r.If N = (n choose r) with n >= 2r then for sure N >= (2r choose r). This is a fairly rapidly increasing function of r, so we can quickly get an upper bound on how big r is, and it won't be very big unless N is enormous.Now we can just try each value of r. We have r! N = r! (n choose r) = n(n-1)(n-2)...(n-r+1), the product of n consecutive integers with the largest being n. This is always somewhere between (n-r+1)^r and n^r, so t := (r! N)^(1/r) is somewhere between n-r+1 and n, so n is somewhere between t and t+r-1. Now we can try them all or do a binary search or something. (We can surely do better but this is easy and efficient enough.) Unless we are unlucky, we will be able to reject most r quickly by observing that ceiling(t) is always one of those consecutive integers, so we can rule out any r for which N isn't a multiple of ceiling((r! N)^(1/r)).So let's look at 7413705167549733. (56 choose 28) is bigger than this, so we can restrict ourselves to r <= 27. If I haven't screwed up my calculations, it turns out that 7413705167549733 isn't a multiple of ceiling(t) for any choice of r other than r=1. So that number isn't nontrivially a binomial coefficient.
(DIR) Post #An5aCJ5jVedhMeMJpA by grob@mstdn.social
2024-10-17T06:34:48Z
0 likes, 0 repeats
@futurebird that's clever! I found this reminder bot as well, I will give it a try here!