My Math Forum  

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

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
agustin975 is offline  
 
March 7th, 2013, 09:26 PM   #2
Math Team
 
mathbalarka's Avatar
 
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.
mathbalarka is offline  
March 7th, 2013, 09:31 PM   #3
Member
 
Joined: Nov 2012

Posts: 30
Thanks: 0

Re: primes

1001?
agustin975 is offline  
March 7th, 2013, 09:34 PM   #4
Math Team
 
mathbalarka's Avatar
 
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.
mathbalarka is offline  
March 8th, 2013, 08:54 AM   #5
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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?
CRGreathouse is offline  
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.
Hedge is offline  
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...
Hedge is offline  
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:
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]

soroban is offline  
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.
Hedge is offline  
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.
Hedge is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2018 My Math Forum. All rights reserved.