Math puzzle

Orgasmic Troll · 2004-12-12, 22:02

All prime numbers greater than 5 end in either 1,3,7 or 9 in base 10. Given a number of n digits where every digit is either 1,3,7 or 9, what is the probability that the number is prime?

If it isn't prime, append digits randomly chosen from {1,3,7,9} until the number is prime. What is the expected number of digits that you will have to add?

Note: I don't know the answer, I don't even know how you would attack it.. I'm interested in seeing what lines of attack people would take against this.

Fusion_power · 2004-12-12, 23:39

A very interesting question. And one that almost requires a proof of the Reimann hypothesis to answer fully.

Stipulate that all even numbers (except 2) are always composite and should not be considered in the percentages. Approximately 10% of all numbers less than 1000 are prime. It follows that 500 of the numbers below 1000 end in an odd number. And since @100 of those 500 numbers are prime, the odds of a given number below 1000 that ends in an odd number being prime would be 20%. This percentage quickly decreases as the size increases. Please note that I am not separating out numbers that end in 5.

I suspect that a certain item from Euler should be applied in a rather novel way.

Fusion

jinydu · 2004-12-13, 00:08

I'm pretty sure your first question doesn't require Riemann's Hypothesis. Please let me restate it:

Given a randomly chosen number of n digits where every digit is either 1,3,7 or 9, what is the probability that the number is prime?

The phrase randomly chosen is necessary because for any particular number, the probability that it is prime is either 0 or 1.

I note that you said that every digit is 1, 3, 7 or 9, not just the last digit. This complicates things considerably. Instead, I'll attack a problem I know how to handle:

Given a randomly chosen number of n digits where the last digit is either 1,3,7 or 9, what is the probability that the number is prime?

A natural number with n digits is between 10^(n-1) and 10^n. According to Gauss, once n is sufficiently large, the number of primes below n is approximately n/(log n), where log is the natural logarithm. Thus, the number of n digit primes is approximately:

(10^n)/(n log 10) - (10^(n-1))/(n log 10)

= (9*10^(n-1))/(n log 10)

The number of naturals with a last digit of 1, 3, 7 or 9 is just 40% of the total number of naturals in the interval. For an n digit number, that's:

0.4*(10^n) - 0.4*(10^(n-1))

= 0.4*(9*10^(n-1))

= 3.6 * 10^(n-1)

Dividing both, we get:

2.5/(n log 10) ~= 1.08574/n

That would be the probability that the number is prime. Please note that its only accurate when n is large, so don't try plugging in n = 1

.

The second problem is too hard for me...

2004-12-12, 22:02	#1
Orgasmic Troll Cranksta Rap Ayatollah Jul 2003 641 Posts	Math puzzle All prime numbers greater than 5 end in either 1,3,7 or 9 in base 10. Given a number of n digits where every digit is either 1,3,7 or 9, what is the probability that the number is prime? If it isn't prime, append digits randomly chosen from {1,3,7,9} until the number is prime. What is the expected number of digits that you will have to add? Note: I don't know the answer, I don't even know how you would attack it.. I'm interested in seeing what lines of attack people would take against this.

2004-12-12, 23:39	#2
Fusion_power Aug 2003 Snicker, AL 959₁₀ Posts	A very interesting question. And one that almost requires a proof of the Reimann hypothesis to answer fully. Stipulate that all even numbers (except 2) are always composite and should not be considered in the percentages. Approximately 10% of all numbers less than 1000 are prime. It follows that 500 of the numbers below 1000 end in an odd number. And since @100 of those 500 numbers are prime, the odds of a given number below 1000 that ends in an odd number being prime would be 20%. This percentage quickly decreases as the size increases. Please note that I am not separating out numbers that end in 5. I suspect that a certain item from Euler should be applied in a rather novel way. Fusion Last fiddled with by Fusion_power on 2004-12-12 at 23:40

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Math-related puzzle links	rogue	Puzzles	1	2007-03-31 23:22
Ramanujan math puzzle cracked at last	Jeff Gilchrist	Math	1	2005-03-24 02:31
math puzzles by Dell (puzzle company)....	ixfd64	Puzzles	0	2004-03-16 00:25
Here's a new math puzzle	hyh1048576	Puzzles	12	2003-06-27 15:46
Offtopic: Math Puzzle	Matthes	Puzzles	28	2003-06-19 20:27

2004-12-13, 00:08	#3
jinydu Dec 2003 Hopefully Near M48 2×3×293 Posts	I'm pretty sure your first question doesn't require Riemann's Hypothesis. Please let me restate it: Given a randomly chosen number of n digits where every digit is either 1,3,7 or 9, what is the probability that the number is prime? The phrase randomly chosen is necessary because for any particular number, the probability that it is prime is either 0 or 1. I note that you said that every digit is 1, 3, 7 or 9, not just the last digit. This complicates things considerably. Instead, I'll attack a problem I know how to handle: Given a randomly chosen number of n digits where the last digit is either 1,3,7 or 9, what is the probability that the number is prime? A natural number with n digits is between 10^(n-1) and 10^n. According to Gauss, once n is sufficiently large, the number of primes below n is approximately n/(log n), where log is the natural logarithm. Thus, the number of n digit primes is approximately: (10^n)/(n log 10) - (10^(n-1))/(n log 10) = (910^(n-1))/(n log 10) The number of naturals with a last digit of 1, 3, 7 or 9 is just 40% of the total number of naturals in the interval. For an n digit number, that's: 0.4(10^n) - 0.4(10^(n-1)) = 0.4(910^(n-1)) = 3.6 10^(n-1) Dividing both, we get: 2.5/(n log 10) ~= 1.08574/n That would be the probability that the number is prime. Please note that its only accurate when n is large, so don't try plugging in n = 1 . The second problem is too hard for me...