March 7th, 2013, 09:21 PM  #1 
Member Joined: Nov 2012 Posts: 30 Thanks: 0  primes
How many primes is smaller than 1376 such that sum of its digits is equal 2.

March 7th, 2013, 09:26 PM  #2  
Math Team Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory  Re: primes Quote:
Consider the 2digit numbers : 11,20 Consider the 3digit numbers : 110,101,200 Consider the 4digit numbers : 1100,1010,1001,2000 The primes in the list are 2,11,101.  
March 7th, 2013, 09:31 PM  #3 
Member Joined: Nov 2012 Posts: 30 Thanks: 0  Re: primes
1001?

March 7th, 2013, 09:34 PM  #4  
Math Team Joined: Mar 2012 From: India, West Bengal Posts: 3,871 Thanks: 86 Math Focus: Number Theory  Re: primes Quote:
 
March 8th, 2013, 08:54 AM  #5 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: primes
1001 is actually a (semi)famous divisibility test: you can use it to test if large numbers [written in decimal] are divisible by 7, 11, and 13. How?

March 8th, 2013, 10:06 AM  #6 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Re: primes
Interesting. Do you repeatedly subtract one from the first and fourth digit in the starting number to test if it is a multiple of 1001 (and thus of 7, 11, 13)? So you're effectively subtracting eg 10010000n, then 1001000n, then 100100n etc? I think that would work but there might be a smarter way. 
March 8th, 2013, 12:05 PM  #7 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Re: primes
No, that doesn't work for everything. Though you could make it work by adding 1 to any pair of digits separated by two places. For instance 9999 x 1001 = 10008999 Add 1001 and you get to 10010000 then you can go on. Then at the end you would have a residue much easier to check for divisibility. But I suspect it must be easier than that? Probably based on starting from a known 0 mod 13  so for instance, 10010000 = 1001 * 10000 = 0 mod 13. 10008999 =  1001 mod 13 = 0 mod 13. That approach could probably be adapted... Thinking aloud... 
March 8th, 2013, 01:26 PM  #8  
Math Team Joined: Dec 2006 From: Lexington, MA Posts: 3,267 Thanks: 407  Re: primes Hello, CRGreathouse! Quote:
I can apply my test to any sixdigit number. If a 6digit number is comprised of two identical 3digit numbers, [color=beige]. . [/color]it is divisible by 7, 11 and 13. Examples:[color=beige] .[/color]  
March 9th, 2013, 01:11 AM  #9 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Re: primes
I'll google this eventually, but having fun playing with it for now. 5837462 = 5(1001)10^3  5(10^3) + 8(1001)10^2  8(10^2) + 3(1001)10^1  3(10^1) + 7(1001)10^0  7(10^0) +462 = 5837 + 462 mod 1001 5837 = 5(1001)  5 +837 = 837  5 mod 1001 5837462 = 5  837 + 462 mod 1001 = 370 mod 1001 = 7 mod 13, 4 mod 11, 1 mod 7 Will that work as a divisibility check for longer numbers if you add then subtract groups of three digits? I'll have a try later, got to do some things this morning. 
March 9th, 2013, 03:10 AM  #10 
Senior Member Joined: Mar 2012 Posts: 572 Thanks: 26  Re: primes
OK, one quick test for a bigger number: 27343763491 I'm guessing you start by adding the last three for any length (then alternate sign for batches of three) because there is no reason why the last three digits will change sign, whereas we saw the second to last batch change sign in the last modular calculation: 491  763 + 343  27 = 44 = 0 mod 11, 5 mod 13, 2, mod 7 Which using a calculator is correct. I like it  I think that really will keep working? If so, presumably you can do something similar for (eg) 10001 to test for divisibility by 73 and 137, but that's less likely to be useful. 

Tags 
primes 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
primes and twin primes: Number between powers of 10  caters  Number Theory  67  March 19th, 2014 04:32 PM 
primes  PerAA  Number Theory  4  October 18th, 2013 08:25 AM 
Primes in Z ?  gelatine1  Algebra  4  September 1st, 2013 10:09 PM 
Primes everywhere  gelatine1  Algebra  13  July 15th, 2013 01:59 AM 
n^2+1 n^2+n+1 primes  johnr  Number Theory  20  April 9th, 2013 05:49 PM 