My Math Forum primes

 Number Theory Number Theory Math Forum

 March 7th, 2013, 10: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, 10:26 PM   #2
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
Re: primes

Quote:
 Originally Posted by agustin975 How many primes is smaller than 1376 such that sum of its digits is equal 2.
Consider the 1-digit numbers : 2
Consider the 2-digit numbers : 11,20
Consider the 3-digit numbers : 110,101,200
Consider the 4-digit numbers : 1100,1010,1001,2000

The primes in the list are 2,11,101.

 March 7th, 2013, 10:31 PM #3 Member   Joined: Nov 2012 Posts: 30 Thanks: 0 Re: primes 1001?
March 7th, 2013, 10:34 PM   #4
Math Team

Joined: Mar 2012
From: India, West Bengal

Posts: 3,871
Thanks: 86

Math Focus: Number Theory
Re: primes

Quote:
 Originally Posted by agustin975 1001?
Divisible by 7.

 March 8th, 2013, 09: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, 11: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, 01: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, 02:26 PM   #8
Math Team

Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 407

Re: primes

Hello, CRGreathouse!

Quote:
 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?

I can apply my test to any six-digit number.

If a 6-digit number is comprised of two identical 3-digit numbers,
[color=beige]. . [/color]it is divisible by 7, 11 and 13.

Examples:[color=beige] .[/color]$\begin{Bmatrix}137,137=&137\,\times\,1001=&137\,\times\,7\,\times\,11\,\times\,13 \\ \\ \\ 23,023=&23\,\times\,1001=&23\,\times\,7\,\times\,11\,\times\,13 \end{Bmatrix}=$

 March 9th, 2013, 02: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, 04: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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post caters Number Theory 67 March 19th, 2014 05:32 PM PerAA Number Theory 4 October 18th, 2013 09:25 AM gelatine1 Algebra 4 September 1st, 2013 11:09 PM gelatine1 Algebra 13 July 15th, 2013 02:59 AM johnr Number Theory 20 April 9th, 2013 06:49 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top