Bounding a prime number based equation

[Nelphine]

Hello all!

I realize I am new to the community of online math forums, so I'm probably breaking a few etiquette rules (and possibly more important rules too - if so, please let me know and I'll fix what I can.)

However, I am working on a math problem, and I am stuck on bounding a particular equation, and I am looking for help.

I'm trying to bound a series of equations, each equation based on the first k primes greater than 3:

k = 1, f(x) = x - x*2/5

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

k = 3, 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.

For example, if x was 103, then in 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 (we can't just use the floor or ceiling).

Specifically, if x was 103, then in the first equation (-x*2/5) could be -40, -41, or -42. The value changes for each value of x.

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?

As an additional note, this equation is equivalent to (at least) one other equation, which is much easier to manipulate and put bounds on. However, since this is the original equation I am working with, I need to make sure any bounds have their basis within the original equation, and then transfer them to the other equation, in order to actually finish the problem.

 

[ramsey2879]

Hello all!

I realize I am new to the community of online math forums, so I'm probably breaking a few etiquette rules (and possibly more important rules too - if so, please let me know and I'll fix what I can.)

However, I am working on a math problem, and I am stuck on bounding a particular equation, and I am looking for help.

I'm trying to bound a series of equations, each equation based on the first k primes greater than 3:

k = 1, f(x) = x - x*2/5

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

k = 3, 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.

For example, if x was 103, then in 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 (we can't just use the floor or ceiling).

Specifically, if x was 103, then in the first equation (-x*2/5) could be -40, -41, or -42. The value changes for each value of x.

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?

As an additional note, this equation is equivalent to (at least) one other equation, which is much easier to manipulate and put bounds on. However, since this is the original equation I am working with, I need to make sure any bounds have their basis within the original equation, and then transfer them to the other equation, in order to actually finish the problem.

I can't make sense of the statement that if x = 103 then (-x*2)/5 could be -40,-41, or 42 since 103*2/5 = 41.2. If you explain the problem with more detail to avoid confusion, you stand a better chance of getting an answer to the question.

 

[Nelphine]

Fair enough; I actually posted this to a few forums, and since I wasn't getting a response here, I've been concentrating on the other ones.

But what I've certainly learned is that my initial description is AWFUL and misleading, for which I apologize. I still haven't managed to completely get a description that makes everyone happy, but I will attempt again:

k = 1, f(x) = x - (2*floor(x/5) + m), m = 0, 1 or 2

k = 2, f(x) = x - (2*(floor(x/5) + m) - (2*floor(x/7) + n) + (4*floor(x/35) + o), m = 0, 1, or 2, n = 0, 1, or 2, o = 0, 1, 2, 3, or 4.

etc


in each case, x is a set of elements, and x will be larger than k (probably by quite a large margin, for instance, if k was 10, x would be at least 273; however, the actual size of x doesn't really matter, as all the patterns and rules hold no matter what size it is, as long as it is large enough not to make f(x) trivially negative; in practice this means that x needs to be something like twice k). For every prime number (greater than 3) p, 2 out of p elements of the set of x are 'bad' elements that don't conform. An element can only be 'bad' or 'good', never partially both; thus x is an integer, f(x) is an integer, and each term of the equation will also be an integer. We don't know which 2 out of those p elements are the bad ones, only that there are exactly 2.

From my example of k = 2 above, and if we then assumed that x = 103, then there would definitely be 40 bad elements based on 5; there will also be 28 bad elements based on 7. There will be an extra m bad elements based on 5, (which represent the bad elements from 101, 102, 103, and if they existed, 104 and 105; since we don't know which 2 of those 5 elements are bad, m can be 0, 1 or 2), and an extra n bad elements based on 7, which again can be 0, 1 or 2.

However, it is possible (in fact definite) that some of the elements of x that are bad will be considered bad both because of 5 and because of 7. This means we will count those bad elements twice, so we need to balance that so that we don't overcount how many bad elements there are. Thus the final term means that 8+o elements of x will have been counted twice, where o could be 0, 1, 2, 3 or 4. However, we'll note that since x = 103, the o elements must be contained within 103-70 = 33 elements, so o must actually be at least 2.

Finishing the example, we find that f(x) = 103 - (40+m) - (28+n) + (8+o), where m = 0, 1 or 2, n = 0, 1 or 2, and o = 2, 3 or 4.
This means that f(x) > 40, which is a positive integer, and so is completely satisfactory.

However, I want this to work even if k was some large number, like 10,000; but f(x) becomes EXTREMELY unwieldy, very fast (even k = 10 is difficult to manipulate), so I need some kind of bound on what these variables m, n, o (and their like) will be, so that I can use an equivalent but much simpler to manipulate equation.

 

[ramsey2879]

You are looking on a way to determine a more restricted bound on {m,n,o,p,...}. Let's call them m(i). As far as I understand m(i) appear in the equations f(x) = y - Sum[ for 3< prime(p) < p(n), 2^j *[Floor[y/ Product(p(1),P(2)...(p(j))] + m(i)]. As far as I understand 0<= m(i)<= 2^j. You attempt to show how the occasion of bad results can limit the value for "o" to > 1 in the third to the last paragraph of your last post, but I can't see how to determine good results from bad results or whether the result for m = 0,n = 2, o = 0 is any different from the result for m = 0, n = 0, o = 2. Accordingly, I need a better understanding of your problem to help you.

 

[Nelphine]

Actually just trying to help me explain the equations f(x) in such a simple manner will be very helpful. I have 4 comments with your current suggestion, the first 3 of which are very simple (and possibly clerical).

Comment 1: "f(x) = y - ... Floor[y/...", these instances of y should be replaced with x, so that it is f(x) = x - ... Floor[x/...

Comment 2: I believe the first term in your formula would be f(x) = x - 2*[Floor[x/5] + m(1)]; this comes as a result of you forgetting to close one set of brackets, and I just want to confirm that the first term would actually be x - [2*Floor[x/5] + m(1)]

Comment 3: Some of the terms are to account for overlap when you consider the same bad element twice. Thus, to account for this you need a (-1)^j in there. Something like:
f(x) = x - Sum[ for 3< prime(p) < p(n), [(-1)^j]*[2^j *[Floor[x/ Product(p(1),P(2)...(p(j))]] + m(i)]]

Comment 4: Your suggested formula seems to run into the problem that I have had, and why I didn't try to use such a construction when initially presenting my problem. Specifically, I believe that using your formula (modified as per my previous 3 comments), if you assume k to equal 2, your formula would be
f(x) = x - 2*Floor[x/5] - m(1) + 4*Floor[x/35] + m(2)
when we actually want
f(x) = x - 2*Floor[x/5] - m(1) - 2*Floor[x/7] - m(2) + 4*Floor[x/35] + m(3)

If you could help me to find a formula that accurately represents that (or if you can explain the error I made in reading your formula if it does so), that would greatly help me.

As to the other issue: There would be a different result because m and n are negative, and o is positive. If you changed your question to 'is there a difference between m = 2, n = 0, o = 0, and m = 0, n = 2, o = 0?' then you would be correct that there is no difference for my purposes.

However, my whole problem is that determining PRECISELY which results are good and which results are bad, is completely dependent on x. For every value of x, you could (in theory) have a different precise determination of which ones are good and which are bad. Thus why I need to find bounds on the formula of how many are bad; finding an exact answer is definitely NOT what I am trying to do.

 

[Nelphine]

My attempt at a proper formula, although I know it's not quite right:

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}

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 specific terms could be p(3)*p(9) if i = 2, or it could be p(4)*p(6)*p(7) if i = 3.)

 

[Nelphine]

Another thing that has been pointed out to me that is wrong with that formula: I forgot to include a set of brackets containing [2^i *floor[m/ product ( from L = j to k, p(L) )] +n(i,j)], as both of those terms should be affected by the (-1)^i