mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-02-24, 05:13   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

17568 Posts
Default 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
MattcAnderson is offline   Reply With Quote
Old 2016-02-24, 05:28   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

632410 Posts
Default

TF to ~60 appears to be adequate.
retina is online now   Reply With Quote
Old 2016-02-24, 06:07   #3
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·29·167 Posts
Lightbulb 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!)
Batalov is offline   Reply With Quote
Old 2016-02-24, 06:09   #4
S485122
 
S485122's Avatar
 
"Jacob"
Sep 2006
Brussels, Belgium

6EE16 Posts
Default

.

Last fiddled with by S485122 on 2016-02-24 at 06:12 Reason: Sergey was quicker and much more didactic
S485122 is offline   Reply With Quote
Old 2016-02-29, 08:57   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

232038 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factorization on 2^p +1 kurtulmehtap Math 25 2010-09-12 14:13
Factorization of 7,254+ dleclair NFSNET Discussion 1 2006-03-21 05:11
Factorization of 11,212+ Wacky NFSNET Discussion 1 2006-03-20 23:43
160 digit factor found of 366 digit (PRP-1) AntonVrba Factoring 7 2005-12-06 22:02
Factorization of 5,307- Jeff Gilchrist NFSNET Discussion 7 2005-02-23 19:46

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


Tue Jan 18 07:49:32 UTC 2022 up 179 days, 2:18, 0 users, load averages: 1.05, 1.04, 1.06

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔