sorting problem

[Euler]

Let's say I want to collect all the possible number pairs between 0 and 5. So, (0,0), (0,1), (0,2), (0,3).....(5,3), (5,4), (5,5)

So obviously you have 6 choice for the first number (0,1,2,3,4,5,6) and six for the second and with simple math you get a total of 36 possible pairs. With me so far?

Let's do it again for the numbers between 2 and 4. Again, we have (2,2), (2,3), ....(4,3),(4,4)
(2,3,4) three choices for first and again three for second, so 9 possible total.

We easily see the number of number of combos will be [(M-N)+1]^2, where M is the larger number and N the smaller. If we were randomly generating numbers in the given window and discarding duplicates, we could be satisfied that once we found [(M-N)+1]^2 pairs, we could stop looking.

Now, what if there is a second condition. Say the two numbers had to have a sum less than a given number. So, back to example 1. I want a list of two numbers, each between 0 and 5 and that have a sum of 5 or less.

Well, a simple Gaussian summation will show that the there are 21 such pairs. (0 and 0,1,2,3,4,5) (1 and 0,1,2,3,4) (2 and 0,1,2,3,) etc. 6+5+4+3+2+1 or N(N+1)/2

So in this case, since 21<36, we can turn off our number generator at 21 found combos.

Now, lets move to multiplication. The number of solutions for the first criteria remains the same. (M-N+1)^2.
I am buggered on the second criteria. How can I figure out how many products would be less than a given number 'P' given the the numbers multiplied will be between N and M?

Right now all I can think to do is generate the list that satisfies criteria 1, and then do a second pass eliminating all that do not pass criteria 2. I think this in an ugly solution though.

Somebody give me a better one?

[Euler]

bump. Where my nerds at?

sorting method that only requires on pass and will work for any window and any operation. GO!

[darkcipher]

You'd think someone with a name like Euler could figure out discrete math... that's too funny.

[Whirlin]

Now, lets move to multiplication. The number of solutions for the first criteria remains the same. (M-N+1)^2.
I am buggered on the second criteria. How can I figure out how many products would be less than a given number 'P' given the the numbers multiplied will be between N and M?

Right now all I can think to do is generate the list that satisfies criteria 1, and then do a second pass eliminating all that do not pass criteria 2. I think this in an ugly solution though.

Somebody give me a better one?
Kind of confused by the ask... But, here's my take on it...

You only need to stop once the first value in criteria 2 fails the multiplication validation, rather than testing all potential solutions.

If array 1 is at 2, and array 2 is at 3, you don't need to evaluate array 2 at values 4, 5, or 6. This would reduce calculation cycles upon failure to only result in 1 failed calculation per value in Array 1. What would that equation be in number of attempts? Don't really feel like figuring it out! I'm not in math class anymore!

[Euler]

yes, but the numbers are generated randomly, not sequentially. So, you could have in if M*N==false, skip M*(N+P) where P is any positive value....but, that would need to be remembered and for sufficiently large sets it is yucky.

I want a RULE for determining the size of the set, not an algorithm for determining the what the set contains. It is easy to do for addition, why is it so much harder for the other operations...or is it?

So to make my ask clearer, "Can you generalize a rule that will determine the number of elements that will satisfy the two conditions outline above?"

My ask is NOT, "How can I make a system that selects elements that fit the the two conditions above?" <-- I agree, this one is trivial.

First correct solution gets Whirlin's bow.

[darkcipher]

it's pronounced oil-er

Discrete math, FTW... see, college wasn't a waste of time after all.

[Euler]

You must spread some Reputation around before giving it to darkcipher again.

I will marry you in place of a green square.

[darkcipher]

Hmmm, tempting offer. Let me think about it for a little bit.

[m444w]

So you...

given a set of integers, is there a non-empty subset whose sum is X?

[Luscinia]

If I understand the question you are asking:

Given integers N, M, and P, where N<M and N^2 <= P, determine the number of pairs (x,y) such that:
(1) N<=x,y<=M
(2) x*y<=P

(I know you asked for "less than P" but the formulas are easier to write with less-than-or-eq)

For x=N, the range of possible y-values is {N, N+1, ..., [P/N]}, so in total ([P/N]-N+1)
For x=N+1, the range of possible y-values is {N, N+1, ..., [P/(N+1)]}, so in total ([P/(N+1)]-N+1)
...
For x=M, the range of possible y-values is {N, N+1, ..., [P/M]}, so in total ([P/M]-N+1)

However, if N*M>P then we can only take x-values up to [P/N], so there are two cases:

Case 1: N*M<=P, so x-values range from N to M

Total number of pairs = ([P/N]-N+1) + ([P/(N+1)]-N+1) + ... + ([P/M]-N+1)
= ([P/N] + [P/(N+1)] + ... + [P/M]) - (N-1)(M-N+1)

I don't think there is a closed form for the first part of this since there isn't one for harmonic series partial sums.

Case 2: N*M>P, so x-values range from N to [P/N]

([P/N]-N+1) + ([P/(N+1)]-N+1) + ... + ([P/([P/N])]-N+1)
= ([P/N] + [P/(N+1)] + ... + [P/([P/N])]) - (N-1)([P/N]-N+1)

[darkcipher]

Wow, look at the big brain on Luscinia... I may be in love.

[Viekn]

If I understand the question you are asking:

Given integers N, M, and P, where N<M and N^2 <= P, determine the number of pairs (x,y) such that:
(1) N<=x,y<=M
(2) x*y<P

(I know you asked for "less than P" but the formulas are easier to write with less-than-or-eq)

For x=N, the range of possible y-values is {N, N+1, ..., [P/N]}, so in total ([P/N]-N+1)
For x=N+1, the range of possible y-values is {N, N+1, ..., [P/(N+1)]}, so in total ([P/(N+1)]-N+1)
...
For x=M, the range of possible y-values is {N, N+1, ..., [P/M]}, so in total ([P/M]-N+1)

However, if N*M>P then we can only take x-values up to [P/N], so there are two cases:

Case 1: N*M<=P, so x-values range from N to M

Total number of pairs = ([P/N]-N+1) + ([P/(N+1)]-N+1) + ... + ([P/M]-N+1)
= ([P/N] + [P/(N+1)] + ... + [P/M]) - (N-1)(M-N+1)

I don't think there is a closed form for the first part of this since there isn't one for harmonic series partial sums.

Case 2: N*M>P, so x-values range from N to [P/N]

([P/N]-N+1) + ([P/(N+1)]-N+1) + ... + ([P/([P/N])]-N+1)
= ([P/N] + [P/(N+1)] + ... + [P/([P/N])]) - (N-1)([P/N]-N+1)

This is the kind of shit I see on a test, and go..."Fuck it, I'm going to get a beer, whose coming?"

[Euler]

I accept blame for this, my question is obviously bad. I will try and be more careful.

Chapter 1: M,N integers within a window.

Math People:
let F and C be integers where F < C. They will serve as min and max values for the two integers on which we wish to operate. I picked F for floor and C for ceiling, if that helps. So

F <= M <= C
F <= N <= C

if COMPUTER MACHINES are your bag,
M=F+rand(1 + C - F)
N=F+rand(1+ C - F)

If you like stories:

You have a box of index cards. Your brother picked a card and wrote his favorite number on it. Then he got a new one and wrote the number after his favorite. Then the number after the number of his favorite, etc. Then he got bored and put the cards he wrote on in a pile. You are going to randomly pick a card, write the number down, put the card back, then repeat.

If you majored in humanities:
Go drink your juice box and watch a cartoon. We'll come get you when we are done.


Now then, we are given two integers L (little) and B (big). We want to create a set so that we cover all the possible pairings of (M,N) such that:

L <= (M$N) <=B

If we were just to create the set, it would be easy, we could systematically choose numbers, starting with (F,F)
If L <= (F$F) <= B we add (F,F) if not we move to (F,F+1) etc.

BUT BUT BUT BUT!!!!

We are NOT selecting numbers. We are given them randomly. So. How do we know when we are done? The upper bound will be [(C-F)+1]^2 pairs because that is the maximum number of unique (M,N) you can create.

BUT what if there are only, say, (C-F)+1 pairs that satisfy L<=(M,N) <=B ???

We would sit in front of our number generator and never reach our upper bound of pairs because that many don't exist. But we could never be sure if they don't exist or if we are getting unlucky number generation.

If I know L,B, F, and C can I come up with a bound that is less than [(C-F)+1]^2 so that I may safely turn off the machine?

1. Is it possible?
2. Can we do it for $=(+,-,/,*)?
3. Can we generalize further?

The more I think about it, the less I think it is possible

[Euler]

Wow, look at the big brain on Luscinia... I may be in love.

but....


Hmmm, tempting offer. Let me think about it for a little bit.

[Whirlin]

I tried working on this for a while with various different datasets to test various hypothesis, and was unable to reach a specific conclusion on an equation.

I worked under a flawed assumption of:

1) There is a discrete number of potential value outcomes, which is M*N, where M is the number of values in the first array, and N is the number of values in the second array.
2) There is a probability that the multiplicative outcome of M*N is less than (or equal to) the anticipated outcome

I attempted many different permutations of 2, taking into account max/min variables of M/N, normalizing for potential outcomes, boundaries, etc... And while I found some data models that worked relatively closely for M=(1-6) and N=(1-6), Once I varied up the array values substantially, the permutations did not hold true.

Honestly, I'm stumped on this one... but to be quite honest, the last math course I took was AP Statistics and AP Calculus in High school, so it's been a long time... Since then I've mainly worked in logical mathematics for equations for Excel, so I'm hardly the expert of this type of stuff.

[darkcipher]

but....

I have enough love to go around, don't worry, Euler

[Latrinsorm]

It is easy to do for addition, why is it so much harder for the other operations...or is it?I think it truly is. With addition, 1 + N = 2 + N - 1 = etc., but it is definitely not the case in general that 1 * N = 2 * (N - 1). Another thing multiplication does that addition does not is prime numbers, or more broadly a number X + 1 does not necessarily have more factors than X, while it will always have more addends, so it's possible to construct sets that can have the same number of pairs that multiply to 6 as 7, but not add to them (ignoring the trivial case of component numbers not large enough to reach), and flat lines are really hard to make in functions.

[Euler]

yeah. If there is a solution to this, it is eluding me at the moment. I think I am going to make a fuzzy solution that won't share with my mathematical friends because they would throw mid-sized stones at me. I think I'll set a "percentage of comfort" value and then calculate how many number pairs your machine would need to draw to reach that percentage based on the window given.

Oh well. Feels dirty, almost like that mathematical quackery known as engineering.