Nu skall vi ägna oss lite siffermagi. De flesta av er känner förstås redan till det här, men för ett fåtal är detta förstås nytt.
Att se om något är jämnt delbart med två är förstås mycket enkelt – alla jämna tal är delbara med två. Det är för lite större tal dock lite svårare att rakt av se om ett tal är jämnt delbart med tre. Är t ex 951 jämnt delbart med tre?
Det finns en mycket enkel metod för att fastställa detta. Av siffermagiskäl så fungerar det i ett bas10-system som så att man kan summera de individuella siffrorna i ett tal, och om summan av dessa är jämnt delbart med tre är även det ursprungliga talet jämnt delbart med tre.
Exempel: 9+5+1=15. 15 är jämnt delbart med tre, alltså är 951 jämnt delbart med tre. En kontroll: 951/3=317.
Metoden är förstås rekursiv. Vet man inte om det resulterande talet är jämnt delbart med tre är det bara att upprepa. Om man nu inte kunde treans multiplikationstabell så är 1+5=6, och alltså är 15 jämnt delbart med tre eftersom 6 är jämnt delbart med 3. Liksom 51 är det.
Så en snabb kontroll av rubrikens stora tal 1981621911376222317 ger direkt att talet är jämnt delbart med tre. 1+9+8+1+6+2+1+9+1+1+3+7+6+2+2+2+3+1+7=72. Och 7+2=9 och 9 är jämnt delbart med tre. Att verifiera detta är lite svårare i de flesta räknare som gärna vill avrunda tal av den här storleken. Men 3^8=6251. 1981621911376222317/6251=317008784414689, dvs 1981621911376222317 är jämnt delbart med tre eftersom 6251 är en faktor av treor.
Är detta då värdelöst vetande och meningslös siffermagi? Naturligtvis inte. När det handlar om primtalsfaktorisering och att avgöra om väldigt stora tal är primtal så kan man på detta sätt eliminera vart sjätte tal som alltså är jämnt delbart med tre. Naturligtvis är egentligen vart tredje tal jämnt delbart med tre, men vart annat tal som är jämnt delbart med tre är också ett jämnt tal och därmed snabbare att identifiera som ej primtal den vägen. Det går alltså rätt snabbt att eliminera 1981621911376222317, 1981621911376222318 (jämnt tal),1981621911376222320 (även jämnt delbart med två, tre och fem),1981621911376222322,1981621911376222323 (jämnt delbart med tre), 1981621911376222324 (jämnt tal), 1981621911376222325 (jämnt delbart med 5) och 1981621911376222326 (jämnt delbart med två och tre) som ej primtal. Kvarvarande tal, dvs 1981621911376222319 kräver antagligen lite mer datorkraft och är åtminstone inte jämnt delbart med 2, 3 eller 5.
Att fastställa om något är ett primtal eller ej har exempelvis tillämpningar inom kryptoteknik, exempelvis vid genereringen av en kryptonyckel eller vid fåfänga försök att knäcka moderna krypton.
Tillägg: Om det inte framgick så går förstås alla tal som slutar på 5 eller 0 också direkt bort som primtal eftersom de är jämnt delbara med primtalet 5.
Relaterat, så kan man göra motsvarande siffermagi med delbarhet med nio (9) även om nio inte är ett primtal, utan 9=3*3. Regeln här är att om summan av siffrorna i talet är jämnt delbart med nio så är även hela talet jämnt delbart med nio. Exempel: 144207891 är jämnt delbart med nio, eftersom 1+4+4+2+0+7+8+9+1=36 och 3+6=9. Kontroll: 144207891/9=16023099.
22 kommentarer
Snyggt. Glöm inte heller att alla tal med 5 går bort också
Kan tipsa om följande tillkännagivande från PrimeGrid om ett 200700 siffror långt tvillingprimtal, se: http://www.primegrid.com/forum_thread.php?id=3874
http://primes.utm.edu/primes/lists/all.txt
Och vill du leka med problem som detta (och upprätthålla din programmeringskompetens nu när du bloggar och klappar får hela dagarna) kan jag tipsa om project euler som är ett lekfullt sätt att få anledning att pyssla med matematik och programmering på fritiden.
http://projecteuler.net/
"De flesta av er känner förstås redan till det här, men för ett fåtal är detta förstås nytt."
Precis så är det.
Kan också tipsa om wolfram om man behöver få fram faktoriseringar snabbt och enkelt
http://www.wolframalpha.com/input/?i=1981621911376222319
/stud
Om man vill ha en snabb hum om huruvida ett stort tal är ett primtal eller ej skulle jag dock nog hellre rekommendera Fermats lilla sats i stället för att faktiskt försöka hitta alla primfaktorer.
Erik, det räcker att hitta en enda faktor för att kunna avfärda ett tal som icke-primtal, ovan visar jag på 2,3 och 5, med vilka man täcker in ca 85% och kan avfärda ca 85% av alla stora tal omgående med i värsta fall penna och papper.
Att t ex testa 2^1981621911376222317 kräver en dator med speciell mjukvara, medan man direkt kan avfärda 1981621911376222317 som icke primtal via enkel addition.
Kul med ett helt oväntat men väldigt intressant inlägg!
Hmm, är inte det du beskriver det som generaliseras i 'Erathostenes sil´?
Kul! En av uppgifterna på min första mattetenta var just att bevisa delat-med-tre-tricket. Tror inte jag fick ihop ett vattentätt bevis…
Tack för en beroendeframkallande blogg!
Nja.
Hej Lars,
Om du söker uppslag för att blogga om så kan du få ett tips.
Det debatteras flitigt om att man vill skilja (s) och LO åt, för att dels höja medlemstalet i fackföreningarna och dels höja antalet (s)-röstare. Men hur har man tänkt göra med det ekonomiska stödet från LO? Skall det fortsätta som vanligt eller skall det vara upp till varje fackförbund alla själva avgöra?
Alternativt slopas helt? Det är inte så länge sedan alla LO-medlemmar var kollektivt anslutna till det socialdemokratiska partiet, mot nästan allas vilja. Jag tycker att man bör gå ut och deklarera detta i god tid före valet om man vill vinna tillbaka alla som ev. kommer att fly till (v) och SD.
Jag vet att du inte ofta bloggar om inrikespolitik, men jag tror att valet 2014 kan bli en rysare för många partier, och väl värt uppmärksamma redan innan man avsatt Juholt.
Håkan Larsson
Den här boken borde översättas till svenska och vara obligatorisk i matematikundervisningen från mellanstadiet och uppåt. Beskriver hur du kan räkna nästan vilka tal som helst i huvudet, och olika tekniker, varav ingen är särskilt avancerad men fungerar mycket bra. Helt enligt principen enklast blir oftast bäst. 150 spänn på adlibris.
Titel: Think Like a Maths Genius
Undertitel: The Art of Calculating in Your Head
Författare: Arthur Benjaman
Författare: Michael Shermer
Förlag: Souvenir Press Ltd
Bandtyp: Häftad, Pocket
Språk: Engelska
Utgiven: 200610
Antal sidor: 304
ISBN10: 0285637762
ISBN13: 9780285637764
https://www.adlibris.com/se/product.aspx?isbn=0285637762
Coolt, det visste jag inte.
Cornu, 14:31
Menar du att testa 2^1981621911376222317 efter primtalsfaktorer? Men det är ju redan givet, faktorerna är en radda tvåor. Därav följer att talet inte är delbart med 3, 5, 7 eller något annat primtal (annat än två).
Kan du inte skriva mer om konflikten i Syrien istället? Även om det inte berör peak oil direkt, skulle en större konflikt i den regionen riskera att leda till kraftiga rörelser i oljepriset. Och försvarskopplingen är väl också ganska tydlig.
/Civilekonom, men inte övertygad
En liten detalj bara:
3⁸ = 6561 och inte 6251
Civilekonom 06:55, ni läser väl ingen matte på ekonomutbildningarna, det räcker ju med olika varianter av plus, minus och procent för att bli ekonom, så jag förlåter dig.
2^1981621911376222317 är en av de operationer som man behöver göra för att i enlighet med Fermats lilla sats testa om 1981621911376222317 är ett primtal. Det visade på beräkningsbarheten i det hela. Naturligtvis är 2^X aldrig ett primtal, men det var alltså inte det som det handlade om.
Om Fermats lilla sats kan du läsa på http://sv.wikipedia.org/wiki/Fermats_lilla_sats, men via metoderna i inlägget kan man alltså eliminera ca 85% av alla tal så man inte behöver köra tyngre beräkningar när man letar primtal.
1 2 3 4 5 6 7 8 9 10.
Vänta, hold the applause..
11!
Jag vet, lite smartass men än sen då?
Cornu 10:40
Okej, tack, med detta förtydligande förstår jag vad du försökte säga. Men om du vill ha en någorlunda säker indikation kring ett allmänt tals primalitet tar det ett bra tag att eliminera primtalsfaktorer med "talmagi", medan Fermats lilla sats ger en betydligt bättre övertygelse på kort tid.
Du hävdar att man behöver speciell mjukvara för detta — min uppfattning är att mjukvaran finns som en del av public key-kryptografi, så nästan varje linux/mac-användare har redan mjukvaran installerad i och med ssh out-of-the box.
Vidare handlar Fermats metod om huruvida a^k är kongruent med a mod k, och man behöver alltså inte räkna ut talet a^k i fullständig representation. Genom klipsk återanvändning av deluträkningar av termer som tillsammans summerar till k (som kan erhållas till exempel genom att representera k binärt) kan det hela bli ganska beräkningseffektivt.
Speciell programvara: Ja, beroende på vad man menar. Å andra sidan ger googling på "ruby fermat primality test" kod att köra i ruby, som också finns som standard på många datorer (t.ex. de senare årens versioner av Mac OS X).
Jag tror att det jag egentligen störde mig på var att de ofullständiga meningar med mycket underförstått innehåll som är lämpliga för att beskriva saker som beskrivs i naturligt språk (såsom politiska ståndpunkter, neosurvivalism eller frustration över bobubbla) lätt leder till saker som inte riktigt har en exakt innebörd, när det gäller sådant som bättre uttrycks i formellt språk.
Men men, gillar fortfarande din blogg, och att du tar dig tid att besvara även sådana som uppenbarligen inte alls tolkar det du säger mellan raderna korrekt.
/Civilekonom, men inte övertygad
Vill bara tipsa om, att om man ska räkna ut siffersumman av 1981621911376222317 för att kolla om den och därmed talet är delbar(t) med 3, så kan man lugnt hoppa över siffrorna 3,6 och 9 för att snabba upp additionen. Och även sekvenserna 81, 21 och 222 om man känner för det.