on another thread now

Printable View

- Apr 28th 2009, 04:24 AMAquafinaPositive Integer is Prime Like
on another thread now

- Apr 28th 2009, 07:03 AMNot2l8
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 aresuch numbers between__80__and then the sequence repeats itself.__0-300__

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. - Apr 28th 2009, 12:44 PMMedia_ManA 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, $\displaystyle 100-50-33-20+16+10+6-3=26$, as Not2l8 computed.

Here is the pattern: $\displaystyle 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:

$\displaystyle 2^03^05^0=1$

$\displaystyle 2^03^05^1=5$

$\displaystyle 2^03^15^0=3$

$\displaystyle 2^03^15^1=15$

$\displaystyle 2^13^05^0=2$

$\displaystyle 2^13^05^1=10$

$\displaystyle 2^13^15^0=6$

$\displaystyle 2^13^15^1=30$

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

$\displaystyle \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 $\displaystyle b_1,b_2,b_3,...,b_n$ represents the boolean digits of $\displaystyle i$, $\displaystyle \omega_i$ represents literally the number of "on" digits, or how many prime factors are in the denominator, and $\displaystyle n$ is an independent variable representing the first $\displaystyle 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. - May 3rd 2009, 02:47 AMAquafina
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" - May 3rd 2009, 07:51 AMMedia_ManFinding 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...

$\displaystyle

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

$

... you can proceed with the following:

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

$\displaystyle \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:

$\displaystyle \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: $\displaystyle \pi_3(x)=\frac{8}{30}x \pm 4 \approx .2667x \pm 4$

Similarly, the number of very primelike integers under x is: $\displaystyle \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. - May 3rd 2009, 08:17 AMAquafina
hi i followed the first bit and got this:

http://www.mathhelpforum.com/math-he...5f43d72a-1.gifso 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?

http://www.mathhelpforum.com/math-he...81ad1e40-1.gif

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

http://www.mathhelpforum.com/math-he...d11ee6f5-1.gif - May 3rd 2009, 09:01 AMMedia_ManA few clarifications...Quote:

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

Alas, the exact value of $\displaystyle \pi_3(x)$ is $\displaystyle 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.

Quote:

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

Similarly, the equation for $\displaystyle \pi_3(x)$ contains 4 negative terms and 4 positive terms, therefore the approximation $\displaystyle \frac{8}{30}x$ could be off by as high as +4 or as low as -4. Whereas, $\displaystyle \pi_6(x) $contains 32 negative terms and 32 positive terms, therefore the approximation $\displaystyle \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 $\displaystyle \lfloor x \rfloor$, each term could be off by at most 1, as $\displaystyle \lfloor 5.86 \rfloor=5$, for example, throwing the answer off by .86 if we chose to ignore the floor function. - May 3rd 2009, 10:19 AMAquafina
thanks :D that makes sense

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

http://www.mathhelpforum.com/math-he...d11ee6f5-1.gif

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? - May 3rd 2009, 10:49 AMMedia_ManOops
Ah, yes, I see what you were referring to now. Yes, that was indeed a typo. May God strike me down.

Quote:

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?

*In fact it repeats in blocks of 30.*(Wink)

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 $\displaystyle n=2x+a=3y+b=5z+c$ for some x,y,z and nonzero a,b,c. Then look at n+30: $\displaystyle 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 $\displaystyle \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 $\displaystyle \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} - May 3rd 2009, 12:11 PMAquafina
thanks a lot :D 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 - May 4th 2009, 12:16 AMAquafina
hi i didnt get the bit where u did...

Recognizing that these factor as follows:

http://www.mathhelpforum.com/math-he...1ab5b472-1.gif

http://www.mathhelpforum.com/math-he...15b97b76-1.gif

http://www.mathhelpforum.com/math-he...81350610-1.gif

http://www.mathhelpforum.com/math-he...c3eab4f5-1.gif

http://www.mathhelpforum.com/math-he...619031dd-1.gif

http://www.mathhelpforum.com/math-he...89ffbfcc-1.gif

http://www.mathhelpforum.com/math-he...48167bfb-1.gif

http://www.mathhelpforum.com/math-he...d4199438-1.gif

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

http://www.mathhelpforum.com/math-he...7da81e71-1.gif

how do i derive that equation? - May 4th 2009, 06:42 AMMedia_ManNot 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 $\displaystyle \pi_3(x)=

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

$

Which can be written as $\displaystyle \pi_3(x)=

\lfloor\frac{x}{2^03^05^0}\rfloor-\lfloor\frac{x}{2^13^05^0}\rfloor-\lfloor\frac{x}{2^03^15^0}\rfloor-$$\displaystyle \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

$

(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: $\displaystyle 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:

$\displaystyle \pi_3(x)=+

\lfloor\frac{x}{5^03^02^0}\rfloor-\lfloor\frac{x}{5^03^02^1}\rfloor-\lfloor\frac{x}{5^03^12^0}\rfloor+$$\displaystyle \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

$

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

The last pattern to notice is that of the $\displaystyle \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 $\displaystyle \omega_i$ represent the number of 1's in the boolean representation of i, so $\displaystyle \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 $\displaystyle a_i$ as follows:

$\displaystyle 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:

$\displaystyle \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,

$\displaystyle \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 $\displaystyle \pi_n(x)$ - May 4th 2009, 07:05 AMAquafina
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...

http://www.mathhelpforum.com/math-he...5f43d72a-1.gif

... you can proceed with the following:

The floor function http://www.mathhelpforum.com/math-he...43a14b63-1.gif literally means "round down to the nearest integer" so if we remove the floor functions we get an approximating equation:

http://www.mathhelpforum.com/math-he...81ad1e40-1.gif......

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? - May 4th 2009, 07:39 AMMedia_ManWhat does the teacher want to see?Quote:

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?

I think the key challenge of the question is the fact that there is no way to trial divide every integer from 1 to $\displaystyle 10^{100}$ , forcing you to come up with something clever. The answer, by the way, so you can check your work, is about $\displaystyle 1.918*10^{99}$ (Wink) - May 4th 2009, 07:57 AMAquafina
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