53 posts / 0 new

## Pages

nelphine
Joined May 2005
866 Posts
This has nothing to do with D&D, but I'm posting this in CharOp because I know a number of people here are actually quite strong with math.  No, this is not a homework assignment.

I'm trying to bound a series of recursive equations:

EDIT: I made a mistake in the initial post and have updated the equations to reflect that.

f(x) = x - x*2/5

f(x) = x - x*2/5 - x*2/7 + x*4/35

f(x) = x - x*2/5 - x*2/7 - x*2/11 + x*4/35 + x*4/55 + x*4/77 - x*8/385

etc

The first wrinkle comes from the fact that x will always be an integer, and my answer must always be a positive integer.  Further the value of every given term (such as -x*2/5) must also be an integer.

For example, if x was 103, then the first equation (-x*2/5) would seem to be -41.

However, the problem comes from the fact that the answers will not be completely evenly spread.

Specifically, if x was 103, then the first equation -(x*2/5) could be -40, -41, or -42.  We simply don't know.

My concern comes from the third equation (and later equations, as we continue to get more and more  terms in the equation as we continue adding prime numbers).  Continuing the example, if x was 103, then:

-x*2/5 could be -40, -41, or -42.  -x*2/7 could be -28, -29 or -30.  -x*2/11 could be -18, -19 or -20.  x*4/35 could be 8, 9, 10, 11 or 12.  x*4/55 could be 4, 5, 6, 7 or 8.  x*4/77 could be 4, 5, 6, 7 or 8.  -x*8/385 could be 0, -1, -2, -3, -4, -5, -6, -7, or -8.

If I simply assume the largest possible answer for each one, then I end up in a situation where my answer is a negative integer (which I know it cannot be).  So how do I put a bound on this equation such that I can ensure I'll always get a positive solution?

The next equation would be:

x - x*2/5 - x*2/7 - x*2/11 - x*2/13 + x*4/35 + x*4/55 + x*4/65 + x*4/77 +x*4/91 + x*4/143 - x*8/385 - x*8/455 - x*8/715 - x*8/1001 + x*16/5005

(the first set of terms is -x*2/prime, the second set is +x*4/product of 2 primes, the third set is -x*8/product of 3 primes, etc, noticing that 2, or 4, etc is 2^(the number of primes in the product forming the denominator), and the set is negative or positive based on (-1)^(the number of primes in the product forming the denominator)

The complicated part is exactly the spread.  Specifically, let us look at the second equation, and next at the term -x*2/5.  For every 5 elements in x, 2 of them are 'bad' elements (thus why we have a minus, and why it is 2/5).  Looking at the next term, -x*2/7:  For every 7 elements in x, 2 of them are 'bad' elements (again, this results in a minus, and 2/7).  The final term, +x*4/35, is to account for the overlap.  We've taken out a set of elements based on the first term, and we've taken out a set of elements based on the second term; however, some of these elements are actually the same elements; specifically, 4 out of every 35 elements will be a bad element that falls in both the first (x*2/5) and second (x*2/7) terms, so we have to add that amount back in to balance the equation.   As a note, the overlap does exactly show up in these patterns, they are not estimates.

As we add more primes into the equation (and I need this to work for 50,000 primes, which is why I need a bound, and why, as I'll explain in a second, the spread is effectively unpredictable), we have more pairs that cause overlap; but then the overlap of pairs start to overlap themselves, creating the third set of terms (that are the triples), and then those start to overlap (causing the fourth set of terms), etc, etc.  With even 10 primes included, this equation becomes completely hopeless to solve using brute force.  There are various other equations that are equivalent to this one (and are much easier to manipulate), but first I need to deal with the weird spread you have noticed, so that I can make sure any manipulations I do to the equivalent equations actually account for all the variances that occur in this, the original equation.

To explain why there is the range:  If x = 103, then it is possible that, out of every 5 elements, the first and second elements are bad.  Thus, the 101st and the 102nd elements would be bad.  In this case, -x*2/5 = -42.  However, it is also possible (I haven't actually worked it out), that if x = 103, then out of every 5 elements, the fourth and fifth elements are bad.  In this case the 104th and 105th elements would be bad; but those elements are not actually in x.  So in this case, -x*2/5 = -40.  (And finally, if out of every 5 elements, the 2nd and 4th elements were bad, then -x*2/5 = -41.)

So, given that I need this equation to have a bound based on a large number of primes (hopefully ANY number of primes), and given that x is a free variable, and that the spread is different for every prime number (and therefore every product of prime numbers for the later sets of terms), and that the spread changes for every value of x, I am left with trying to bound it in rather silly fashions.

However, given that all I need is a bound that makes the equation result in a positive integer each time (even if it is only 1), the bound should be possible.  I just don't know how to find it.
nrujac
Joined Dec 2011
2 Posts
Let me see if I understand the question. Are you trying to find the largest number of terms you can add on to the series such that the result is always positive regardless of the value for x? Also, why does the value for x cluster?

Assuming the value for x can be any positive integer, we can attempt to find a bound on the number of terms (in terms of x), but I'm not entirely certain what you're asking here. I assume this is related to charop, so this is a probability question on some level -- can you share more details on what you're working on so we can restate the problem in a more concise notation? A lot of times, these problems that seem intractable wind up being a lot simpler if you can put them in the correct notation.
DeAnno
Joined Jul 2008
174 Posts
What confuses me is this buisiness of 103*2/5 = 40, 41, or 42.  103*2/5 = 41.2  That could be interpreted as 41 or 42, but how could it be interpreted as 40?

Are you trying to say that the term has value v: floor(103/5)*2 < v < ceiling(103*2/5) ?
The Direct Damage Sorcerer of 3.5e: The Mailman
Joined Jun 2008
1318 Posts
So the formula is kinda like...

f(x,y,n) = {z-n/2, ..., z-1, z = rnd(x*n/y), z+1, ..., z+n/2}

x,y,n is assumed to be positive, and y assumed to be a non-zero, and n assumed to be a multiple of 2.

Then you throw in...

Actually that wouldn't work at all.

The example answers you give have no pattern that I can derive in their set.  The first couple average a range from {z-n/2, z, z+n/2} where z is the rounded answer.  Later on, the other sets range randomly from sets of {z-n, z} or {z-n+1, z, z+n-1}

Further, nothing you have shown actually points out where the recursive bits comes in at.  In fact, there looks to be a ... is that a recursive function inside a recursive function?  I can see where the 2, -4, and 8 part can be done (2*n*(-1)^(n-1)), but not the strange 5, 7, 35, 55 set of strangeness.
nrujac
Joined Dec 2011
2 Posts
The denominators are being generated by prime numbers. 5, 7, 11 => 5, 7, 11, 35 (5*7), 77 (7*11), 385 (35*11). So the next number in the series is 2695 (35*77). The numerators are the respective powers of two. My question is how he gets his clustered values for x, it makes no sense. I see someone else's interpretation as rounding, but that only ever gets you the choice of two numbers depending on how you round. I think he's trying to multiply that error factor through, and getting a gigantic number of possibilities, but I'm pretty sure he doesn't need to do that if he's only trying to stamp down on the rounding error. All he needs to do is compute the result precisely and then round at the end. This is the standard approach to value calculation taught in most high schools.
Joined Jun 2008
1318 Posts
Oh!  I think I'm starting to see the pattern here as well, NruJaC.  Now its just how the clustered values are formed.  I know the range are equal to the numerator of the equation (2,4,8) + 1 for the original rounded answer, but I'm still trying to figure out how the high and lows are formed for the range.
IxidorRS
Joined Sep 2011
2781 Posts
Using CharOp for math problems should make for a pretty epic thread.
nelphine
Joined May 2005
866 Posts
Ok, to provide more information, it is based on primes.  I realize when I posted this I screwed up and missed posting a very important piece; each equation should start with 'x - ...'.  Based on THIS I want to end up with positive answers.

So the equations should actually be:

x - x*2/5

x - x*2/5 - x*2/7 + x*4/35

x - x*2/5 - x*2/7 - x*2/11 + x*4/35 + x*4/55 + x*4/77 - x*8/385

The next equation would be:

x - x*2/5 - x*2/7 - x*2/11 - x*2/13 + x*4/35 + x*4/55 + x*4/65 + x*4/77 +x*4/91 + x*4/143 - x*8/385 - x*8/455 - x*8/715 - x*8/1001 + x*16/5005

(the first set of terms is -x*2/prime, the second set is +x*4/product of 2 primes, the third set is -x*8/product of 3 primes, etc, noticing that 2, or 4, etc is 2^(the number of primes in the product forming the denominator), and the set is negative or positive based on (-1)^(the number of primes in the product forming the denominator)

The complicated part is exactly the spread.  Specifically, let us look at the second equation, and next at the term -x*2/5.  For every 5 elements in x, 2 of them are 'bad' elements (thus why we have a minus, and why it is 2/5).  Looking at the next term, -x*2/7:  For every 7 elements in x, 2 of them are 'bad' elements (again, this results in a minus, and 2/7).  The final term, +x*4/35, is to account for the overlap.  We've taken out a set of elements based on the first term, and we've taken out a set of elements based on the second term; however, some of these elements are actually the same elements; specifically, 4 out of every 35 elements will be a bad element that falls in both the first (x*2/5) and second (x*2/7) terms, so we have to add that amount back in to balance the equation.   As a note, the overlap does exactly show up in these patterns, they are not estimates.

As we add more primes into the equation (and I need this to work for 50,000 primes, which is why I need a bound, and why, as I'll explain in a second, the spread is effectively unpredictable), we have more pairs that cause overlap; but then the overlap of pairs start to overlap themselves, creating the third set of terms (that are the triples), and then those start to overlap (causing the fourth set of terms), etc, etc.  With even 10 primes included, this equation becomes completely hopeless to solve using brute force.  There are various other equations that are equivalent to this one (and are much easier to manipulate), but first I need to deal with the weird spread you have noticed, so that I can make sure any manipulations I do to the equivalent equations actually account for all the variances that occur in this, the original equation.

To explain why there is the range:  If x = 103, then it is possible that, out of every 5 elements, the first and second elements are bad.  Thus, the 101st and the 102nd elements would be bad.  In this case, -x*2/5 = -42.  However, it is also possible (I haven't actually worked it out), that if x = 103, then out of every 5 elements, the fourth and fifth elements are bad.  In this case the 104th and 105th elements would be bad; but those elements are not actually in x.  So in this case, -x*2/5 = -40.  (And finally, if out of every 5 elements, the 2nd and 4th elements were bad, then -x*2/5 = -41.)

So, given that I need this equation to have a bound based on a large number of primes (hopefully ANY number of primes), and given that x is a free variable, and that the spread is different for every prime number (and therefore every product of prime numbers for the later sets of terms), and that the spread changes for every value of x, I am left with trying to bound it in rather silly fashions.

However, given that all I need is a bound that makes the equation result in a positive integer each time (even if it is only 1), the bound should be possible.  I just don't know how to find it.
nelphine
Joined May 2005
866 Posts
As an idea of what I have been trying, I had originally not realized that I would need to account for the wierd spread in any of the sets of terms past the first (the terms which are triples, or quadruples, or higher, of primes).  Thus to create a bound for the first set of terms (-x*2/prime), I simply assumed the worst case scenario, which was that the final set would always have 2 'bad' elements in it.  (So if x = 103, I would simply assume that -x*2/5 = -42.  Similarly -x*2/7 = -30)

Because I was only accounting for the the first set of terms, assuming the worst case actually did work, and results in the positive integer solution I was looking for.   The second and later sets of terms are only there to account for overlap (and overlap of overlap, etc), and so only account for a very small percentage of the final answer; so I know that overall the equation DOES result in a positive solution.  I just don't know what to do to rigorously account for the variance of those overlap sets.
Ogg-Mosh
Joined Jun 2010
78 Posts
just a quick, unproductive note: None of what you have posted are actually equations, as there is no equality listed (no f(x) = ...). You've just listed a few terms, and it's not clear from those terms what you want to actually solve for.
nelphine
Joined May 2005
866 Posts
lol whoops.  Yes, each one should have "f(x) =" at the front.  So specifically, the first one would be f(x) = x - x*2/5

If anyone cares, a slightly more accurate statement would be something like

f(x) = x - (5*(floor(x/5)))*2/5 - y, where y would be 0, 1 or 2 (and for later terms, y would start ranging over larger values).  But I felt that is actually a more confusing way to show it.
DragonBarbarian
Joined Dec 2011
139 Posts
x - x*2/5-

x - x*2/5 - x*2/7 + x*4/35

x - x*2/5 - x*2/7 - x*2/11 + x*4/35 + x*4/55 + x*4/77 - x*8/385

I will solve all of it for 103.

103 - (103*2/5=41.2) = 61.8

61.8 - (103*2/7=29.428)= 32.372, (103*4/35) + 11.771... = 44.143,

61.8, - (x*2/11=18.7272), 25.4158, 32.906, 38.256... = 36.116

So there you go, the answers. The question is, what are you really doing this for, and what are you trying to figure out?

To be honest, by putting it over a common denominator, which in this case would be actually be 385, you can find a more exact and precise answer without all the complicated and intermediate math.

So it would look more like

154/385, 110/385, 70/385, 44/385, 28/385, 20/385, 8/385

which we see an drop of 44, to 40, to 26, to 16, to 8... which is exopentially decreasing, but decreasing less each time, so it looks like a square root or something.

So it would be more like... -, -, -, +, +, +, -, assuming that there is an X in front of each of these numbers...

x - x*2/5 - x*2/7 - x*2/11 + x*4/35 + x*4/55 + x*4/77 - x*8/385

X - 154/385, -110/385, -70/385, +44/385, +28/385, +20/385, -8/385

Or 477 - 342  = 143/385, x 103 = 36.116883

So there you go, an easy to solve an otherwise complex answer, and while there is a seemingly existent pattern, it appears to be arbitrary and this yet to seems to serve a purpose...
nelphine
Joined May 2005
866 Posts
Unfortunately DragonBarbarian, the final answer must be an integer; and the spread will not be exact for the last few elements.  (Meaning I can't simply use the floor or ceiling functions.)  See post #7 for a complete explanation. (I probably should amend that into the first post to avoid confusing people.)
AtG
Joined Feb 2010
1305 Posts
edit: I forgot about the very first term in the expressions here, the 'x'.  Adding that back in means the sequence should converge to 0.

Okay, the first observation is that x falls out of this completely.  It's irrelevant.

The second is that you appear to be trying to calculate the limit of a sequence.

We'll denote the elements of the sequence by f(n).  Let P(k) be the kth prime.  Inspection tells us:

f(n) = f(n-1) * (1 - 2/P(n+2)) + 2/P(n+2)

Explanation:

f(n) is the sum of 2/5 through 2/P(n+2) (since you start your primes at 5, the 3rd prime), minus 4/(every pairwise product of primes from 5 through P(n+2), plus 8/(every three-way product of same), etc.

f(n-1) is the sum of 2/5 through 2/P(n+1), minus 4/(every pairwise product of primes from 5 through P(n+1), etc.

So to get from f(n-1) to f(n), we just take f(n-1) and add 2/P(n+2), and subtract 4/(P(n+2) pairwise product with each of 5 through P(n+1)), etc.

I'm pretty sure this sequence converges to 1, just looking at it.
Joined Dec 2008
329 Posts
I have to say that stumbled into this thread hoping to see n-dimentional knots on m-dimentional membranes--only to be surprised with the reality of the bounding of bad functions. w00t! Go MATH!
nelphine
Joined May 2005
866 Posts

@AtG:  If you ignore the discrepencies due to the spread not being correct, and simply consider the equation as if you could have non integer solutions, it actually (I think) diverges as x gets larger, although I haven't completely proven that yet (as it doesn't help me due to my constraints).   The problem being that I can't actually use the obvious non-integer solutions and then simply take the closest integer, which is what I had initially done before realizing I needed to account for the spread discrepancies.
Zathris
Joined Nov 2009
6277 Posts
Well, you can figure out the probability of any given integer solution for eat set, but that really is only useful for determining your lowest, highest, mean, and median
"Invokers are probably better round after round but Wizard dailies are devastating. Actually, devastating is too light a word. Wizard daily powers are soul crushing, encounter ending, havoc causing pieces of awesome." -AirPower25 Sear the Flesh, Purify the Soul; Harden the Heart, and Improve the Mind; Born of Blood, but Forged by Fire; The MECH warrior reaches perfection.
nelphine
Joined May 2005
866 Posts
any particular suggestions on how to figure out how to determine the worst case scenario (meaning: the most 'bad' elements) which I think means your lowest, but might mean your highest, and yet still have a positive integer value for the overall equation?  That's what I'm looking for.  I just need to show that either the later sets of terms are insignificant to the overall total, or that the overall total will always be positive.
DragonBarbarian
Joined Dec 2011
139 Posts
Well what pattern does it follow?

It apparently fit into that 385, and what exactly are you looking for?

It apears to be a summation of a repeating number.

For instance, a guy walks into bar and orders a bear; an infinite more people come in and say "I want half of what he's having" for the guy in front.

The bartender says "You're all idiots" and takes out two beers; I.E. the summation leads to 2.

So the question is, you're trying to find a summation right; what's the equation you're using to find these numbers?

And what exactly are you trying to figure out?

The ceiling to the floor? O_o
AtG
Joined Feb 2010
1305 Posts

@AtG:  If you ignore the discrepencies due to the spread not being correct, and simply consider the equation as if you could have non integer solutions, it actually (I think) diverges as x gets larger, although I haven't completely proven that yet (as it doesn't help me due to my constraints).   The problem being that I can't actually use the obvious non-integer solutions and then simply take the closest integer, which is what I had initially done before realizing I needed to account for the spread discrepancies.

Um, no.  I have no idea what you mean by "spread", and there is no equation here to have solutions.  I am implicitly saying x=1 and observing the behavior of the coefficient of x (because the entire series can separate out as a lone coefficient of x).  But the actual algebraic sequence described converges to zero.  (I believe that last result based on the structure of the recurrence but haven't proved it.)
nelphine
Joined May 2005
866 Posts
@AtG:

All right, consider the second of what I called equations:

f(x) = x - x*2/5 - x*2/7 + x*4/35

however, note that this equation is actually equivalent to the equation:

f(x) = (x - x*2/5) - (x - x*2/5)*2/7, which is a fairly simple equation to manipulate and put bounds on (and the set of equations based on this version diverges, as the number of primes gets higher).

But my first equation isn't quite accurate; I have to account for what I call the unpredictable 'spread'.  What it should really be is:

f(x) = x - (5*floor(x/5))*2/5 - m - (7*floor(x/7))*2/7 - n + (35*floor(x/35))*4/35 + o
where m = 0, 1, or 2, n = 0, 1, or 2, o = 0, 1, 2, 3, or 4
and m, n, o are determined by the exact value of the given x

the 'spread' I'm referring to is the unpredictability of m, n and o, and I need to bound it in my original equation, not simply my equivalent equation

@DragonBarbarian: Perhaps my conversation with AtG will help explain it to you.
Additionally: the pattern of what the terms are in any given equation is based on the primes, specifically, the first k primes greater than 3, where k is decided by the input.  My first equation uses k = 1, so only considers the prime '5'.  Second one considers k = 2, so considers the primes '5' and '7'.  Third one considers k = 3, so considers the primes '5', '7', and '11'.  Each equation needs a term -x*2/pi, where pi = the ith prime, i from 3 to k, and it needs a terms for each pair of primes (such as 5*7 = 35) that can be created from the first k primes, and it needs a term for each triple of primes, and a term for each quadruple, etc, etc.
AtG
Joined Feb 2010
1305 Posts
Nelphine, I'm going to rearrange your equation a bit:

f(x) = x - x*2/5 - x*2/7 + x*4/35

is equivalent to

f(x) = x * (1 - 2/5 - 2/7 + 4/35)

And if we are actually talking about a sequence of functions fk(x), such that:

f1(x) = x * (1 - 2/5)
f2(x) = x * (1 - 2/5 - 2/7 + 4/35)

etc. then the only interesting or relevant feature here is the behavior of that coefficient.  I believe that coefficient converges to zero in the limit. I just checked it and f1000(1) = 0.030896815, and is only 7.7914E-06 less than f999(1).  So it may not converge to zero, but very close.

I have no idea at all why you are trying to do each multiplication separately and round there.

nelphine
Joined May 2005
866 Posts
x is always an integer; and x will generally become larger as k becomes larger.  I need the equation to have a positive integer solution for large values of k (such as k = 10,000, at which point, x would have a minimum value of somewhere over 20,000, but which could easily be, say, 2,000,000)

AtG
Joined Feb 2010
1305 Posts

x is always an integer; and x will generally become larger as k becomes larger. I need the equation to have a positive integer solution for large values of k (such as k = 10,000, at which point, x would have a minimum value of somewhere over 20,000, but which could easily be, say, 2,000,000)

This is fundamentally confused.

We have a sequences of function of x, {fk(x)}. We know that:

f1(x) = x * (1 - 2/5)
f2(x) = x * (1 - 2/5 - 2/7 + 4/35)

and in general I have provided a method for computing fk(x) for aribtrary k.

Now here's the important point:

We cannot use this information to solve for x.

We have been given no constraints on x from the previous information. x could be 100. x could be pi. x could be -27.5. And so on.

OK, so you tell me x is an integer. Fine. x is an integer. So x can't be pi or -27.5. But x can still be 1, 2, 3, 4, 5... and so on, it can be any integer and that doesn't conflict with any information given.

So your thing about needing "integer solutions" is literally meaningless. There is nothing to solve for.

The algebra you've provided does not reflect this at all, and I think your question is still ill-posed.

Let's consider the set {1,2,3,4} (for some reason you are ignoring that 2 and 3 are prime; fine). I belive you would say that no elements of it are bad.

Then let's consider the set {1,2,3,4,5}. By your description it sounds like 5, and one other element of the set ought to be bad. Thus there would be two bad elements.

Then let's consider the set {1,2,3,4,5,6,7}. By your description it sounds like 5, 7, and one or two (but you aren't sure which) other elements of the set ought to be bad, so there may be three or four total bad elements.

Can you provide some mechanical description of your notion of badness, and why you think it has these properties?

nelphine
Joined May 2005
866 Posts
As a note, in the first post, I did mention that everything had to be integers.

As a further note, I am aware this is not a particularly clear question; hopefully, that is why I myself haven't found the solution I'm looking for.  Further to that, any nit-picking you do does in fact help me, as it helps me clarify exactly what is going on, so that if I try to present this to someone else they will understand. So I appreciate any criticisms, and will do my best to explain what I actually mean; and if it turns out I have contradicted myself, or mistakenly confused anyone, I am sorry.

So next, you are right that my algebra doesn't reflect what I want accurately.  I was hoping someone else might have already worked on this, and so been able to recognize it by the little bit I presented.  I also was trying to avoid a wall of text in the initial post so that people wouldn't simply get fed up or confused.  Based on the conclusion of this discussion, I'll try to update the initial post in a meaningful way.

Next: I'm ignoring 2 and 3 because the elements of x are constructed such that, based on the prime numbers 2 and 3, no elements in x will be bad.

Considering the set {1, 2, 3, 4}, I would actually say that there MIGHT be some bad ones.  Specifically, 5*(floor(x/5)) + m (m = 0, 1, or 2), elements would be bad.  Since x in this case = 4, 5*(floor(x/5)) = 0.  Therefore, there would be x-0= 4 elements containing m bad ones, where m could be 0, 1 or 2.

Next, the set {1,2,3,4,5}.  Here, x = 5, therefore 5*(floor(x/5)) = 5.  Therefore there would be 2 + m bad ones.  In this case, since there are EXACTLY 5 elements, there would be x-5 = 0 elements containing m bad ones, where m could be 0, 1, or 2; but since there are only 0 elements containing m bad ones, then m must actually equal 0.

In both of these cases, we have decided that k = 1, which would be reasonable, given the low value of x.

Now, considering the set {1,...,7}, x = 7, and assuming k = 2.  Therefore, 5*(floor(x/5)) = 5, and 7*(floor(x/7)) = 7.  Therefore, we have 2 + m bad ones based on the prime number 5, where the m bad ones are contained by x-5= 2 elements.  So m could be 0, 1 or 2.  We ALSO have 2 + n bad ones based on the prime number 7, where the n bad ones are contained by x-7= 0 elements.  So in this case n must equal 0.

Note, regardless of anything, we never know precisely WHICH elements are bad; we only know how many there are, and approxamitely which elements are bad.
Looking at the set {1,...,7}, we know that we have 2+m elements that are bad based on 5.  We also know that the first 2 bad elements must be located within the first 5 elements of x, and that the m bad elements must be located within the last 2 elements of x.  We know that there are 2 bad elements based on the number 7, and we know that these 2 elements can be any of the 7 elements of x.

Continuing with the set {1,...,7}, we have 4+m bad ones.  This means there could be as few as 4 and as many as 6 bad elements.  However, it is also possible that some of the bad elements based on the number 5 are actually the same elements which are bad based on the number 7.  If this is the case, we don't want to count those bad elements twice.  Specifically, we know that 35*(floor(x/35)) + o elements are bad based on both 5 and 7.  o in this case could be 0, 1, 2, 3 or 4.  Since 35*(floor(x/35)) = 0, there are actually o elements that are bad based on both 5 and 7.

Finally we reach the conclusion:  We have 4+m-o bad elements; given the unpredictabe nature of m and o, this means that in practice we have between 2 and 6 bad elements, although we don't know which elements are actually bad.

Lastly, this is a good example: at worst, we have 6 bad elements; the size of x is 7, therefore, there MUST be at least 1 good element.  THIS is what I actually wish to prove; I simply wish to prove that for all x, and for all k, f(x) must always be positive (and due to the nature of what is going on, f(x) will also always be an integer.)
AtG
Joined Feb 2010
1305 Posts
As a note, in the first post, I did mention that everything had to be integers.

Yes, but there is no logical reason for that to apply to the individual components of an algebraic expression.  If it does, you should not be constructing an algebraic expression.

As a further note, I am aware this is not a particularly clear question; hopefully, that is why I myself haven't found the solution I'm looking for.  Further to that, any nit-picking you do does in fact help me, as it helps me clarify exactly what is going on, so that if I try to present this to someone else they will understand. So I appreciate any criticisms, and will do my best to explain what I actually mean; and if it turns out I have contradicted myself, or mistakenly confused anyone, I am sorry.

Yes, I understand this, it's not a problem.  That's how people figure out new bits of math, by trying to express intuition with rigor.

Considering the set {1, 2, 3, 4}, I would actually say that there MIGHT be some bad ones.  Specifically, 5*(floor(x/5)) + m (m = 0, 1, or 2), elements would be bad.  Since x in this case = 4, 5*(floor(x/5)) = 0.  Therefore, there would be x-0= 4 elements containing m bad ones, where m could be 0, 1 or 2.

Why?  I need some mechanical description of what "badness" is or what causes it.  You're telling me how you think you can calculate the number of bad elements, but if it all possible I'd like to know why the elements are bad, and particularly which ones are bad.

Note, regardless of anything, we never know precisely WHICH elements are bad; we only know how many there are, and approxamitely which elements are bad.

Greyville
Joined Jan 2012
72 Posts
Considering the set {1, 2, 3, 4}, I would actually say that there MIGHT be some bad ones.  Specifically, 5*(floor(x/5)) + m (m = 0, 1, or 2), elements would be bad.  Since x in this case = 4, 5*(floor(x/5)) = 0.  Therefore, there would be x-0= 4 elements containing m bad ones, where m could be 0, 1 or 2.

A few problems here. First, I think you mean to say that there are 2*floor(x/5) + m (m in {0,1,2}) bad elements. You make this mistake throughout your post. It is also worth noting that when x=4, there must be at least one bad element. I don't think this really impacts the part you're focusing on though.

Continuing with the set {1,...,7}, we have 4+m bad ones.  This means there could be as few as 4 and as many as 6 bad elements.  However, it is also possible that some of the bad elements based on the number 5 are actually the same elements which are bad based on the number 7.  If this is the case, we don't want to count those bad elements twice.  Specifically, we know that 35*(floor(x/35)) + o elements are bad based on both 5 and 7.  o in this case could be 0, 1, 2, 3 or 4.  Since 35*(floor(x/35)) = 0, there are actually o elements that are bad based on both 5 and 7.

It's also sort of worth noting here that the value of o is limited by x % 35. If x=40, then 4 bad elements overlap in the first 35, but no more than 2 can overlap in the remaining 5, so o <= 2. Once again, this is not necessarily relevant.

Lastly, this is a good example: at worst, we have 6 bad elements; the size of x is 7, therefore, there MUST be at least 1 good element.  THIS is what I actually wish to prove; I simply wish to prove that for all x, and for all k, f(x) must always be positive (and due to the nature of what is going on, f(x) will also always be an integer.)

The statement there is trivially proved false. x=4, k=2 can easily cover all four elements (or even more trivially, x=1, k=1). What I think you mean to prove is:
For all k >= 1, for all x >= P(k), f_k(x) > 0
(Where P(k) is the kth prime number, starting from P(1) = 5)

From basic inspection this seems to hold for low values. It also sounds interesting. Maths isn't my primary area, so I'm definitely rusty, but I'll will be thinking about this tomorrow.

nelphine
Joined May 2005
866 Posts
Tum te tum..

@AtG:  I'll get the rest of my work in order tonight and post up the explanation about why they become bad - it's a fairly lengthy proof, and I've proven everything else, but I have realized that this particular part can't be explained away in the method I was originally using.

@Greyville:  You are correct in all 3 cases.  As an addition I'll try to get my limits on x as well (they are very specific for what I need, but aside from them being largish, they aren't actually that important to solving my problem)

Finally:  Can you explain why o is limited by x*35%?  That's exactly the kind of bound I want, I just am not sure how to go about finding it, or more importantly, explaining it.  (In fact, if it's what I think you mean, that would probably precisely solve my problem.)
nelphine
Joined May 2005
866 Posts
@AtG: All right, mechanics of x, and why I'm using this 'equation'.

x is the set of multiples of 6 between a number and it's square.  k is the number of primes lower than the number (not including 2 and 3).  Bad elements of x are those that are equivalent to 1 or equivalent to -1 mod any prime lower than the number.  As a note, x can be a much larger set and still produce the same results, as long as it is a set of consecutive multiples of 6 such that none of them are lower than the number.

If x were infinite, and k were 3, then the number of good elements would actually be f(x) = x - (x*2/5 + x*2/7 + x*2/11 - x*4/35 - x*4/55 - x*4/77 + x*8/385)

This equation in turn is equivalent to g(x) = ((x - x*2/5) - (x - x*2/5)*2/7) - ((x - x*2/5) - (x - x*2/5)*2/7)*2/11

g(x) can then be easily manipulated to get the proof I'm looking for.

However, I then noticed my 'spread' problem (which is a result of x being finite) and bounded g(x) in order to solve it; this was fairly simple, and produced nice results.  But then I realized that g(x) wasn't actually a direct translation of the original problem (which is trying to find out how many elements of x are not equivalent to 1 or -1 mod any prime lower than the given number).  So I need to figure out if I can bound f(x) such that I can still use g(x) in a meaningful way.  Although I suppose, I could simply try to solve the problem from a different direction too, if anyone really wants to do that (or knows of a way to do that.)
AtG
Joined Feb 2010
1305 Posts
OK, if x is a set then let's be consistent and denote it as X, and let us say that |X| is the cardinality of X.  k is two less than the number of primes less than |X|.

x in X is 'bad' if x = 1 mod k or x = -1 mod k.  OK.

We are curious about how many elements of X are bad.  Denote this as f(X).

...

Yeah, you aren't going to get an exact algebraic formula for f(X); you can just get an asymptote and/or upper and lower bounds.
nelphine
Joined May 2005
866 Posts
but that's all I need; lower bounds.  I just need to find some way to prove that it is a positive integer.

I think that if I could just assume that every term will be maximized as if it had reached (if the term is increasing the number of bad elements) the next full set, and (if the term is decreasing the number of bad elements) the previous full set, then I would be fine.  But I'm not entirely sure how to go about showing that.

With my typical example of |X| = 103, I would want to assume that -x*2/5 = 42, -x*2/7 = 30, and x*4/35 = 4.

Any suggestions on how to say that in mathematical terms?  For the first set of terms (-x*2/p), I can just subtract 2*k at the end of the whole equation; but I'm not sure how to (intelligibly) describe that for the other terms, since there are vastly more overlap terms than there are in the first set of terms.
AtG
Joined Feb 2010
1305 Posts
Um, to show that f(X) is a positive integer you just need to demonstrate the existence of one 'bad' number, which is guaranteed to be true if |X| > 3.
nelphine
Joined May 2005
866 Posts
erm I think I miscommunicated something.  f(x) = # of good elements.  I need to show that f(x) is a positive integer.  (Basically, I need to show that not all the multiples of 6 are equivalent to 1 or -1 mod any of the first k primes)
Limond
Joined Jun 2008
349 Posts
Interesting build, though I would have gone with the standard charge kit, or maybe KAM.
nfck
Joined Mar 2010
1 Post
If I understood correctly a good element is a multiple of 6 between n and n^2 that isn't equivalent to 1 or -1 mod any prime between 5 and n.

Let x be a multiple of 6. We have to find out whether x + 1 or x - 1 is a multiple of a primer number less than n. None of those two numbers is divisible by 2 (odd numbers) or 3 (should be obvious). And since they are between n and n^2 at least one of their prime factors would be between 5 and n, or they would be a prime themselves. If they are a prime x is a good number, if at least one of them isn't x is a bad number.

So in other words f(x) = # of prime pairs (twin primes) between n and n^2. Prime pair is a pair of (p, p+2) where both p and p + 2 are prime numbers. You can check about twin primes on wiki or similar.

Hope this helps.
Greyville
Joined Jan 2012
72 Posts
Finally:  Can you explain why o is limited by x*35%?  That's exactly the kind of bound I want, I just am not sure how to go about finding it, or more importantly, explaining it.  (In fact, if it's what I think you mean, that would probably precisely solve my problem.)

I'm not going to go on much about this direction, as other directions seem more promising, but I should clear this up: by x % 35 I meant x mod 35. (I tend towards programming notation by habit on that one.)

At a cursory glance, nfck's analysis seems to be correct. Wikipedia says that the existence of infinitely many prime pairs is an open question, and it looks like your problem might be equivalent. If this is the case, I wish you the best of luck

(Where/how did this problem arise?)
nelphine
Joined May 2005
866 Posts
It came up in my work on the Twin Prime Conjecture :P

I didn't really want to state that as most of the people I've talked to promptly shy away and avoid helping much.  But since you've figured it out, yes, I'm trying to prove the Twin Prime Conjecture.
AtG
Joined Feb 2010
1305 Posts
After your latest response to me I figured you were working on that or something equivalent.  I'm pretty much certain that a counting argument of the form you're attempting won't work.
nelphine
Joined May 2005
866 Posts
Yeah I'm beginning to feel like I have to stop spending hours every day trying to fix it, although I have 2 ideas left that I'd like to finish trying.  One of my big problems is really just defining a single formula algebraic formula that encapsulates what I'm trying to do.

It should be SOMETHING like: given k, let m = [p(k)^2 - p(k)]/6, where p(k) = the kth prime number, then:

f(k) = m + sum [ from i = 1 to k, sum ( from j = 3 to k, (-1)^i * 2^i *floor[m/ product ( from L = j to k, p(L) )] +n(i,j) ) ]

where n(i,j) is an element from the set {0,1,...,2^i}

Is that actually the right formula?  I think there's still something wrong with the product part of it (specifically what L should range over), sigh.. (L should range over i elements, but how do I formalize which elements??? (since for instance it could be p(3)*p(9) if i = 2, or it could be p(4)*p(6)*p(7) if i = 3.)

Anyways, assuming I can eventually figure out the right formula, then what we end up with is the sum of a set of sums of products.  Further, the total for all the sets of sums past any given set of sum must be less than the given set of sums. (So for instance if the given set of sums was the first set, which is the set considering 2*floor(m/p(j))+n(1,j), then the sum of all the later sets, for the triples and quadruples etc of primes, must total less than the first set.)  This is because all later sets are simply accounting for overlap in the given set.  Now all the n(i,j) terms in those sets are but a fraction of their total; so all the n(i,j) terms past a given i must be lower than the sum for the given ith set of sums.

This in term means if I could somehow prove that sum of all the sets of sums past the given ith set were a specific fraction of the given ith set (like 1/4), then I would have a useable bound on the n(i,j) terms.
Istaran
Joined Sep 2006
3410 Posts
@AtG: All right, mechanics of x, and why I'm using this 'equation'.

x is the set of multiples of 6 between a number and it's square.  k is the number of primes lower than the number (not including 2 and 3).  Bad elements of x are those that are equivalent to 1 or equivalent to -1 mod any prime lower than the number.  As a note, x can be a much larger set and still produce the same results, as long as it is a set of consecutive multiples of 6 such that none of them are lower than the number.

If x were infinite, and k were 3, then the number of good elements would actually be f(x) = x - (x*2/5 + x*2/7 + x*2/11 - x*4/35 - x*4/55 - x*4/77 + x*8/385)

This equation in turn is equivalent to g(x) = ((x - x*2/5) - (x - x*2/5)*2/7) - ((x - x*2/5) - (x - x*2/5)*2/7)*2/11

g(x) can then be easily manipulated to get the proof I'm looking for.

However, I then noticed my 'spread' problem (which is a result of x being finite) and bounded g(x) in order to solve it; this was fairly simple, and produced nice results.  But then I realized that g(x) wasn't actually a direct translation of the original problem (which is trying to find out how many elements of x are not equivalent to 1 or -1 mod any prime lower than the given number).  So I need to figure out if I can bound f(x) such that I can still use g(x) in a meaningful way.  Although I suppose, I could simply try to solve the problem from a different direction too, if anyone really wants to do that (or knows of a way to do that.)

It really helps that you actually explained what you're actually looking for. :P

So, I'll start by splitting it out into two portions. First is one complete pattern:
so for your k =2 , for example, one complete pattern takes a set of 35 numbers to occur. During that complete pattern you have 2 * 7 + 2 * 5 - 4 bad numbers. So good numbers = 35 - 14 - 10 - 4 = 15.
So once that first set occurs you have 15 guaranteed good numbers right there. Increasing x beyond this point can only increase f(x) above that level.

Edit to add: As k increases, we know it can't cause a zeroing out of a complete set, though the size of a complete set grows quite rapidly. For example, at k = 1, a complete set is 5 and 2 out of the set are bad. Going to k = 2, we multiply the size of a complete set by 7, basically grabbing what was previously 7 complete sets, which had a positive number of good numbers. We then eliminate 2/7s of those numbers (which divides in evenly, by definition) as bad, so we have again a positive number. (15 if you remember above).
To go from k = n to k = n + 1, we take the first P(n+3) complete sets from the previous iteration, which we know has a positive number of good numbers, and remove 2 / P(n+3) of those. Since P(n+3) is > 2, we remove less than 100% of them, so there must still be some left.

So, actually since you said all you want is to know f(x) > 0, then we basically just need to know what is the minimum x such that f(x) > 0? Given the real definition, f(x) -can't- be less than 0, because it is a count of elements.

So for k = 1, f(x) > 0 for x >= 3. For x = 1 or 2, it could be 0.
For k = 2, f(x) > 0 for x >= 5. Of the first five elements, 4 can be bad at most.
For k = 3 we start hitting issues. If we're trying to construct the worst case scenario:
I'll list some elements by which prime they are bad by to illustrate:
[5, 5, 7, 7, 11, 5, 5, 11, good!, 7, 7 & 5, 5, good!.. etc]
So we have minimum x = 9 to guarantee a good one, unlike the previous pattern of k*2+1.
For k = 4
[5, 5, 7, 7, 11, 5, 5, 11, 13, 7, 7&5, 5, 13, good!, good!, 11& 5, 5&7, 7, 11, etc] minimum x = 14. If I'm even doing it right! I'm pretty sure this pattern creates the most bad numbers before one comes in good. So here we see that both 5s and 7s got a repetition in, but the overlap showed up once. I can't see a way to remove that overlap without creating a different one.
For k = 5
[5, 5, 7, 7, 11, 5, 5, 11, 13, 7, 7&5, 5, 13, 17, 17, 11& 5, 5&7, 7, 11, good!, ...] so minimum x = 20, assuming my technique is correct. (Basely putting the new interference pattern into the first break in the existing patterns, so that the most frequent patterns can repeat most effectively.)

so the maximum x that can create no good values for a given k is 2, 4, 8, 13, 19.. it's going up by more each time (delta is 2, 4, 5, 6...)

So anyways, that second part only really matters if you need it to work for small xs. If x >= P(3) * P(4) * ... * P(k+1) * P(k+2) then you have at least one complete set and will have guaranteed at least one good. I guess it depends then how low your x needs to be able to go.

Does this help any? I don't even know. :P
Greyville
Joined Jan 2012
72 Posts
Interesting.

I don't think the problem you described earlier (or my formulation of it, which I think you agreed with):
For all k >= 1, for all x >= P(k), f_k(x) > 0
(Where P(k) is the kth prime number, starting from P(1) = 5, and f_k(x) is the 'function' you defined.)

Is actually equivalent to the problem as you stated it:
x is the set of multiples of 6 between a number and it's square.  k is the number of primes lower than the number (not including 2 and 3).  Bad elements of x are those that are equivalent to 1 or equivalent to -1 mod any prime lower than the number.  As a note, x can be a much larger set and still produce the same results, as long as it is a set of consecutive multiples of 6 such that none of them are lower than the number.

For the problem as you originally stated it (or my understanding, again), you were looking to show that there exists an x >= P(k) such that x is not congruent to any of:
a_i mod P(i)
b_i mod P(i)
...
...
a_k mod P(k)
b_k mod P(k)

for any integers a_1, ... , a_k and b_1, ... , b_k such that a_i is not congruent to b_i mod P(i).

Your later statement seems to be that problem, but with each a_i = 1, each b_i = -1 and the restriction that x must be a multiple of 6. In that way it seems a weaker statement in some ways and stronger in another.

For the problem:
For all k >= 1, for all x >= P(k), f_k(x) > 0
(Where P(k) is the kth prime number, starting from P(1) = 5, and f_k(x) is the 'function' you defined.)

If my understanding that it is with the congruences with arbitrary a_i and b_i as I described it above, then there should be a relatively simple proof for
For all k >= 1, for all x >= P(1)*P(2)*...*P(k), f_k(x) > 0
Using the Chinese Remainder Theorem. But I don't know if reducing that bound of P(1)*P(2)*...*P(k) is feasible.

and something else to point out:
x is the set of multiples of 6 between a number and it's square.  k is the number of primes lower than the number (not including 2 and 3).  Bad elements of x are those that are equivalent to 1 or equivalent to -1 mod any prime lower than the number.  As a note, x can be a much larger set and still produce the same results, as long as it is a set of consecutive multiples of 6 such that none of them are lower than the number.

If you have no upper bound on the size of x then 6*P(1)*P(2)*...*P(k) should always be a multiple of 6 not congruent to 1 or -1 mod any of the P(i).