Jaollisuus

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Nyt ei pikaisella silmäyksellä löytynyt logiikan ja lukuteorian kirjasta, mutta onko olemassa algoritmejä, joilla mielivaltaisen suuren kokonaisluvun voisi osoittaa olevan jaollinen 3:lla? Luku on siis todella niin suuri, että sen numeroiden summan määrittäminen vie äärimmäisen pitkän ajan.

Kommentit (8)

kuningas
Seuraa 
Viestejä1246
Liittynyt10.12.2007
huismjar
Nyt ei pikaisella silmäyksellä löytynyt logiikan ja lukuteorian kirjasta, mutta onko olemassa algoritmejä, joilla mielivaltaisen suuren kokonaisluvun voisi osoittaa olevan jaollinen 3:lla? Luku on siis todella niin suuri, että sen numeroiden summan määrittäminen vie äärimmäisen pitkän ajan.

Vähennä siitä 3*10exp(x), missä x mahdollsimman suuri luku.
Toista edellinen tarpeellisen monta kertaa.
Lopulta jäljelle jäävän luvun on oltava kolmella jaollinen.

(esim. 333622-> vähennä 300000.
33622 -> vähennä 30000.
3622 -> vähennä 3000.
622 -> vähennä 300.
322 -> vähennä 300.
22 -> ei jaollinen.)

War doesn't determine who's right but who's left.

There is no such thing as an atheist in a foxhole.

Vierailija
kuningas
huismjar
Nyt ei pikaisella silmäyksellä löytynyt logiikan ja lukuteorian kirjasta, mutta onko olemassa algoritmejä, joilla mielivaltaisen suuren kokonaisluvun voisi osoittaa olevan jaollinen 3:lla? Luku on siis todella niin suuri, että sen numeroiden summan määrittäminen vie äärimmäisen pitkän ajan.



Vähennä siitä 3*10exp(x), missä x mahdollsimman suuri luku.
Toista edellinen tarpeellisen monta kertaa.
Lopulta jäljelle jäävän luvun on oltava kolmella jaollinen.

(esim. 333622-> vähennä 300000.
33622 -> vähennä 30000.
3622 -> vähennä 3000.
622 -> vähennä 300.
322 -> vähennä 300.
22 -> ei jaollinen.)

Kiitän tästä. Pahoittelen noita muita topicceja, jotenkin mystisesti onnistuin kämmäämään aiheen lähettämisen.

Vierailija

Laske luvun numerot yhteen. Jos tulos on kolmella jaollinen, niin niin on alkuperäinen lukukin

esim.
3436776 --> 3+4+3+6+7+7+6 = 36

36 on kolmella jaollinen ja niin on alkuperäinen lukukin

P.S: Kyllähän tuossa aiemmin sanottiin jo yksi ratkaisutapa, mutta ajattelin pistää tämänkin

JAM
Seuraa 
Viestejä192
Liittynyt5.4.2006

Egen esittämä klassinen tapa taitaa olla nopeampi (useampaan kertaan sovellettuna) kuin kuninkaan vähennyslaskumenetelmä.
Pitäisi tietää, millä tavalla tietokoneen muistissa sitten on talletettuna tämä suuri kokonaisluku ja millä tavalla on ohjelmoitu näitä valtavan pitkiä lukuja koskevat laskutoimitukset? Onko luku talletettu binäärisenä vai 10-järjestelmän lukuna? Jos binäärisenä niin mikä silloin on jaollisuusssääntö? Olisiko sama kuin 11:n jaollisuussääntö kymmenjärjestelmässä?

Salausalgoritmeissa käytetyissä luvuissa samoinkuin maailmankaikkeuden hiukkasten lukumäärässä on 'vain' kymmeniä numeroita ja suurimmissa tunnetuissa alkuluvuissa on miljoonia numeroita. Onko nyt kyseessä vielä suuremmat luvut?

Vierailija
JAM
Onko luku talletettu binäärisenä vai 10-järjestelmän lukuna?

Kaikki on tietokoneessa bitteinä.
Jos binäärisenä niin mikä silloin on jaollisuusssääntö?

Joko ihmisen kehittämä algoritmi tietylle jakajalle tai sitten vain kokeillaan, koska tietokoneissa tuota laskentakapasiteettia ja mielenkiintoa tehdä se riittää enemmän kuin ihmisessä

JAM
Seuraa 
Viestejä192
Liittynyt5.4.2006
Kaikki on tietokoneessa bitteinä.

Kaikki on tietenkin bitteinä, ja tietokone osaa laskea vain 1+1 = 0 ja 1 muistiin

Luku voidaan kuitenkin tallettaa monella tavalla bitteinä. Esimerkiksi tallennetaan luku 13 bittijonona 1101 tai siten, että 1 (0001) on yhdessä muistipaikassa ja 3 (0011) toisessa muistipaikassa. Jälkimmäistä tapaa tarvitaan esimerkiksi, kun pitää tulostaa '13'.

Vierailija
JAM
Luku voidaan kuitenkin tallettaa monella tavalla bitteinä. Esimerkiksi tallennetaan luku 13 bittijonona 1101 tai siten, että 1 (0001) on yhdessä muistipaikassa ja 3 (0011) toisessa muistipaikassa. Jälkimmäistä tapaa tarvitaan esimerkiksi, kun pitää tulostaa '13'.

Tällöin on kyseessä koneen bittimäärän ylitys, eli käytetään kahta muistipaikkaa tallentamaan suuri luku. Tämä ei kuitenkaan vaikuta siihen, että tietokone tallentaa kaikki luvut bitteinä.

Neutroni
Seuraa 
Viestejä26872
Liittynyt16.3.2005

Noin pikaisesti kokeillen numeroiden summasääntö toimii heksadesimaaliluvuillakin. Lukuteoriassa ehkä on jotain korkampitasoisia sääntöjä, mutta kyllä tuo summasääntö toimii käytännössä. Jos luku mahtuu nykyaikaisen tietokoneen muistiin, kone pystyy laskemaan sen numeroiden summan verraten nopeasti.

Ilmeisesti tuo on laajennettavissa pidemmillekin luvuille, ainakin 256-kantaan. Jos luku on binäärinen, prosessorin kykyjä hyödyntänee tehokkaimmin summaamalla 32 bittisiä sanoja. Summalle riittää 96 bittiä aivan varmasti, vaikka koneessasi olisi kiinni kaikki koskaan valmistetut kovalevyt ja puolijohdemuistit.

Uusimmat

Suosituimmat