Programmering - maraton

[Mattebruker]

Utfall med to fargar ( 10 + 10 ) har 1$\cdot$ $(\genfrac{}{}{0ex}{}{7}{2})$ = $\frac{7\cdot 6}{2}$ = 21 utfall. Dette bidraget er teke med i "totalen" ( sjå vedlagt kode ).

Oppfølgar: Undersøke om der finnast eit 5-siffra primtal med 4 partal-siffer.
P.S. Så langt er vi berre tre brukarar som er med på denne "leiken". Skulle ønskje at fleire melder seg på. Da blir det straks meir interessant å delta.

[Aleks855]

Ble det avgjort hva svaret på Gustavs oppgave var?

[Gustav]

Ble det avgjort hva svaret på Gustavs oppgave var?

Aleks er i nærheten, men ikke helt riktig

[Mattebruker]

Eg må ha misforstått problemstillinga i denne oppgava. Viser likevel korleis talet på utfall, etter mine berekningar, fordeler seg på antal fargar:

Sju fargar: 26544 utfall
Seks fargar: 76104 utfall
Fem fargar: 68166 utfall
Fire fargar: 22155 utfall
Tre fargar: 2205 utfall
To fargar: 21 utfall

Sum utfall = 26544 + 76104 + 68166 + 22155 + 2205 + 21 = 195195

No lurer eg på: Kvar ligg feilen ?

[Aleks855]

Ble det avgjort hva svaret på Gustavs oppgave var?

Aleks er i nærheten, men ikke helt riktig

Jeg har nå kjørt en milliard simulasjoner, men jeg har bare seks "låste" siffer: $6.67925\dots$

[Mattebruker]

Presenterer her mitt løysingforslag i kortform:

La X vere talet på fargar i eit tilfeldig utplukk på 20 element ( av totalt 70 som ligg i "kurven" ).

E( X ) = 2$\cdot$P( X = 2 ) + 3$\cdot$P( X = 3 ) + 4$\cdot$P( X=4 ) + 5$\cdot$P( X = 5 ) + 6$\cdot$P( X =6 ) + 7$\cdot$P( X = 7 )

P( X = 2 ) = $\frac{gunstig}{mulege}$ = $\frac{21}{195195}$ ( sjå tabell forrige innlegget mitt )
.
.
.
P( X = 7 ) = $\frac{gunstige}{mulege}$ = $\frac{26544}{195195}$

Du som les dette innlegget må gjerne kome med kritiske, saklege kommentarar til denne reknemåten.

[Aleks855]

Presenterer her mitt løysingforslag i kortform:

La X vere talet på fargar i eit tilfeldig utplukk på 20 element ( av totalt 70 som ligg i "kurven" ).

E( X ) = 2$\cdot$P( X = 2 ) + 3$\cdot$P( X = 3 ) + 4$\cdot$P( X=4 ) + 5$\cdot$P( X = 5 ) + 6$\cdot$P( X =6 ) + 7$\cdot$P( X = 7 )

P( X = 2 ) = $\frac{gunstig}{mulege}$ = $\frac{21}{195195}$ ( sjå tabell forrige innlegget mitt )
.
.
.
P( X = 7 ) = $\frac{gunstige}{mulege}$ = $\frac{26544}{195195}$

Du som les dette innlegget må gjerne kome med kritiske, saklege kommentarar til denne reknemåten.

Men hva er det endelige svaret du får av utregninga?

[Mattebruker]

E( X ) = 5.525443787 ( jamfør innlegg 8. aug. kl. 12.21 ) . Dette resultatet kan vi lett dobbelsjekke ved å rekne ut summen "for hånd" på f.eks. ein Casio-kalkulator.

[Aleks855]

Jeg tok en jukse-metode fordi jeg ikke fikk til matematikken. I denne metoden kjørte jeg 25 milliarder simulasjoner av 20 trekk fra en "krukke" med 70 elementer av 7 forskjellige typer (10 av hver) og fikk i gjennomsnitt 6.81874180... distinkte elementer per simulasjon.

Med det svaret i bakhodet prøvde jeg følgende metode:

Antall permutasjoner der vi IKKE plukker en gitt farge er $(\genfrac{}{}{0ex}{}{60}{20})$, og antall totale permutasjoner er $(\genfrac{}{}{0ex}{}{70}{20})$.

Så sannsynligheten for å få en gitt farge er $1-\frac{(\genfrac{}{}{0ex}{}{60}{20})}{(\genfrac{}{}{0ex}{}{70}{20})}$.

Forventet antall farger per trekk av 20 baller er da $$\stackrel{\text{rød}}{\overbrace{(1-\frac{(\genfrac{}{}{0ex}{}{60}{20})}{(\genfrac{}{}{0ex}{}{70}{20})})}}+\stackrel{\text{grønn}}{\overbrace{(1-\frac{(\genfrac{}{}{0ex}{}{60}{20})}{(\genfrac{}{}{0ex}{}{70}{20})})}}+\stackrel{\text{blå}}{\overbrace{(1-\frac{(\genfrac{}{}{0ex}{}{60}{20})}{(\genfrac{}{}{0ex}{}{70}{20})})}}+\dots =7(1-\frac{(\genfrac{}{}{0ex}{}{60}{20})}{(\genfrac{}{}{0ex}{}{70}{20})})\approx 6.81874180$$ som stemmer overens med simulasjonen.

Siden Gustav nevnte at jeg var i nærheten etter 1 milliard simulasjoner, så antar jeg at dette er rett.

[Gustav]

Fasiten sier 6.818741802 så Aleks har rett.

Problemet er orginalt formulert her: https://projecteuler.net/problem=493

[Mattebruker]

Interessant løysing !
Sit likevel igjen med eitt spørsmål: Kan Aleks eller Gustav forklare kvifor metoden med "vekta middelverdi" ikkje fungerer i dette tilfelle ?

[Aleks855]

Oppfølgar: Undersøke om der finnast eit 5-siffra primtal med 4 partal-siffer

Kort svar: Ja, det finnes mange.

[+] Skjult tekst

Code: Select all

[20021, 20023, 20029, 20047, 20063, 20089, 20201, 20249, 20261, 20269, 20287, 20407, 20441, 20443, 20483, 20627, 20641, 20663, 20681, 20807, 20809, 20849, 20887, 22003, 22027, 22063, 22067, 22229, 22247, 22283, 22409, 22441, 22447, 22469, 22481, 22483, 22621, 22643, 22669, 22807, 22861, 24001, 24007, 24023, 24029, 24043, 24049, 24061, 24083, 24203, 24223, 24229, 24247, 24281, 24407, 24421, 24443, 24469, 24481, 24623, 24683, 24809, 24821, 24841, 24847, 24889, 26003, 26021, 26029, 26041, 26083, 26203, 26209, 26227, 26249, 26261, 26263, 26267, 26407, 26423, 26449, 26489, 26627, 26641, 26647, 26669, 26681, 26683, 26687, 26801, 26821, 26849, 26861, 26863, 26881, 28001, 28027, 28069, 28081, 28087, 28201, 28229, 28283, 28289, 28403, 28409, 28429, 28447, 28463, 28603, 28607, 28621, 28627, 28643, 28649, 28661, 28663, 28669, 28687, 28807, 28843, 28867, 40009, 40063, 40087, 40241, 40283, 40289, 40423, 40427, 40429, 40483, 40487, 40609, 40627, 40801, 40823, 40829, 40841, 40847, 40849, 40867, 40883, 42023, 42043, 42061, 42083, 42089, 42209, 42221, 42223, 42227, 42281, 42283, 42403, 42407, 42409, 42443, 42461, 42463, 42467, 42487, 42641, 42643, 42649, 42667, 42683, 42689, 42821, 42829, 42841, 42863, 44021, 44027, 44029, 44041, 44087, 44089, 44201, 44203, 44207, 44221, 44249, 44263, 44267, 44269, 44281, 44449, 44483, 44621, 44623, 44641, 44647, 44683, 44687, 44809, 44843, 44867, 44887, 46021, 46027, 46049, 46061, 46229, 46261, 46441, 46447, 46489, 46601, 46643, 46649, 46663, 46681, 46687, 46807, 46829, 46861, 46867, 46889, 48023, 48029, 48049, 48221, 48247, 48281, 48407, 48409, 48449, 48463, 48481, 48487, 48623, 48647, 48649, 48661, 48809, 48821, 48823, 48847, 48869, 48883, 48889, 60029, 60041, 60083, 60089, 60209, 60223, 60289, 60427, 60443, 60449, 60601, 60607, 60623, 60647, 60649, 60661, 60689, 60821, 60869, 60887, 60889, 62003, 62047, 62081, 62201, 62207, 62401, 62423, 62467, 62483, 62603, 62627, 62683, 62687, 62801, 62827, 62861, 62869, 64007, 64063, 64067, 64081, 64223, 64283, 64403, 64483, 64489, 64601, 64609, 64621, 64627, 64661, 64663, 64667, 64849, 66029, 66041, 66047, 66067, 66083, 66089, 66221, 66403, 66449, 66463, 66467, 66601, 66629, 66643, 66683, 66809, 66821, 66841, 66863, 66883, 66889, 68023, 68041, 68087, 68207, 68209, 68227, 68261, 68281, 68443, 68447, 68449, 68483, 68489, 68669, 68683, 68687, 68821, 68863, 68881, 80021, 80207, 80209, 80221, 80263, 80287, 80407, 80429, 80447, 80449, 80489, 80603, 80621, 80627, 80629, 80669, 80681, 80683, 80687, 80803, 80809, 80849, 80863, 82003, 82007, 82009, 82021, 82067, 82207, 82223, 82241, 82261, 82267, 82421, 82463, 82469, 82483, 82487, 82601, 82609, 82847, 82883, 82889, 84047, 84061, 84067, 84089, 84221, 84223, 84229, 84247, 84263, 84401, 84407, 84421, 84443, 84449, 84463, 84467, 84481, 84629, 84649, 84809, 84827, 84869, 86027, 86029, 86069, 86083, 86201, 86209, 86243, 86249, 86263, 86269, 86287, 86423, 86441, 86461, 86467, 86627, 86629, 86689, 86843, 86861, 86869, 88001, 88003, 88007, 88069, 88223, 88241, 88261, 88289, 88423, 88427, 88463, 88469, 88607, 88609, 88643, 88661, 88663, 88667, 88681, 88801, 88807, 88843, 88861, 88867, 88883]

Det finnes noen lure optimiseringer her. Blant annet er vi ikke interessert i femsifrede tall som begynner med et oddetall, for da må de øvrige sifrene være partall, inkludert det siste sifret, og da er det definitivt ikke et primtall. Jeg starta derfor søket på $20001$ i stedet for $10001$. Men av latskap leter jeg også forgjeves gjennom $3xxxx,5xxxx,\dots$. Dette er dog en tolererbar omvei siden skriptet uansett kjører på bare noen millisekund.

Bruker Erasthotenes' Sil (som har blitt min favorittalgoritme grunnet hvor utrolig kjapt den kategoriserer veldig høye primtall), og teller deretter opp partallssifre.

Code: Select all

primes = [True]*100000

primes[0] = False
primes[1] = False

for i in range(2, len(primes)):
    for j in range(2*i, len(primes), i):
        primes[j] = False

targets = []
for i in range(20001, 100000, 2):
    if primes[i]:
        evens = 0
        for j in str(i):
            if int(j) % 2 == 0:
                evens += 1
        if evens == 4:
            targets.append(i)
print(targets)

Jeg er ikke så dyktig med Python, så det finnes sikkert noen kule one-liners som kan byttes inn her. Føler koden min bærer preg av årevis med applikasjonskoding

[Aleks855]

Oppfølger: Hvilket naturlig tall $n<{10}^6$ treffer flest primtall i sin Collatz-følge?

Definisjon: Collatz-følgen til en $n\in \mathbb{N}$ er gitt ved $$n_{i+1}=\{\begin{array}{ll}{n}_i/2& n_i\text{er partall}\\ 3n_i+1& n_i\text{er oddetall}\end{array}$$

Eksempel: Collatz-følgen til $n=10$ er $10,5,16,8,4,2,1$ og inneholder $n$ selv.

[Gustav]

Interessant løysing !
Sit likevel igjen med eitt spørsmål: Kan Aleks eller Gustav forklare kvifor metoden med "vekta middelverdi" ikkje fungerer i dette tilfelle ?

Definisjonen av forventningsverdi gir at svaret her blir $\sum _{n=2}^{7}np(n)$, der $p(n)$ er sannsynligheten for å få $n$ distinkte farger (og $\sum _{n=2}^{7}p(n)=1$), så det må vel være utgangspunktet.

[Mattebruker]

Her er vi heilt einige , Gustav.