mersenneforum.org 5 digit factorization
 Register FAQ Search Today's Posts Mark Forums Read

 2016-02-24, 05:13 #1 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 2·503 Posts 5 digit factorization Hi Math People, My puzzle today is to factor the number 46423. I would like to see how to use the fact that 7*11*13 = 1001 is related. Regards, Matt
 2016-02-24, 05:28 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 22×3×17×31 Posts TF to ~60 appears to be adequate.
 2016-02-24, 06:07 #3 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×29×167 Posts The famous divisibilty test for 7, 11 and 13 at once LaurV recently mentioned that he'd invented this divisibilty test when he was in 7th grade. Well, he ...and perhaps, many others. It goes like this: 1. you are given a large (for a human eye) number N, e.g. 20 or even 40 or 80 digits 2. you then split from right to left every three positions (in your case 46'423) 3. you add up all odd skip-every-other groups of digits (here, simply 46) 4. you add up all even skip-every-other groups (here, simply 423) 5. subtract smaller from the larger (here, you get 377) 6. Now you can test for divisibility for 7, 11 and 13 (377 doesn't divide by 7 or 11 but 13 divides it 7. Therefore, here, 7 or 11 do not divide N, but 13 does. 8. Divide out. (Here, the remainder is prime. You are done factoring!)
 2016-02-24, 06:09 #4 S485122     "Jacob" Sep 2006 Brussels, Belgium 6EE16 Posts . Last fiddled with by S485122 on 2016-02-24 at 06:12 Reason: Sergey was quicker and much more didactic
2016-02-29, 08:57   #5
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

9,859 Posts

Quote:
 Originally Posted by Batalov LaurV recently mentioned ...
True, but quite complicate.
Because 1001 is multiple of 7, 11, and 13, subtracting it from your number won't change the divisibility to any of these 3 primes. Also, subtracting 10 times it, or subtracting 100 times it. So, you get rid first of 3003, remaining 43420, then get rid of 2002(0) remaining 23400 (you just imaginary shift the digits by 3 and subtract the smaller from the bigger, i.e. in 46423, 6 is bigger than 3, get rid of 3, you have 43420, then first 4 is bigger than 2, get rid of twos, you have 23400). So your problem is to find out if 234 is divisible with either 7, 11, or 13, and splitting it in 2 (easier to do it in your mind than all those additions) leaves 117 which you can immediately see that it does not split to 11 (it leaves a 7 residue, cutting the 11), nor 7 (cut the last 7, it leaves a 40, i.e. a 5 residue), but if you put 13 to it, it is 130.

edit: to be clear, when I saw your number I could tell, following the long story above, that is a multiple of 13, in less than half of a second (no joke). Learning which numbers to 1000 are divisible by 13 and 7 helps (for 11 there is the +/- trick). I don't really know them, but if I get a high number I try cutting out mentally everything which is bigger than 7, or applying the fact that 301 is multiple of 7 (as 1001-700), so you just cut out three times from the hundreds what you cut from the units, and for 13, it helps the fact that 299 is a multiple of 13 (cut out 300 how many you can, then add 1 for each cut). Therefore, you very fast get an odd number below 300, and there you either know the "table" or do some more additions/subtractions.

Last fiddled with by LaurV on 2016-02-29 at 09:08

 Similar Threads Thread Thread Starter Forum Replies Last Post kurtulmehtap Math 25 2010-09-12 14:13 dleclair NFSNET Discussion 1 2006-03-21 05:11 Wacky NFSNET Discussion 1 2006-03-20 23:43 AntonVrba Factoring 7 2005-12-06 22:02 Jeff Gilchrist NFSNET Discussion 7 2005-02-23 19:46

All times are UTC. The time now is 07:39.

Tue Jan 18 07:39:32 UTC 2022 up 179 days, 2:08, 0 users, load averages: 1.14, 1.03, 1.10