Results 1 to 15 of 15

Math Help - Positive Integer is Prime Like

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    Positive Integer is Prime Like

    on another thread now
    Last edited by Aquafina; June 10th 2009 at 06:58 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2009
    Posts
    13
    Hi there,

    I'm a totally non maths guy. But I've looked at primes for fun over the last few weeks...

    By your definition (not divisible by 2,3,5) I can tell you there are 26 'prime like' numbers between 0-100 28 in 100-200 & 26 between 200-300

    What might be useful for you to know is that there are 80 such numbers between 0-300 and then the sequence repeats itself.

    In other words in 0-900 there will be 240 'prime like' numbers in 0-90000
    there will be (90000/300 x 80) 24000 etc.

    In a number not divisible by 300 eg. 1000 just go 1000/300 = 3 remainder 100 so there are 3x80 + 28 (number of 'prime likes' in 0-100)
    So 268 'prime like' numbers between 0-1000.

    The sequences for your 'very prime like' numbers also start repeating themselves at various intervals and I can give you a cumbersome formula for the answer, but I'm sure an actual maths guy could explain it better.

    The above is probably useless to you, just trying to contribute while I wait for someone to answer my post as well.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    A Simple Sieve

    Start with 100. Subtract out the 50 multiples of 2, the 33 multiples of 3, and the 20 multiples of 5. Merely subtracting these numbers puts us in the negative, because there is a lot of overlap, double and triple eliminating certain numbers. So, go into the negative, and then add back in the 16 multiples of 6, the 10 multiples of 10, and the 6 multiples of 15. Now we have another problem, as we've double un-eliminated the 3 multiples of thirty. After all of this, 100-50-33-20+16+10+6-3=26, as Not2l8 computed.

    Here is the pattern: x-\lfloor\frac{x}{2}\rfloor-\lfloor\frac{x}{3}\rfloor-\lfloor\frac{x}{5}\rfloor+\lfloor\frac{x}{6}\rfloo  r+\lfloor\frac{x}{10}\rfloor+\lfloor\frac{x}{15}\r  floor-\lfloor\frac{x}{30}\rfloor

    Recognizing that these factor as follows:

    2^03^05^0=1
    2^03^05^1=5
    2^03^15^0=3
    2^03^15^1=15
    2^13^05^0=2
    2^13^05^1=10
    2^13^15^0=6
    2^13^15^1=30

    We can simply add when the number of factors is even, and subtract when odd:

    \pi_n(x)=\sum_{i=0}^{2^n-1}(-1)^{\omega_i}\lfloor\frac{x}{p_1^{b1} p_2^{b2}p_3^{b3}...p_n^{bn}}\rfloor

    Where b_1,b_2,b_3,...,b_n represents the boolean digits of i, \omega_i represents literally the number of "on" digits, or how many prime factors are in the denominator, and n is an independent variable representing the first n prime numbers.

    This is an admittedly complicated equation, but works much better as a computer program, crunching large numbers very quickly. Setting n=6 gives you the primes 2,3,5,7,11,13 as you request in your post.

    Also note that for an "approximation" just drop the floor functions and use the GCD to combine all these fractions. This will give you a polynomial of degree n with rational coefficients that will do the job.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Apr 2009
    Posts
    190
    hi, thanks for the reply! i didnt understand the last bit though, do u have an easier method perhaps?

    because at the end of the question it says:

    "Explain your reasoning as carefully as you can"
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Finding an approximation...

    Try out the experiment I mentioned in my first paragraph for yourself, and you can see the pattern. If you follow me to here...

    <br /> <br />
x-\lfloor\frac{x}{2}\rfloor-\lfloor\frac{x}{3}\rfloor-\lfloor\frac{x}{5}\rfloor+\lfloor\frac{x}{6}\rfloo  r+\lfloor\frac{x}{10}\rfloor+\lfloor\frac{x}{15}\r  floor-\lfloor\frac{x}{30}\rfloor<br />

    ... you can proceed with the following:

    The floor function \lfloor x \rfloor literally means "round down to the nearest integer" so if we remove the floor functions we get an approximating equation:

    \pi_3(x) \approx x-\frac{x}{2}-\frac{x}{3}-\frac{x}{5}+\frac{x}{6}+\frac{x}{10}+\frac{x}{15}-\frac{x}{30}

    Realizing that we can easily get a common denominator, we have:

    \pi_3(x) \approx \frac{30x-15x-10x-6x+5x+3x+2x-x}{30}=\frac{8}{30}x

    Therefore approximately 8 in 30 numbers on the number line are "primelike" as you call them. By stripping the original exact equation of the floor functions, we introduce an error of at most +1 for the positive terms and -1 for the negative terms. Therefore,

    The number of primelike integers under x is given by: \pi_3(x)=\frac{8}{30}x \pm 4 \approx .2667x \pm 4

    Similarly, the number of very primelike integers under x is: \pi_6(x)=\frac{5760}{30030}x \pm 32 \approx .1918x \pm 32

    So about 27% of all numbers are primelike, and 19% are very primelike. As an added bonus, the error percentage of this estimate decreases very quickly. For example, using this equation, there are approximately 191808 very primelike numbers under a million, give or take 32, which is an error margin of only .0032%

    *Note: I made the statement earlier that the exact form of this sieving equation works better as a computer program than an equation. If the approximation is what you are after, then I hope this post is clear. If you are interested in experimenting with the exact answers, let me know and I can provide you with the pseudocode that puts this formula into action. If you are familiar with computer programming, you can therefore create a program that returns an exact answer staggeringly quickly, as in fractions of a second even for numbers so large the computer has just barely enough memory to hold them.
    Last edited by Media_Man; May 3rd 2009 at 11:51 AM. Reason: Fixed a typo
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2009
    Posts
    190
    hi i followed the first bit and got this:

    so are these the prime like numbers less than 100? will i have to start again for 1000, by subtracting and adding numbers that arent prime like?

    also, whats the pi 3 bit here, and the similiar ones seen in the other equations?



    finally, how did the 4 turn into a 32 in this:

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    A few clarifications...

    also, whats the pi 3 bit here, and the similiar ones seen in the other equations?
    In number theory, \pi(x) actually has nothing to do with the number \pi=3.1415926..., and instead literally means "the number of primes less than or equal to x." For example, \pi(100)=25, because there are 25 primes under 100, and \pi(101)=26 since 101 is itself prime. Since this can be construed as "the number of ints under x not divisible by 2,3,5,7,11,13,17,..." I thought it a fitting notation to call the function "the number of ints under x not divisible by 2,3,5, the first 3 primes" as \pi_3(x). Similarly, I am calling \pi_6(x) "the number of ints less than or equal to x not divisible by 2,3,5,7,11,13, the first 6 primes." Please understand this is just my own personal choice of notation here. This habit, as you know, comes from the desire to generalize these kinds of results. Now, for all eternity, we can call the function \pi_n(x) "the number of positive integers less than or equal to x that are not divisible by the first n primes."

    Alas, the exact value of \pi_3(x) is x-\lfloor\frac{x}{2}\rfloor-\lfloor\frac{x}{3}\rfloor-\lfloor\frac{x}{5}\rfloor+\lfloor\frac{x}{6}\rfloo  r+\lfloor\frac{x}{10}\rfloor+\lfloor\frac{x}{15}\r  floor-\lfloor\frac{x}{30}\rfloor , not just for x up to 100 or 1000, but for every number on the number line.

    finally, how did the 4 turn into a 32 in this:
    This equation is simply the final result of calculations I did not include in my post, because they are way too long. The equation above for \pi_3(x) only contains 8 terms ( 2^3). However, the equation for \pi_6(x), if you care to expand it, contains 64 terms  (2^6), involving coefficients of up to 5 digits. (I cheated and used a computer )

    Similarly, the equation for \pi_3(x) contains 4 negative terms and 4 positive terms, therefore the approximation \frac{8}{30}x could be off by as high as +4 or as low as -4. Whereas, \pi_6(x) contains 32 negative terms and 32 positive terms, therefore the approximation \frac{5760}{30030}x could be off by as high as +32 or as low as -32. Again, the reasoning behind this is that by ignoring the floor function \lfloor x \rfloor, each term could be off by at most 1, as \lfloor 5.86 \rfloor=5, for example, throwing the answer off by .86 if we chose to ignore the floor function.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Apr 2009
    Posts
    190
    thanks that makes sense

    i presume it was a typo then at the bit where u said:



    with the first 4 being a 32?

    would a question of this sort rely on these methods that you have used in number theory? or would there be approaches using basic school mathematics as well?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Oops

    Ah, yes, I see what you were referring to now. Yes, that was indeed a typo. May God strike me down.

    would a question of this sort rely on these methods that you have used in number theory? or would there be approaches using basic school mathematics as well?
    Well, Not2l8 seems to have used a computer to verify that the sequence repeats in blocks of 300. In fact it repeats in blocks of 30.

    Here is a visual for you. In bold are the primelike numbers:

    01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
    31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
    61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

    The fact that they appear to line up in columns is not a coincidence. Suppose n<30 is primelike. Then n leaves a nonzero remainder when divided by 2,3, or 5. So let n=2x+a=3y+b=5z+c for some x,y,z and nonzero a,b,c. Then look at n+30: n+30=2(x+15)+a=3(y+10)+b=5(z+6)+c. So n+30 also leaves a nonzero remainder when divided by 2,3, or 5. Therefore, if n is primelike, n+30 is also primelike, and vice versa. Since there are 8 primelikes between 1 and 30, the number of primelikes under x is approximately \frac{8}{30}x

    What makes 30 special is that 30=lcm(2,3,5)=2*3*5. Hopefully this is "basic school" enough. However, the \pm4 error bit is probably impossible to extract out of this line of reasoning. You would just have to commit the first 8 primelike numbers to memory, and apply the following logic: Take 522. Since 522=510+12=30*17+12, there are 17*8=136 primelikes up to 510, and since there are 3 between 1 and 12, there are 3 from 511 to 522.

    For the very primelike case, this process repeats in blocks of 30030, more than you probably want to have to hand-calculate and memorize. If you did, however, choose to count up and memorize the first 5760 very primelike numbers, then you could apply all the same logic as in the previous example.

    *Note: The practical application for what you are doing is finding prime numbers quickly. Since a prime greater than 30 must be primelike, then ALL prime numbers over thirty must be of the form 30k+a, for a={1,7,11,13,17,19,23,29}
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Apr 2009
    Posts
    190
    thanks a lot that answers it

    on a side note, since you've done number theory, when you try to solve how many triangular numbers are square numbers, it comes to this pell equation: x^2 - 2y^2 = 1

    have a look at the link: Square Triangular Number -- from Wolfram MathWorld

    how do i solve the pell's equation now? is it reasonable to presume that there are infinite many integer solutions for any pell's equation?

    this is also a case, square pentagonal numbers:

    Pentagonal Square Number -- from Wolfram MathWorld
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Apr 2009
    Posts
    190
    hi i didnt get the bit where u did...

    Recognizing that these factor as follows:










    We can simply add when the number of factors is even, and subtract when odd:



    how do i derive that equation?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Not a good idea

    Though this equation is theoretically correct, I cannot think of a single practical way to use it.

    Consider what we have proved earlier, that \pi_3(x)=<br />
x-\lfloor\frac{x}{2}\rfloor-\lfloor\frac{x}{3}\rfloor-\lfloor\frac{x}{5}\rfloor+\lfloor\frac{x}{6}\rfloo  r+\lfloor\frac{x}{10}\rfloor+\lfloor\frac{x}{15}\r  floor-\lfloor\frac{x}{30}\rfloor<br />

    Which can be written as \pi_3(x)=<br />
\lfloor\frac{x}{2^03^05^0}\rfloor-\lfloor\frac{x}{2^13^05^0}\rfloor-\lfloor\frac{x}{2^03^15^0}\rfloor- \lfloor\frac{x}{2^03^05^1}\rfloor+\lfloor\frac{x}{  2^13^15^0}\rfloor+\lfloor\frac{x}{2^13^05^1}\rfloo  r+\lfloor\frac{x}{2^03^15^1}\rfloor-\lfloor\frac{x}{2^13^15^1}\rfloor<br />

    (All we're doing here is simply prime-factoring the denominators.) Notice that in the denominator, every combination of three 0's and 1's is used in the exponents. The following numbers are the boolean representations of integers 0 through 7: 000_2,001_2,010_2,011_2,100_2,101_2,110_2,111_2. In the above equation, they appear out of order, so let's rewrite again:

    \pi_3(x)=+<br />
\lfloor\frac{x}{5^03^02^0}\rfloor-\lfloor\frac{x}{5^03^02^1}\rfloor-\lfloor\frac{x}{5^03^12^0}\rfloor+ \lfloor\frac{x}{5^03^12^1}\rfloor-\lfloor\frac{x}{5^13^02^0}\rfloor+\lfloor\frac{x}{  5^13^02^1}\rfloor+\lfloor\frac{x}{5^13^12^0}\rfloo  r-\lfloor\frac{x}{5^13^12^1}\rfloor<br />

    Since each of these terms correspond to a number 0 through 7, create a sequence called a_i such that if we find the boolean representation of i=(b_1b_2b_3)_2, then a_i=\lfloor \frac{x}{2^{b1}3^{b2}5^{b3}} \rfloor

    The last pattern to notice is that of the \pm signs. I do not know of a straight-up formula mapping {0,1,2,3,4,5,6,7} to {+--+-++-}, but the rule nonetheless is simple: If there are an even number of 1's, you use +, and if there are an odd number of 1's, you get -. So let \omega_i represent the number of 1's in the boolean representation of i, so \omega={0,1,1,2,1,2,2,3}. As you know, when we put -1 to an even power, the result is +1, and when put to an odd power, the result is -1, the exact pattern here. So adjust a_i as follows:

    a_i=(-1)^{\omega_i}\lfloor \frac{x}{2^{b1}3^{b2}5^{b3}} \rfloor

    Now, simply add all eight terms together, and you have your answer:

    \pi_3(x)=\sum_{i=0}^{7}a_i=\sum_{i=0}^{7}(-1)^{\omega_i}\lfloor \frac{x}{2^{b1}3^{b2}5^{b3}} \rfloor

    The biggest use of this way of writing is acknowledging that the same basic algorithm works whether we use 3 primes, 6 primes, or 600. Generalizing,

    \pi_n(x)=\sum_{i=0}^{2^n-1}(-1)^{\omega_i}\lfloor \frac{x}{2^{b1}3^{b2}5^{b3}...p_n^{bn}} \rfloor

    Hopefully this post is clear enough to follow. Again, I stress that this equation cannot be simplified in any way I know of, and is practically useless at calculating actual values for an arbitrary x. It is the most compact way of expressing the sieving algorithm outlined in my first post. If you truly want to test it out, I can help you with a computer program accepting x and n as inputs and spitting out \pi_n(x)
    Last edited by Media_Man; May 4th 2009 at 08:00 AM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Apr 2009
    Posts
    190
    ah thanks! so for the means of this question, i just use the approximation method u used, i.e. being

    Try out the experiment I mentioned in my first paragraph for yourself, and you can see the pattern. If you follow me to here...



    ... you can proceed with the following:

    The floor function literally means "round down to the nearest integer" so if we remove the floor functions we get an approximating equation:

    ......

    but the other one u showed is the actual formula, which isnt required for this as such. that makes sense.

    why do they ask about the "explain your reasoning carefully" part with the very prime like under 10^10, and 10^100? Is that to do with that the percentage error is decreasing like you said?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    What does the teacher want to see?

    why do they ask about the "explain your reasoning carefully" part with the very prime like under 10^10, and 10^100? Is that to do with that the percentage error is decreasing like you said?
    Well, it depends on what the exact wording on the question is. Do they want an approximate answer, \pm an error margin? Or do they want an exact answer, regardless of the method? Are you allowed to use a computer? Having now equipped yourself with three or four different ways of solving this problem, you might ask the person who posed this question in the first place which line of attack might be most appropriate.

    I think the key challenge of the question is the fact that there is no way to trial divide every integer from 1 to 10^{100} , forcing you to come up with something clever. The answer, by the way, so you can check your work, is about 1.918*10^{99}
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member
    Joined
    Apr 2009
    Posts
    190
    thanks a lot! ill ask him and let u know if there is any confusion.

    I think i asked earlier im not sure, but do u know if the pell equation:

    x^2 - 2(y^2) = 1

    will have infinite integer solutions? it was to do with that triangular square numbers stuff and pentagonal square numbers
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. any positive integer can be expressed..
    Posted in the Algebra Forum
    Replies: 9
    Last Post: February 28th 2011, 12:31 PM
  2. Replies: 5
    Last Post: October 16th 2010, 12:08 AM
  3. Raise integer to positive integer power
    Posted in the Algebra Forum
    Replies: 2
    Last Post: May 21st 2009, 01:20 PM
  4. positive integer
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 23rd 2009, 05:38 AM
  5. Replies: 1
    Last Post: May 5th 2008, 12:35 PM

Search Tags


/mathhelpforum @mathhelpforum