My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 1 Post By Maschke
  • 1 Post By skipjack
  • 1 Post By youngmath
Reply
 
LinkBack Thread Tools Display Modes
April 1st, 2019, 04:11 AM   #1
Member
 
Joined: Mar 2019
From: iran

Posts: 64
Thanks: 6

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
youngmath is offline  
 
April 1st, 2019, 04:52 AM   #2
Member
 
Joined: Mar 2019
From: iran

Posts: 64
Thanks: 6

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
youngmath is offline  
April 1st, 2019, 07:29 AM   #3
Senior Member
 
Joined: Aug 2012

Posts: 2,265
Thanks: 690

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 07:54 AM.
Maschke is online now  
April 1st, 2019, 08:55 AM   #4
Member
 
Joined: Mar 2019
From: iran

Posts: 64
Thanks: 6

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 10:13 AM.
youngmath is offline  
April 1st, 2019, 09:37 AM   #5
Math Team
 
topsquark's Avatar
 
Joined: May 2013
From: The Astral plane

Posts: 2,138
Thanks: 872

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
Originally Posted by youngmath View Post
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 10:14 AM.
topsquark is offline  
April 1st, 2019, 10:25 AM   #6
Global Moderator
 
Joined: Dec 2006

Posts: 20,484
Thanks: 2041

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
skipjack is offline  
April 1st, 2019, 10:30 AM   #7
Member
 
Joined: Mar 2019
From: iran

Posts: 64
Thanks: 6

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
youngmath is offline  
April 1st, 2019, 10:42 AM   #8
Member
 
Joined: Mar 2019
From: iran

Posts: 64
Thanks: 6

pi(10000) = 10000 × (1/2 × 2/3 × ... × 96/97) + pi(100) = 1203 + 25 = 1228 and true value of pi(10000) is 1229
youngmath is offline  
April 1st, 2019, 10:52 AM   #9
Math Team
 
topsquark's Avatar
 
Joined: May 2013
From: The Astral plane

Posts: 2,138
Thanks: 872

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
Originally Posted by skipjack View Post
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
topsquark is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
number, primes



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Number of primes matqkks Number Theory 10 November 5th, 2018 02:21 PM
Conjecture about the number of primes uvkajed Number Theory 2 August 5th, 2015 10:51 AM
primes and twin primes: Number between powers of 10 caters Number Theory 67 March 19th, 2014 04:32 PM
problems in the primes number WORLD Number Theory 5 September 3rd, 2012 02:36 PM
Primes as the seeds for any number Agno Number Theory 53 November 19th, 2011 04:10 PM





Copyright © 2019 My Math Forum. All rights reserved.