Forum » Znanost in tehnologija » Digitalna evolucija
Digitalna evolucija
Thomas ::
Greš gledat vse subkvadrate 4x4. Vsak je bitni niz, v bistvu. Na adresi, ki jo predstavlja, nekje že kar vnaprej piše, koliko praštevil je v tem subkvadratu ...
Oziroma ... sploh ne delaš s kvadrati, pač pa z vsemi izpisanimi subnizi.
Hm ...
Oziroma ... sploh ne delaš s kvadrati, pač pa z vsemi izpisanimi subnizi.
Hm ...
snow ::
Ja ampak pol maš nize enakih dolžin predsestavljene?
Prvo 'poskeniraš' po takih nizih malo...če zgleda obetavno gremo pregledovat večje nize.
Mogoče res nebi blo slabo subkvadrate!!
Prvo 'poskeniraš' po takih nizih malo...če zgleda obetavno gremo pregledovat večje nize.
Mogoče res nebi blo slabo subkvadrate!!
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Tole sicer verjetno precej omeji nabor rešitev, ampak kaj če začneš na sredini, poiščeš "optimalno" (v EA duhu, da ne bo pomote) rešitev, povečaš N za dva, poiščeš optimalen rob, povečaš N za 2, ...
Otroška radovednost - gonilo napredka.
snow ::
Tako zadevo bi se lahko najbrž že bruteforce šel.
Hm ja omejimo se tukaj najbrž, lepo pa je če ima EA dost odprte roke, pa naj on grunta!
Hm ja omejimo se tukaj najbrž, lepo pa je če ima EA dost odprte roke, pa naj on grunta!
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Se bolj ali manj strinjam. Moram priznati, da trenutno bolj ali manj nekritično valim ideje. 
Sam bi verjetno obtežil sode in lihe števke v rešitvah še pred iskanjem praštevil, če si pogledamo statistiko do 8:
* dokazano optimalna rešitev
Kjer je več enakovrednih rešitev, sem vzel tisto z največ sodimi števili.
Sam bi verjetno obtežil sode in lihe števke v rešitvah še pred iskanjem praštevil, če si pogledamo statistiko do 8:
| N | n(sodih) | f(sodih) |
|---|---|---|
| 2* | 1 | 0,25 |
| 3* | 1 | 0,11 |
| 4* | 3 | 0,19 |
| 5 | 4 | 0,16 |
| 6 | 5 | 0,14 |
| 7 | 8 | 0,13 |
| 8 | 7 | 0,11 |
* dokazano optimalna rešitev
Kjer je več enakovrednih rešitev, sem vzel tisto z največ sodimi števili.
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
snow ::
Jaz sem pa študiral, da mogoče nebi blo slabo naredit statistiko cifer, ki se pojavljajo v praštavilih.
OwcA
Hm, kaj to si potem ti že reševal nekaj al kako? Random generirana polja? Kak check za praštevila si pa mel?
No potem lahko damo EA-ju da bolj verjetno naredi neko liho cifro na polju, kot pa sodo, ampak verjetno bi dost hitro tudi sam ven vrgel takšno rešitev.
Jaz zdej gruntam po najhitrejšem checkerju... še kar :)
OwcA
Hm, kaj to si potem ti že reševal nekaj al kako? Random generirana polja? Kak check za praštevila si pa mel?
No potem lahko damo EA-ju da bolj verjetno naredi neko liho cifro na polju, kot pa sodo, ampak verjetno bi dost hitro tudi sam ven vrgel takšno rešitev.
Jaz zdej gruntam po najhitrejšem checkerju... še kar :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Tole me je tudi nekaj matralo... kolk stringov posamezne dolžine mamo v polju 20x20:
n |freq| sum freq|
2 2964 2964
3 2736 5700
4 2516 8216
5 2304 10520
6 2100 12620
7 1904 14524
8 1716 16240
9 1536 17776
10 1364 19140
11 1200 20340
12 1044 21384
13 896 22280
14 756 23036
15 624 23660
16 500 24160
17 384 24544
18 276 24820
19 176 24996
20 84 25080
Se pravi tam do stringov vključno z 11 mamo 80% vseh stringov. Pa še praštevila so tam bolj pogosta na krajših dolžinah a ne?
Ni mi pa jasno 'iz kolk strani' gledamo stringe dolžine 1.
A jih je skupaj 20*20 ali 8*20*20 :)? Verjetno prvo... bom vprašal tam.
n |freq| sum freq|
2 2964 2964
3 2736 5700
4 2516 8216
5 2304 10520
6 2100 12620
7 1904 14524
8 1716 16240
9 1536 17776
10 1364 19140
11 1200 20340
12 1044 21384
13 896 22280
14 756 23036
15 624 23660
16 500 24160
17 384 24544
18 276 24820
19 176 24996
20 84 25080
Se pravi tam do stringov vključno z 11 mamo 80% vseh stringov. Pa še praštevila so tam bolj pogosta na krajših dolžinah a ne?
Ni mi pa jasno 'iz kolk strani' gledamo stringe dolžine 1.
A jih je skupaj 20*20 ali 8*20*20 :)? Verjetno prvo... bom vprašal tam.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
To je bistveno vprašanje, ja. Če stringe dolžine 1 šteje1 krat ali osemkrat.
Nekaj se mi dozdeva, da je optimum sestavljen iz dveh barv. Barve 7 in barve 3. Ker 7 in 3 dajeta mnogo praštevil.
3,7,37,73,337,373,733,773,3373,3733,7333,33377,33773,37337, 77377,77773,333337,333737,373777,377737,733333,733373,
737773,773777,777373,777737,3333373,3333773,3337333,3337777,
3377377,3733333,3773377,3773773,3777377
Težko verjamem, da v optimalno konfiguracijo 7 in 3 lahko uštukaš kakšno drugo cifro tako, da imaš praštevil še več. Izključujem pa tudi (še) ne.
Ampak zgleda je problem simpler, kot izgleda na prvi pogled.
Nekaj se mi dozdeva, da je optimum sestavljen iz dveh barv. Barve 7 in barve 3. Ker 7 in 3 dajeta mnogo praštevil.
3,7,37,73,337,373,733,773,3373,3733,7333,33377,33773,37337, 77377,77773,333337,333737,373777,377737,733333,733373,
737773,773777,777373,777737,3333373,3333773,3337333,3337777,
3377377,3733333,3773377,3773773,3777377
Težko verjamem, da v optimalno konfiguracijo 7 in 3 lahko uštukaš kakšno drugo cifro tako, da imaš praštevil še več. Izključujem pa tudi (še) ne.
Ampak zgleda je problem simpler, kot izgleda na prvi pogled.
snow ::
Kekci tak butasto napišejo navodilo.
Zdej sem zvedel da se šteje število različnih praštevil. To pa mal spremeni zadeve.
Lp iz Rogle :)
Zdej sem zvedel da se šteje število različnih praštevil. To pa mal spremeni zadeve.
Lp iz Rogle :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Hm :) Aja? No fajn za nas pol a?
Zakaj je v dead endu?
Zakaj je v dead endu?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Ampak izvoren problem bi pa bil zanimiv. Me kar malo mika, da se poskusil v tem.
Te potem tudi Mathworld citira?
Te potem tudi Mathworld citira?
Otroška radovednost - gonilo napredka.
snow ::
Thomas
A je tolk mal praštevil, da bi lahko dejansko z neko pametno funkcijo kar bolj kot ne vsa postavil v polje... al kako?
Rabim pač tam jim pametno argumentirat, da se gremo onega, ki šteje VSA praštevila.. tisto bi znalo bit bolj zanimivo tudi meni :)
A je tolk mal praštevil, da bi lahko dejansko z neko pametno funkcijo kar bolj kot ne vsa postavil v polje... al kako?
Rabim pač tam jim pametno argumentirat, da se gremo onega, ki šteje VSA praštevila.. tisto bi znalo bit bolj zanimivo tudi meni :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Na PTSP so pa prišli do 692.
No saj jaz sem tja do ene 670 prišel na eni poti... pol pa sem odkril eno drugo med tistimi tridesetimi mesti. In je šlo še way down. Bom pa dal moj rezultat v sredo gor, ko se zadeva tudi zakjuči... če ne bo kdo boljšega ustvaril do takrat
No saj jaz sem tja do ene 670 prišel na eni poti... pol pa sem odkril eno drugo med tistimi tridesetimi mesti. In je šlo še way down. Bom pa dal moj rezultat v sredo gor, ko se zadeva tudi zakjuči... če ne bo kdo boljšega ustvaril do takrat
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
Ne. Problem se zvede na najti tak 20 dolg niz, ki vsebuje maksimalno praštevilskih substringov. To ni pretežko. Saj glavno vlogo igrajo majhna praštevila. Nikakor ni 10^20 možnosti, pač pa BISTVENO manj.
Tako ustoličiš recimo TOP 10 stringov. Zdaj moraš samo še ugotoviti, katera permutacija s ponavljanjem tistih tazgornjih, da zanesljivo več praštevil, kot katerakoli druga. Morda je dovolj, da naložiš 20 teh 20 dolgih stringov enega na drugega v kvadrat. Morda moraš zraven dodati še tadrugega ... kaj dosti dlje pa to ne gre.
Ni treba, da pravzaprav šteješ, koliko teh praštevil je, glavno da dokažeš (pri sebi), da je menjanje za drug 20 dolg string kjerkoli v tabeli zanesljivo zaman. Da nujno več podere, kot da novih. Pa maš.
p.s.
Upaj snow, da bo Siol v sredo deloval!
Tako ustoličiš recimo TOP 10 stringov. Zdaj moraš samo še ugotoviti, katera permutacija s ponavljanjem tistih tazgornjih, da zanesljivo več praštevil, kot katerakoli druga. Morda je dovolj, da naložiš 20 teh 20 dolgih stringov enega na drugega v kvadrat. Morda moraš zraven dodati še tadrugega ... kaj dosti dlje pa to ne gre.
Ni treba, da pravzaprav šteješ, koliko teh praštevil je, glavno da dokažeš (pri sebi), da je menjanje za drug 20 dolg string kjerkoli v tabeli zanesljivo zaman. Da nujno več podere, kot da novih. Pa maš.
p.s.
Upaj snow, da bo Siol v sredo deloval!
Thomas ::
Zdej tko. Če iščemo RAZLIČNA pratevila, potem je skoraj zagotovo optimium zelo blizu, če našopaš TOP 20 stringov v kvadrat.
Če pa iščemo samo NAJVEČ praštevil v tem kvadratu, našopaš taglavnega 20 krat.
Si blizu, v vsakem primeru. Lahko pa mau poevoluiraš, to pa tudi. Ni treba dost.
Če pa iščemo samo NAJVEČ praštevil v tem kvadratu, našopaš taglavnega 20 krat.
Si blizu, v vsakem primeru. Lahko pa mau poevoluiraš, to pa tudi. Ni treba dost.
Zgodovina sprememb…
- spremenil: Thomas ()
snow ::
Hm.
Misliš da bi tole izdelovanje podstringov res prineslo zelo zelo dobro rešitev? No treba je pač imeti najboljšo rešitev med vsemi :)
Ideja mi je všeč... samo zgleda preveč simpl :)
Bi blo treba probat na manjših kvadratih, kjer so dokazane dobre rešitve.
OwcA a ti si one rešitve za one kvadrate do 4 kje iz neta pobral ali si sam naredu kak solver?
Misliš da bi tole izdelovanje podstringov res prineslo zelo zelo dobro rešitev? No treba je pač imeti najboljšo rešitev med vsemi :)
Ideja mi je všeč... samo zgleda preveč simpl :)
Bi blo treba probat na manjših kvadratih, kjer so dokazane dobre rešitve.
OwcA a ti si one rešitve za one kvadrate do 4 kje iz neta pobral ali si sam naredu kak solver?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Mathworld in tisti link, ki si ga ti dal.
Otroška radovednost - gonilo napredka.
Zgodovina sprememb…
- spremenilo: OwcA ()
snow ::
Copy paste iz grupe:
The contest votes are now over !
The contest will officially start on the 1st of July and will be about
"Primes in a square" !
----------------------------------------------------------------
Given n, fill the n*n square-grid with digits 0..9 such that there are
as many primes as possible among the number formed from consecutive
digits horizontally or vertically.
http://www.primepuzzles.net/puzzles/puz...
Extending upto N=20 could be an interesting challenge.
You can replace primes with squares, or any other sequence of integers
that does not turn the problem trivial.
----------------------------------------------------------------
We'll take the Gordon Lee original problem as part 1:
1) the primes must be DISTINCT
2) the numbers can be formed horizontally, vertically or DIAGONALLY
As usual, there will be a second part, which is not yet completely
defined.
Here are some possible extensions:
- primes -> squares/cubes
- fill a m*n rectangle
- fill a n*n*n cube
- fill the n*n grid with values 1 to n*n
Please share your opinions/ideas, I'll take the final decision.
My current main problem is that testing grids takes too much time on
the server.
For example, there are around 20,000 numbers to test on a 20x20 grid,
and our PHP server has only a slow multiprecision routine in PHP
(BcMath + CryptRSA routine).
On the server, the script can only run during 6 seconds.
http://faq.1and1.com/scripting_language...
Maybe someone could provide me scripts in PHP, Perl, Python or Ruby to
QUICKLY check the primality of a number upto 20 digits ?
The two other ways are:
- using a webservice (a program is hosted on another computer, and an
URL is requested, returning the number of primes in a grid)
- using a mail bot. When a solution is submitted, a mail is sent, and
a distant computer checks the mail and counts the number of primes. In
this case, the scores are not updated in real-time.
I'm open to all propositions.
Hm.. so lets play?
The contest votes are now over !
The contest will officially start on the 1st of July and will be about
"Primes in a square" !
----------------------------------------------------------------
Given n, fill the n*n square-grid with digits 0..9 such that there are
as many primes as possible among the number formed from consecutive
digits horizontally or vertically.
http://www.primepuzzles.net/puzzles/puz...
Extending upto N=20 could be an interesting challenge.
You can replace primes with squares, or any other sequence of integers
that does not turn the problem trivial.
----------------------------------------------------------------
We'll take the Gordon Lee original problem as part 1:
1) the primes must be DISTINCT
2) the numbers can be formed horizontally, vertically or DIAGONALLY
As usual, there will be a second part, which is not yet completely
defined.
Here are some possible extensions:
- primes -> squares/cubes
- fill a m*n rectangle
- fill a n*n*n cube
- fill the n*n grid with values 1 to n*n
Please share your opinions/ideas, I'll take the final decision.
My current main problem is that testing grids takes too much time on
the server.
For example, there are around 20,000 numbers to test on a 20x20 grid,
and our PHP server has only a slow multiprecision routine in PHP
(BcMath + CryptRSA routine).
On the server, the script can only run during 6 seconds.
http://faq.1and1.com/scripting_language...
Maybe someone could provide me scripts in PHP, Perl, Python or Ruby to
QUICKLY check the primality of a number upto 20 digits ?
The two other ways are:
- using a webservice (a program is hosted on another computer, and an
URL is requested, returning the number of primes in a grid)
- using a mail bot. When a solution is submitted, a mail is sent, and
a distant computer checks the mail and counts the number of primes. In
this case, the scores are not updated in real-time.
I'm open to all propositions.
Hm.. so lets play?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Thomas ::
> 2) the numbers can be formed horizontally, vertically or DIAGONALLY
A v obe smeri?
Tudi dolžine 1?
A v obe smeri?
Tudi dolžine 1?
snow ::
Distinct. Tak da je vseeno.
Si lahko mislimo da v eno smer.
Hm.. bom mal premisljeval danes zvecer mogoce se kaj sprogramiral.
Si lahko mislimo da v eno smer.
Hm.. bom mal premisljeval danes zvecer mogoce se kaj sprogramiral.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Na 20*20 polju maš 400 cifer dolžine 1.
Zdej lahko maš največ 4 (2,3,5,7) praštevil gor. In je vseeno iz katere 'smeri' jih gledaš, ker tako ali tako lahko šteješ vsako samo enkrat!
Sem studiral v kakšno tabelo spravit tale preštevila.
Kakšna je razlika v hitrosti (če je) med tabelo tipa int in short.
Ali bi mogoče z malo računanja spravil 1 praštevilo na bit in bi lahko imel en velikosti razred več praštevil... ali bi bila to bolj izguba časa?
Kak si pa že porabljena praštevila označevat, da dobimo score? Sploh ona velika... nad 10 mest.
Zdej lahko maš največ 4 (2,3,5,7) praštevil gor. In je vseeno iz katere 'smeri' jih gledaš, ker tako ali tako lahko šteješ vsako samo enkrat!
Sem studiral v kakšno tabelo spravit tale preštevila.
Kakšna je razlika v hitrosti (če je) med tabelo tipa int in short.
Ali bi mogoče z malo računanja spravil 1 praštevilo na bit in bi lahko imel en velikosti razred več praštevil... ali bi bila to bolj izguba časa?
Kak si pa že porabljena praštevila označevat, da dobimo score? Sploh ona velika... nad 10 mest.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Kakšna je razlika v hitrosti (če je) med tabelo tipa int in short.
Samo v velikosti. Če že misliš tako optimizirati, potem je že char več kot dovolj.
Ali bi mogoče z malo računanja spravil 1 praštevilo na bit in bi lahko imel en velikosti razred več praštevil... ali bi bila to bolj izguba časa?
A to misliš tako:
2->00
3->01
5->11
7->10
(namenoma ne tečejo v binarnem zapisu po velikosti, ampak upoštevajo pravilo en bit flip na prehod)?
V vsakem primeru se mi zdi to preveč kompliciranja.
Kak si pa že porabljena praštevila označevat, da dobimo score? Sploh ona velika... nad 10 mest.
A je sploh treba označevati? Greš sistematično od leve proti desni, od zgoraj navzdol, od najkrajšega niza do najdaljšega za obe dimenziji.
Otroška radovednost - gonilo napredka.
snow ::
Glede binary sem mislu nekak takole:
V enem intu imamo postavljene bite na 1, če je cifra praštevilo, če pa je na 0 pač ni.
Se pravi 0010101100 za (9,8,7,6,5,4,3,2,1,0), ampak pač za vse.
Ja od levo zgoraj do spodaj desno... ampak vsako praštevilo moraš štet samo enkrat. Na kak način si naj zapišem neko praštevilo, ki je dolgo ene 17 mest in da potem primerjam če sem ga že upošteval? Hm long long(64bit) to lahko drži a ne?
Je kdo že gledal kake primality checke?
V enem intu imamo postavljene bite na 1, če je cifra praštevilo, če pa je na 0 pač ni.
Se pravi 0010101100 za (9,8,7,6,5,4,3,2,1,0), ampak pač za vse.
Ja od levo zgoraj do spodaj desno... ampak vsako praštevilo moraš štet samo enkrat. Na kak način si naj zapišem neko praštevilo, ki je dolgo ene 17 mest in da potem primerjam če sem ga že upošteval? Hm long long(64bit) to lahko drži a ne?
Je kdo že gledal kake primality checke?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Zgodovina sprememb…
- spremenilo: snow ()
snow ::
2^64 < 10^20 hm :)
No 2^64 = 10^19,26
In kako naj preverjam sploh te 20 mesta števila če so praštevila?
Kak se to dela s takimi velikimi ciframi?
No 2^64 = 10^19,26
In kako naj preverjam sploh te 20 mesta števila če so praštevila?
Kak se to dela s takimi velikimi ciframi?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Sergio ::
Jaz bi napolnil n*n tabelo z 3 5 7 (randomly), pa gledal, kolk sem zadel 
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Sergio ::
Evo, stevila do milijon. Se verjetnost zracunam.
3
5
7
37
53
73
337
353
373
557
577
733
757
773
3373
3533
3557
3733
5333
5557
5573
5737
7333
7537
7573
7577
7753
7757
33353
33377
33533
33577
33757
33773
35353
35533
35537
35573
35753
37337
37357
37537
37573
53353
53377
53773
53777
55333
55337
55373
55733
57373
57557
57737
57773
73553
73757
75337
75353
75377
75533
75553
75557
75577
75773
77377
77557
77573
77773
333337
333533
333737
333757
335557
337537
353333
353557
353737
353777
355573
355753
355777
357353
357377
357733
357737
373357
373553
373753
373757
373777
375373
375533
375553
375757
375773
377353
377537
377557
377737
533353
533573
533737
533777
535333
535573
535757
537373
537773
553573
553733
553757
555337
555557
557377
557533
557537
557573
573557
573737
573757
575557
575573
575753
575777
577333
577537
577573
577757
733333
733373
733753
733757
735337
735373
735533
735557
735733
737353
737533
737537
737573
737753
737773
753353
753373
753737
753773
755333
755357
755737
757553
757577
757753
773533
773537
773777
775553
775573
775757
775777
777353
777373
777737
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Zgodovina sprememb…
- spremenil: Sergio ()
Sergio ::
1. stolpec stevilo stevil iz teh stevil dolgih i
2. stolpec stevilo prastevil iz teh stevil dolgih i
3. stolpec verjetnost zadetka da je prastevilo.
2. stolpec stevilo prastevil iz teh stevil dolgih i
3. stolpec verjetnost zadetka da je prastevilo.
3.0 3.0, p=1.0
3.0 9.0, p=0.3333333333333333
8.0 27.0, p=0.2962962962962963
14.0 81.0, p=0.1728395061728395
41.0 243.0, p=0.16872427983539096
95.0 729.0, p=0.13031550068587106
242.0 2187.0, p=0.11065386374028349
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Zgodovina sprememb…
- spremenil: Sergio ()
Thomas ::
Najprej še zdej ne vem, če velja branje z desne proti levi IN z leve proti desni. Od zgoraj dol IN od spodaj gor.
Pa ne mislim za dolžino 1, pač pa za dolžino 2, 3 ali več.
> Kak se to dela s takimi velikimi ciframi?
To se pa tk nardi:
Uskladiščiš vsa praštevila do 32 milijard. Teh je med brati dobro milijardo. Pomeni, potrošiš kakšne 4 Giga RAMota. Anyway.
Potem probaš 20 mestno število deliti z njimi. Če nobeno ne deli, maš praštevilo. Kar je verjetnost kakšne 3 promile.
Kej boljš ne gre!
Pa ne mislim za dolžino 1, pač pa za dolžino 2, 3 ali več.
> Kak se to dela s takimi velikimi ciframi?
To se pa tk nardi:
Uskladiščiš vsa praštevila do 32 milijard. Teh je med brati dobro milijardo. Pomeni, potrošiš kakšne 4 Giga RAMota. Anyway.
Potem probaš 20 mestno število deliti z njimi. Če nobeno ne deli, maš praštevilo. Kar je verjetnost kakšne 3 promile.
Kej boljš ne gre!
Zgodovina sprememb…
- spremenil: Thomas ()
Sergio ::
Thomas: kaj pa z verjetnostnimi algoritmi? Ti niso cist natancni, so pa izjemno hitri...
Mislim, da tukaj ne isces ekzaktne resitve, ampak cim boljso aprokcimacijo.
Mislim, da tukaj ne isces ekzaktne resitve, ampak cim boljso aprokcimacijo.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Sej v tem je štos. Da dobra aproksimacija je že ta, da nobenega 20 dolgega praštevila nimaš v kvadratu. Te ne zanimajo. Je isto kot probabilistični test. To je problem unega strička, ki mu ti uploadaš svoj kvadrat, da ti jih prešteje še tavelike zraven. Ti pa veš, da imaš veliko množico (IMO tisoč+) manjših.
Striček ti pa da 2 bomusa še, recimo.
Ko se dela gužva (na pamet govorim) okoli rezultata 1215, pa nekoliko našponaš svoj test tako, da poišče do 7 namesto do 6 dolga praštevila.
Striček ti pa da 2 bomusa še, recimo.
Ko se dela gužva (na pamet govorim) okoli rezultata 1215, pa nekoliko našponaš svoj test tako, da poišče do 7 namesto do 6 dolga praštevila.
Thomas ::
Kako verjetno se ti zdi, da ne boš imel največjega števila kratkih praštevil v kvadratu, pa boš manjko nadomestil s tadolgimi?
Zelo malo verjetno. Zato vse napore samo v tamala praštevila, tadolga, ki si jih pa slučajno zadel, so pa samo bonus. Drobiž, v skupnem številu.
Ja?
Zelo malo verjetno. Zato vse napore samo v tamala praštevila, tadolga, ki si jih pa slučajno zadel, so pa samo bonus. Drobiž, v skupnem številu.
Ja?
snow ::
0 3386986
1 5510645
2 4047829
3 5472472
4 4022501
5 4015732
6 4007705
7 5443074
8 3998411
9 5432190
Statistika cifer v praštevilih do 100 maljonov(100 mega rama).
Mene zanima kako za vraga naj neko 20 mestno cifro spravim v eno spremenljivko... če pa ta ne zmore tako velikih cifer. Long long drži tja do ene 17 mestnih cifer. Ma ubistvu se niti ne mislim nekaj ukvarjat s takimi velikimi ciframi, se strinjam s Thomasom da se bolj splača naštimat fitness na ta bolj kratke... tud če pogledate ono mojo statistiko zgoraj se vidi kolk je katerih cifer raznih dolžin v kvadratu 20*20.
Aha se pogovarjajo zdej da bi omejili iskanje praštevil do 2^64 (long long), oziroma celo na 2^51 zaradi nekih hitrih testov... vidi linka: link1 link2
Pa kvadrat bi naj bil malo manjši... 19x19 pravijo zaenkrat.
Gleda se pa v vse smeri ja.
Ha.. na PTSP se počasi dogaja.. pa da vidimo kako deep gremo. Upam da ne pod 652 :)
1 5510645
2 4047829
3 5472472
4 4022501
5 4015732
6 4007705
7 5443074
8 3998411
9 5432190
Statistika cifer v praštevilih do 100 maljonov(100 mega rama).
Mene zanima kako za vraga naj neko 20 mestno cifro spravim v eno spremenljivko... če pa ta ne zmore tako velikih cifer. Long long drži tja do ene 17 mestnih cifer. Ma ubistvu se niti ne mislim nekaj ukvarjat s takimi velikimi ciframi, se strinjam s Thomasom da se bolj splača naštimat fitness na ta bolj kratke... tud če pogledate ono mojo statistiko zgoraj se vidi kolk je katerih cifer raznih dolžin v kvadratu 20*20.
Aha se pogovarjajo zdej da bi omejili iskanje praštevil do 2^64 (long long), oziroma celo na 2^51 zaradi nekih hitrih testov... vidi linka: link1 link2
Pa kvadrat bi naj bil malo manjši... 19x19 pravijo zaenkrat.
Gleda se pa v vse smeri ja.
Ha.. na PTSP se počasi dogaja.. pa da vidimo kako deep gremo. Upam da ne pod 652 :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Uporabi kakšno knjižnico za delo z obsceno velikimi števili.
Otroška radovednost - gonilo napredka.
snow ::
Če oni pravijo da jih ne bodo čekiral, jih bom jaz še tolk manj :)
Zdej smo na fazi gruntanja o najhitrejšem pregledu vseh cifer. Ideje? Mislim kr direkt na kodo skoraj.
Zdej smo na fazi gruntanja o najhitrejšem pregledu vseh cifer. Ideje? Mislim kr direkt na kodo skoraj.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
snow ::
Eh bleh.. en je dal gor 648 na PTSP
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
Sergio ::
Thomas: tocno tako. Ravno zato sem sestavil kvadrat samo iz trojk, petk in sedmic .
Pobral sm vsa enomestna, potem pa po verjetnosti (ki sem jo tudi specificiral zgoraj) naprej :)
IMHO bi jaz samo v neskoncnost generiral kvadrate pa stel prastevila do take dolzine, kolikor bi mi CPU se dopustil.
.Pobral sm vsa enomestna, potem pa po verjetnosti (ki sem jo tudi specificiral zgoraj) naprej :)
IMHO bi jaz samo v neskoncnost generiral kvadrate pa stel prastevila do take dolzine, kolikor bi mi CPU se dopustil.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Sergio ::
Kvadrat 19x19.
1. vrstica 337337337...
2. vrstica 373373373...
3. vrstica 733733733...
V kvadratu 19x19 je to
- 361 prastevil dolzine 1
- 1156 prastevil dolzine 3
Ostalih sploh gledal nisem. Je pa to polna mreza glede na prastevila dolzine 1 in 3, v obe smeri. Hudo ane? :)))
1. vrstica 337337337...
2. vrstica 373373373...
3. vrstica 733733733...
V kvadratu 19x19 je to
- 361 prastevil dolzine 1
- 1156 prastevil dolzine 3
Ostalih sploh gledal nisem. Je pa to polna mreza glede na prastevila dolzine 1 in 3, v obe smeri. Hudo ane? :)))
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Ja, je. Se pravi do števila 2000 praštevil se verjetno kar pride. Glavnina pri majhnih, seveda.
Sergio ::
Ja, OK. Ampak kar mi ne gre v glavo je (ob pogoju, da imas prav, mislm da imas IMHO) je pa smieslnost tega problema.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Thomas ::
Samo prestiž. Ni enostavno ugotoviti, kateri izmed 10^300 možnih kvadratov je najbolj natrpan s praštevili.
Sergio ::
Kaj pol, a se prijavimo? :)
Jaz mam eno lustno idejico kako v precej kratkem casu prit do precej dobre resitve... Pol pa dam kodo, pa lahko naprej delate.
Jaz mam eno lustno idejico kako v precej kratkem casu prit do precej dobre resitve... Pol pa dam kodo, pa lahko naprej delate.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.
če usoda ustavi mu korak,
on se ji zoperstavi.
Phil ::
A se zdaj šteje število vseh praštevil ali število različnih praštevil?
Malo igranja z EA (poganjanje < 10minut):
štetje v vse smeri + štetje vseh praštevil + upoštevanje 6 mestnih cifer
primes: 6332 (tukaj vsako enomestno praštevilo šteješ 8x ???)
3 3 7 9 5 3 3 3 3 3 7 7 5 7 2 7 3 7 4
7 9 7 0 0 5 1 7 9 7 1 3 9 9 1 3 7 5 7
3 0 1 7 3 1 3 6 1 3 3 7 0 1 2 2 3 1 7
3 1 1 0 1 3 3 7 3 3 7 6 9 5 8 5 0 6 7
7 7 3 9 3 3 4 2 6 1 7 3 1 2 2 3 7 3 5
3 7 3 7 1 2 6 9 1 7 9 5 9 7 9 7 5 6 7
3 1 1 3 7 6 2 4 3 7 3 3 7 3 5 9 0 7 9
7 7 9 3 4 1 2 3 1 1 1 7 6 0 2 1 0 2 3
9 1 6 2 3 3 7 0 1 9 9 7 7 9 3 1 9 4 3
7 1 1 7 0 7 7 9 7 1 3 3 3 3 7 3 1 7 3
7 4 7 1 8 7 5 9 2 9 1 5 2 1 3 9 0 1 7
2 3 5 3 9 5 4 7 9 6 1 7 7 5 1 9 3 7 2
3 0 1 7 0 9 7 1 7 7 5 9 1 1 3 5 7 1 3
3 7 7 3 5 4 3 3 8 3 3 7 7 7 5 2 1 1 5
7 1 3 9 3 0 3 5 5 9 1 7 3 7 7 5 3 4 7
3 1 7 3 9 7 7 3 0 0 3 3 3 7 1 5 0 3 3
3 7 7 5 7 7 3 3 3 1 1 4 7 9 3 0 3 1 5
7 3 3 4 9 3 8 7 1 1 3 1 3 3 7 1 0 3 7
3 3 3 7 7 7 3 3 3 2 7 7 2 7 3 3 2 5 7
štetje v vse smeri + štetje različnih praštevil + upoštevanje 6 mestnih cifer
primes: 959
1 5 3 9 1 4 8 9 5 8 7 3 3 9 1 7 0 2 7
3 5 0 4 1 4 6 4 4 1 7 8 8 8 9 0 1 0 9
8 3 1 0 9 2 7 3 7 5 9 1 2 9 0 9 4 1 3
2 1 6 5 4 9 5 9 3 5 5 6 1 8 7 3 4 4 1
5 9 4 5 1 7 9 7 3 1 6 0 7 3 7 5 9 3 4
7 7 9 0 4 3 6 3 4 2 9 1 8 3 6 9 7 2 7
4 8 3 1 9 4 5 7 3 2 9 5 8 2 3 8 1 6 7
7 4 6 7 8 7 7 9 3 3 3 9 5 1 1 6 5 3 3
7 7 4 7 7 4 7 1 8 7 5 7 9 3 9 9 6 1 3
6 4 7 8 3 5 7 5 2 1 3 7 6 1 9 8 4 1 6
1 0 3 7 5 7 2 1 9 2 5 9 6 7 8 5 8 9 9
2 2 5 5 1 3 2 1 1 3 2 5 7 5 4 7 7 7 7
0 3 3 9 7 4 9 6 7 8 7 1 0 2 5 5 9 4 6
2 2 8 3 7 3 7 9 6 9 4 1 1 5 7 1 4 3 7
1 6 6 7 9 8 3 1 6 2 7 0 3 0 0 9 5 3 7
5 1 0 7 2 1 3 4 9 1 9 9 9 1 1 0 2 6 2
6 5 5 3 3 7 1 3 7 0 7 1 8 0 6 5 0 0 3
7 9 0 3 2 4 7 5 2 9 6 3 9 7 6 3 5 2 1
1 0 3 3 6 9 5 7 1 7 9 2 8 8 6 0 3 0 8
Praštevila do 1k v kocki:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
257
263
269
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
811
821
823
829
839
853
857
859
863
877
887
907
911
919
937
941
947
953
967
971
977
983
991
997
Upam da mi program pravilno prešteva tole. Zaenkrat sem preizkusil samo na unih premirih na netu (5x5,...). Gotovo je kakšen bug notri
.
LP
Malo igranja z EA (poganjanje < 10minut):
štetje v vse smeri + štetje vseh praštevil + upoštevanje 6 mestnih cifer
primes: 6332 (tukaj vsako enomestno praštevilo šteješ 8x ???)
3 3 7 9 5 3 3 3 3 3 7 7 5 7 2 7 3 7 4
7 9 7 0 0 5 1 7 9 7 1 3 9 9 1 3 7 5 7
3 0 1 7 3 1 3 6 1 3 3 7 0 1 2 2 3 1 7
3 1 1 0 1 3 3 7 3 3 7 6 9 5 8 5 0 6 7
7 7 3 9 3 3 4 2 6 1 7 3 1 2 2 3 7 3 5
3 7 3 7 1 2 6 9 1 7 9 5 9 7 9 7 5 6 7
3 1 1 3 7 6 2 4 3 7 3 3 7 3 5 9 0 7 9
7 7 9 3 4 1 2 3 1 1 1 7 6 0 2 1 0 2 3
9 1 6 2 3 3 7 0 1 9 9 7 7 9 3 1 9 4 3
7 1 1 7 0 7 7 9 7 1 3 3 3 3 7 3 1 7 3
7 4 7 1 8 7 5 9 2 9 1 5 2 1 3 9 0 1 7
2 3 5 3 9 5 4 7 9 6 1 7 7 5 1 9 3 7 2
3 0 1 7 0 9 7 1 7 7 5 9 1 1 3 5 7 1 3
3 7 7 3 5 4 3 3 8 3 3 7 7 7 5 2 1 1 5
7 1 3 9 3 0 3 5 5 9 1 7 3 7 7 5 3 4 7
3 1 7 3 9 7 7 3 0 0 3 3 3 7 1 5 0 3 3
3 7 7 5 7 7 3 3 3 1 1 4 7 9 3 0 3 1 5
7 3 3 4 9 3 8 7 1 1 3 1 3 3 7 1 0 3 7
3 3 3 7 7 7 3 3 3 2 7 7 2 7 3 3 2 5 7
štetje v vse smeri + štetje različnih praštevil + upoštevanje 6 mestnih cifer
primes: 959
1 5 3 9 1 4 8 9 5 8 7 3 3 9 1 7 0 2 7
3 5 0 4 1 4 6 4 4 1 7 8 8 8 9 0 1 0 9
8 3 1 0 9 2 7 3 7 5 9 1 2 9 0 9 4 1 3
2 1 6 5 4 9 5 9 3 5 5 6 1 8 7 3 4 4 1
5 9 4 5 1 7 9 7 3 1 6 0 7 3 7 5 9 3 4
7 7 9 0 4 3 6 3 4 2 9 1 8 3 6 9 7 2 7
4 8 3 1 9 4 5 7 3 2 9 5 8 2 3 8 1 6 7
7 4 6 7 8 7 7 9 3 3 3 9 5 1 1 6 5 3 3
7 7 4 7 7 4 7 1 8 7 5 7 9 3 9 9 6 1 3
6 4 7 8 3 5 7 5 2 1 3 7 6 1 9 8 4 1 6
1 0 3 7 5 7 2 1 9 2 5 9 6 7 8 5 8 9 9
2 2 5 5 1 3 2 1 1 3 2 5 7 5 4 7 7 7 7
0 3 3 9 7 4 9 6 7 8 7 1 0 2 5 5 9 4 6
2 2 8 3 7 3 7 9 6 9 4 1 1 5 7 1 4 3 7
1 6 6 7 9 8 3 1 6 2 7 0 3 0 0 9 5 3 7
5 1 0 7 2 1 3 4 9 1 9 9 9 1 1 0 2 6 2
6 5 5 3 3 7 1 3 7 0 7 1 8 0 6 5 0 0 3
7 9 0 3 2 4 7 5 2 9 6 3 9 7 6 3 5 2 1
1 0 3 3 6 9 5 7 1 7 9 2 8 8 6 0 3 0 8
Praštevila do 1k v kocki:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
257
263
269
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541
547
557
563
569
571
577
587
593
599
601
607
613
617
619
631
641
647
653
659
661
673
677
683
691
701
709
719
727
733
739
743
751
757
761
769
773
787
797
811
821
823
829
839
853
857
859
863
877
887
907
911
919
937
941
947
953
967
971
977
983
991
997
Upam da mi program pravilno prešteva tole. Zaenkrat sem preizkusil samo na unih premirih na netu (5x5,...). Gotovo je kakšen bug notri
.LP
Zgodovina sprememb…
- spremenil: Phil ()
snow ::
cman
Različna praštevila se gleda.
> The PHP scorer will use a table to quickly check if a number below
10^6 is prime. Did you know that this table can fit into 33Kb ?
(We can store 30 primes in 8 bits).
Hm? Kako tole 30 prastevil v 8 bitih?? Jaz bi rekel da gre pac 8 prastevil na 8 bitov...
Jaz mam lepo eno tabelo 100Mb rama.. 100 miljonov cifer. Tip char pac.. 1 oznacuje prime, 0 pa nonprime. Se pravi gledam s tem do vkljucno dolzine 8, najdene pa mecem v en std::vector pa potem gledam ce sem doloceno prastevilo ze dal notri.
Hitrost preverjanja je pa nekje 20 miljonov na sekundo na P4... sem naredil en 300*300 kvadrat pa preveril notri vse substringe do vkjucno dolzine 8.
Ena tabela v kateri najdete informacije o dolzinah substringov v kvadratu 20*20 pa o stevilu prastevil dolocene dolzine.
Kje se zdej najbolj splaca glodat?
Moj algo za sprehod po kvadratu in test za praštevila.
sum = stevilo enomestnih prastevil.. preverim posebej.
Zadeva sicer dela.. sam nevem kolk je zdej to optimalno.
Različna praštevila se gleda.
> The PHP scorer will use a table to quickly check if a number below
10^6 is prime. Did you know that this table can fit into 33Kb ?
(We can store 30 primes in 8 bits).
Hm? Kako tole 30 prastevil v 8 bitih?? Jaz bi rekel da gre pac 8 prastevil na 8 bitov...
Jaz mam lepo eno tabelo 100Mb rama.. 100 miljonov cifer. Tip char pac.. 1 oznacuje prime, 0 pa nonprime. Se pravi gledam s tem do vkljucno dolzine 8, najdene pa mecem v en std::vector pa potem gledam ce sem doloceno prastevilo ze dal notri.
Hitrost preverjanja je pa nekje 20 miljonov na sekundo na P4... sem naredil en 300*300 kvadrat pa preveril notri vse substringe do vkjucno dolzine 8.
Ena tabela v kateri najdete informacije o dolzinah substringov v kvadratu 20*20 pa o stevilu prastevil dolocene dolzine.
Kje se zdej najbolj splaca glodat?
Moj algo za sprehod po kvadratu in test za praštevila.
sum = stevilo enomestnih prastevil.. preverim posebej.
//[2,8] check
int sumprev=0;
//gledamo vse dolzine od 2 do 8
for(l=1;l<8;l++)
{
sumprev=sum;
//zacnemo v vseh x-ih
for(x=0;x<SIZE;x++)
{
//in vseh y-nih
for(y=0;y<SIZE;y++)
{
//pa v vse smeri
for(m=0;m<8;m++)
{
switch(m)
{
case 0:{cx=1;cy=0;break;}
case 1:{cx=1;cy=1;break;}
case 2:{cx=0;cy=1;break;}
case 3:{cx=-1;cy=1;break;}
case 4:{cx=-1;cy=0;break;}
case 5:{cx=-1;cy=-1;break;}
case 6:{cx=0;cy=-1;break;}
case 7:{cx=1;cy=-1;break;}
}
//ce gre v tisto smer... pa ce prva cifra ni 0
if(table[x][y] && (x+cx*l)>=0 && (x+cx*l)<SIZE && (y+cy*l)>=0 && (y+cy*l)<SIZE){
num=0;
//sestavimo cifro..
for(d=0;d<=l;d++)
{
num*=10;
num+=table[x+cx*d][y+cy*d];
}
//preverimo ce je prime in ce se ni v tabeli
if(primes[num])
{
int same=0;
for(int v=sumprev;v<vecPrimes.size();v++)
{
if(vecPrimes[v]==num)
{
same=1;
break;
}
}
if(!same)
{
vecPrimes.push_back(num);
sum++;
}
}
}
}
}
}
}
Zadeva sicer dela.. sam nevem kolk je zdej to optimalno.
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins
OwcA ::
Jaz mam lepo eno tabelo 100Mb rama.. 100 miljonov cifer. Tip char pac.. 1 oznacuje prime, 0 pa nonprime.
Daj potem raje tabelo bool-ov ali std::bitset.
Otroška radovednost - gonilo napredka.
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Najhitrejši programski jezik? (strani: 1 2 )Oddelek: Programiranje | 7848 (5668) | Senitel |
| » | Funkcija z logičnimi operaterji.... (strani: 1 2 )Oddelek: Programiranje | 5716 (5062) | CaqKa |
| » | Petaflopsu naproti (strani: 1 2 3 )Oddelek: Novice / Procesorji | 9095 (9095) | Marjan |
| » | cene permutacij help pleaseOddelek: Programiranje | 2120 (1727) | Sergio |
| » | kako definirtati prasteviloOddelek: Programiranje | 3832 (3637) | ooux |