# Prime Numbers

• Feb 28th 2014, 02:00 PM
Prime Numbers
Hi all, there are two games we play as bets and I wondered if there are anyway to increase my odds other than randomly ending in 1,3,7,9.
winner is always first person correct, you take it in turns and get say 15 secs each ago.

game one - random range given ie 4000-5000 first to guess a prime
game two - random range given ie 4000-5000 first to guess a double prime (11,13/17,19/29,31)

last question is there anyway to group all prime numbers (except grouping by end 1,3,7,9)
Euler rule I have read but can't apply it in time to the games lol

I'll add a pole and could you vote wether there is anyway to increase my chances or not. Ie it's a 50/50 game.

• Mar 6th 2014, 03:01 PM
Jabbie
Re: Prime Numbers
Kinda hard
• Mar 7th 2014, 01:05 AM
Re: Prime Numbers
Yeah I think it's a 50/50 game, would people mind voting many thanks
• Mar 12th 2014, 08:23 AM
Deveno
Re: Prime Numbers
If one player reduces mod 3, and the other does not (this can be done using a sum of digits strategy) then that player has better odds than the other.

For example, if the range is 1,000 numbers, it is obvious that neither player picks an even number, so we have 500 to choose from. Removing the 100 numbers that are odd multiples of 5, leaves both players a pool of 400.

However, if the player uses the "mod 3" strategy, they might eliminate (depending on the start of the range) another 133-134 numbers or so, meaning they have, if the number of prime numbers in the range is x:

x/267 vs. x/400 chance of picking a prime.

This strategy becomes even MORE useful in picking prime pairs, since MOST odd pairs will have at least one element of the pair divisible by 3.

Of course, if both players use this strategy, they both have the same odds.
• Mar 12th 2014, 09:04 AM
Shakarri
Re: Prime Numbers
The mod 3 rule which Deveno mentioned is that if you add up all the digits of a number and the sum is divisible by 3 then the original number is also divisible by 3. I believe this is the only other rule which is quick enough to do in 15 seconds.
• Mar 12th 2014, 09:16 AM
SlipEternal
Re: Prime Numbers
Seeing if a number is divisible by 7 is not too terrible. Take the rightmost digit and double it. Subtract the doubled number from the remaining digits. If that new number is divisible by 7, then the original number was, as well.

Example: 203
The right-most digit is 3, so doubling it gives 6. The remaining digits are "20", so 20-6 = 14, which is divisible by 7, so 203 is divisible by 7. $203 = 7\cdot 29$

Example: 2,023. The right-most digit is 3, so doubling it gives 6. The remaining digits are "202", so 202-6 = 196. How can I tell if that is divisible by 7? Well, we do the process again. The right-most digit is now 6, so doubling it gives 12. 19-12 = 7, which is divisible by 7, so 196 is divisible by 7, hence 2,023 is divisible by 7. $2,023 = 7\cdot 289$

You would need to use this process at most twice for each number in the range 4,000-5,000.

Seeing if a number is divisible by 11 is easy, too. Add up odd-positioned digits and even-positioned digits. If the difference between those sums is divisible by 11, then the original number is divisible by 11.

Example: 4,697. The odd-positioned digits are 4 and 9. The even-positioned digits are 6 and 7. The sums are both 13, and 13-13 = 0, which is divisible by 11. Hence, 4,697 is divisible by 11. $4,697 = 11\cdot 427$

Example: 4,081. The odd-positioned digits are 4 and 8. The even-positioned digits are 0 and 1. The sums are 12 and 1, and 11-1 = 11, which is divisible by 11. Hence 4,081 is divisible by 11. $4,081 = 11\cdot 371$
• Mar 12th 2014, 10:23 AM
SlipEternal
Re: Prime Numbers
A possibly simpler rule for divisibility by 7 is this: Take the last two digits mod 7. Subtract three times that from the leftmost digits (without the right-most two). If that is divisible by 7, then the whole number is divisible by 7.

Example: 4,571. 71 = 70+1. 45-3*1 = 42 is divisible by 7, so 4,571 is, as well. $4,571 = 7\cdot 653$.

Example: 4,249. 49 = 49+0. 42-3*0 = 42 is divisible by 7, so 4,249 is, as well. $4,249 = 7\cdot 607$.

Example: 4,781. 81 = 77+4. 47-3*4 = 35 is divisible by 7, so 4,781 is, as well. $4,781 = 7\cdot 683$.
• Mar 12th 2014, 10:49 AM
Deveno
Re: Prime Numbers
Quote:

Originally Posted by SlipEternal
A possibly simpler rule for divisibility by 7 is this: Take the last two digits mod 7. Subtract three times that from the leftmost digits (without the right-most two). If that is divisible by 7, then the whole number is divisible by 7.

Example: 4,571. 71 = 70+1. 45-3*1 = 42 is divisible by 7, so 4,571 is, as well. $4,571 = 7\cdot 653$.

Example: 4,249. 49 = 49+0. 42-3*0 = 42 is divisible by 7, so 4,249 is, as well. $4,249 = 7\cdot 607$.

Example: 4,781. 81 = 77+4. 47-3*4 = 35 is divisible by 7, so 4,781 is, as well. $4,781 = 7\cdot 683$.

Excellent! Another strategy to improve your odds. You should have placed a wager :P
• Mar 12th 2014, 02:44 PM
SlipEternal
Re: Prime Numbers
Since the range given is 4000-5000, you can also reverse it. Take the left two digits and find what they are equal to mod 7. Add twice that to the right two digits, and if it is divisible by 7, so was the original number. Using the same examples as above:

4,571: 45 = 42+3 and 71+2*3 = 77 is divisible by 7

4,249: 42 = 42+0 and 49+2*0 = 49 is divisible by 7

4,781: 47 = 42+5 and 81+2*5 = 91 is divisible by 7

In general, to figure out if a number is divisible by a prime (other than 2 or 5), you can do it digit by digit. For example, suppose your number is $x$, and you want to figure out if it is divisible by the prime $p$. Using the division algorithm, you can write $x$ two different ways:

$x = 10q_1 + r_1, 0\le r_1 < 10$
$x = pq_2 + r_2, 0 \le r_2 < p$

Truncating off the right-most digit gives $q_1$. Consider $q_1 + kr_1$ using the division algorithm:

$q_1 + kr_1 = pq_3 + r_3, 0\le r_3 < p$

Multiply both sides by 10 and both add and subtract $r_1$:

$(10q_1 + r_1) - r_1 + 10kr_1 = 10pq_3 + 10r_3$

Since $10q_1+r_1 = x = pq_2+r_2$, you have:

$pq_2 + r_2 + (10k-1)r_1 = 10pq_3 + 10r_3$

Find $k$ such that $10k-1 \equiv 0 \pmod{p}$. You want to keep $k$ small, so try both positive and negative values for $k$ until you find one that works. Then, $10k-1 = pz$ for some $z \in \mathbb{Z}$. This gives:

$pq_2 +r_2 + pzr_1 = 10pq_3 + 10r_3$

Moving everything with a $p$ to the LHS and everything else to the RHS gives:

$p(q_2 + zr_1 - q_3) = 10r_3 - r_2$

Since $0\le r_2 < p$ and $0\le r_3 < p$, you know that $r_2 = 0$ if and only if $r_3 = 0$.

To remove two digits at a time, instead of using $x = 10q_1 + r_1$, use $x = 100q_1 + r_1, 0\le r_1 < 100$, and the process is the same, only instead of trying to find the value for $k$ with smallest absolute value such that $10k-1 \equiv 0 \pmod{p}$, you are looking for the value for $k$ with smallest absolute value such that $100k-1 \equiv 0 \pmod{p}$.
• Mar 12th 2014, 05:00 PM
SlipEternal
Re: Prime Numbers
Oh, another strategy is to write the numbers in a different base. For example, in base 34, you would be choosing numbers of the form $d_2\cdot 34^2 + d_1\cdot 34^1 + d_0\cdot 34^0$. Using base-34, you have:

\begin{align*}34 & \equiv 0 \pmod{2} \\ 34 & \equiv 1 \pmod{3} \\ 34 & \equiv -1 \pmod{5} \\ 34 & \equiv -1 \pmod{7} \\ 34 & \equiv 1 \pmod{11} \\ 34 & \equiv 0\pmod{17}\end{align*}

So, if the rightmost digit is even or 17, then the whole number is divisible by 2 or 17. If the sum of the digits is divisible by 3 or 11, the whole number is. If you add up odd-positioned digits and subtract the even-positioned digits, if that sum is divisible by 5 or 7, so is the whole number. Out of numbers less than 100 and all primes up to 67 (since the square root of 5000 is between 70 and 71, you don't need to check for primes higher than 67), if you consider each number mod each prime, no number is congruent to 0, 1, or -1 for more than six of those primes. The smallest number to be congruent to 0, 1, or -1 mod six of those primes is 34.

This gives three things to check. The rightmost digit, the sum of the digits, and the difference of the sums of odd- and even-positioned digits.

Numbers would be between $3\cdot 34^2+15\cdot 34+22 = 4000$ and $4\cdot 34^2+11\cdot 34 + 1 = 5000$

So, you pick a number where $d_0 \equiv 1 \pmod{2}$ and $d_0 \neq 17$. You also don't want $d_0+d_1+d_2$ to be divisible by 3 or 11, and you don't want $d_0+d_2-d_1$ to be divisible by 5 or 7. Since these sums will be less than 100, this divisibility should be easy to check in each case.