Number Theory Number Theory Math Forum

 April 1st, 2019, 05:11 AM #1 Senior Member   Joined: Mar 2019 From: iran Posts: 318 Thanks: 14 number of primes less than n is this correct? pi(n) = number of primes less than n pi(n) = n × (1/2 × 2/3 × 4/5 × ... × p-1/p) p = largest prime less than square root of n April 1st, 2019, 05:52 AM #2 Senior Member   Joined: Mar 2019 From: iran Posts: 318 Thanks: 14 proof a prime number is a number that isn't divisible by primes less than or equal to it's square root 1/2 of numbers are not divisible by 2 2/3 of them are not divisible by 3 4/5 of them are not divisible by 5 . . . p-1/p of them are not divisible by p p = largest prime equal to or less than square root of given number so number of primes less than n is n × product of these fractions April 1st, 2019, 08:29 AM #3 Senior Member   Joined: Aug 2012 Posts: 2,426 Thanks: 760 Half of the numbers aren't divisible by 2. Then 2/3 of the numbers aren't divisible by 3 ... but you counted 6 twice so you have to account for that. Likewise 4/5 aren't divisible by 5 but you counted 10 and 15 twice, etc. So your formula works once you put in all the correction factors, which make it a lot more complicated. Thanks from topsquark Last edited by Maschke; April 1st, 2019 at 08:54 AM. April 1st, 2019, 09:55 AM #4 Senior Member   Joined: Mar 2019 From: iran Posts: 318 Thanks: 14 I didn't count composite numbers like 6 or 10. I counted prime numbers; half of numbers are not divisible by 2 (odd numbers) 1 3 5 7 9 11 as you see, 2/3 of them (odd numbers) are not divisible by 3 (1 5 7 11) 1/2 × 2/3 = 1/3 of numbers are not divisible by 2 or 3 Last edited by skipjack; April 1st, 2019 at 11:13 AM. April 1st, 2019, 10:37 AM   #5
Math Team

Joined: May 2013
From: The Astral plane

Posts: 2,345
Thanks: 986

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
 Originally Posted by youngmath I didn't count composite numbers like 6 or 10. I counted prime numbers; half of numbers are not divisible by 2 (odd numbers) 1 3 5 7 9 11 as you see, 2/3 of them (odd numbers) are not divisible by 3 (1 5 7 11) 1/2 × 2/3 = 1/3 of numbers are not divisible by 2 or 3
You aren't making your list long enough.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49 for example.

I count 15 primes out of 25 numbers. The ratio is closer to 1/2 than 1/3. This shows that your ratio of 2/3 is only an approximation. Part of the trouble here is that you have to have the whole list of primes to do your ratios. Unfortunately, that list is infinite, so you are stuck with approximations.

-Dan

Last edited by skipjack; April 1st, 2019 at 11:14 AM. April 1st, 2019, 11:25 AM #6 Global Moderator   Joined: Dec 2006 Posts: 21,124 Thanks: 2332 Of those 25 numbers, 14 are prime and 10 are composite. The 10 composite numbers comprise 7 that divide by 3, 2 that divide by 5 (but not by 3) and 1 that divides by 7 (but not by 3 or 5). Hence youngmath's method works quite well for the above example. Thanks from topsquark April 1st, 2019, 11:30 AM #7 Senior Member   Joined: Mar 2019 From: iran Posts: 318 Thanks: 14 this formula does't count prime numbers less than square root of n true formula is: pi(n) - pi(√n) = n × (1/2 × 2/3 × 4/5 × ... × p-1/p) p = largest prime less than or equal to square root of n Thanks from topsquark April 1st, 2019, 11:42 AM #8 Senior Member   Joined: Mar 2019 From: iran Posts: 318 Thanks: 14 pi(10000) = 10000 × (1/2 × 2/3 × ... × 96/97) + pi(100) = 1203 + 25 = 1228 and true value of pi(10000) is 1229 April 1st, 2019, 11:52 AM   #9
Math Team

Joined: May 2013
From: The Astral plane

Posts: 2,345
Thanks: 986

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
 Originally Posted by skipjack Of those 25 numbers, 14 are prime and 10 are composite. The 10 composite numbers comprise 7 that divide by 3, 2 that divide by 5 (but not by 3) and 1 that divides by 7 (but not by 3 or 5). Hence youngmath's method works quite well for the above example.
I see, thanks for the catch. I was doing it wrong.

-Dan Tags number, primes Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post matqkks Number Theory 10 November 5th, 2018 03:21 PM uvkajed Number Theory 2 August 5th, 2015 11:51 AM caters Number Theory 67 March 19th, 2014 05:32 PM WORLD Number Theory 5 September 3rd, 2012 03:36 PM Agno Number Theory 53 November 19th, 2011 05:10 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top      