Programmering - maraton

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk for videregående skole og oppover på høyskolenivå. Alle som føler trangen er velkommen til å svare.

Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga

Mattebruker
Weierstrass
Weierstrass
Innlegg: 457
Registrert: 26/02-2021 21:28

Utfall med to fargar ( 10 + 10 ) har 1[tex]\cdot[/tex] [tex]\binom{7}{2}[/tex] = [tex]\frac{7\cdot 6}{2}[/tex] = 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
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Ble det avgjort hva svaret på Gustavs oppgave var?
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Aleks855 skrev: 08/08-2022 23:03 Ble det avgjort hva svaret på Gustavs oppgave var?
Aleks er i nærheten, men ikke helt riktig
Mattebruker
Weierstrass
Weierstrass
Innlegg: 457
Registrert: 26/02-2021 21:28

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 ?
Sist redigert av Mattebruker den 10/08-2022 10:47, redigert 1 gang totalt.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Gustav skrev: 09/08-2022 00:58
Aleks855 skrev: 08/08-2022 23:03 Ble det avgjort hva svaret på Gustavs oppgave var?
Aleks er i nærheten, men ikke helt riktig
:lol:

Jeg har nå kjørt en milliard simulasjoner, men jeg har bare seks "låste" siffer: $6.67925\ldots$
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 457
Registrert: 26/02-2021 21:28

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[tex]\cdot[/tex]P( X = 2 ) + 3[tex]\cdot[/tex]P( X = 3 ) + 4[tex]\cdot[/tex]P( X=4 ) + 5[tex]\cdot[/tex]P( X = 5 ) + 6[tex]\cdot[/tex]P( X =6 ) + 7[tex]\cdot[/tex]P( X = 7 )

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

Du som les dette innlegget må gjerne kome med kritiske, saklege kommentarar til denne reknemåten.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Mattebruker skrev: 10/08-2022 10:28 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[tex]\cdot[/tex]P( X = 2 ) + 3[tex]\cdot[/tex]P( X = 3 ) + 4[tex]\cdot[/tex]P( X=4 ) + 5[tex]\cdot[/tex]P( X = 5 ) + 6[tex]\cdot[/tex]P( X =6 ) + 7[tex]\cdot[/tex]P( X = 7 )

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

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?
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 457
Registrert: 26/02-2021 21:28

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
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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 $\binom{60}{20}$, og antall totale permutasjoner er $\binom{70}{20}$.

Så sannsynligheten for å få en gitt farge er $1 - \frac{\binom{60}{20}}{\binom{70}{20}}$.

Forventet antall farger per trekk av 20 baller er da $$\overbrace{\left( 1 - \frac{\binom{60}{20}}{\binom{70}{20}} \right)}^{\text{rød}} + \overbrace{\left( 1 - \frac{\binom{60}{20}}{\binom{70}{20}} \right)}^{\text{grønn}} + \overbrace{\left( 1 - \frac{\binom{60}{20}}{\binom{70}{20}} \right)}^{\text{blå}} + \ldots = 7\left( 1 - \frac{\binom{60}{20}}{\binom{70}{20}} \right) \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.
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Fasiten sier 6.818741802 så Aleks har rett.

Problemet er orginalt formulert her: https://projecteuler.net/problem=493
Mattebruker
Weierstrass
Weierstrass
Innlegg: 457
Registrert: 26/02-2021 21:28

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 ?
Sist redigert av Mattebruker den 10/08-2022 15:26, redigert 1 gang totalt.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Oppfølgar: Undersøke om der finnast eit 5-siffra primtal med 4 partal-siffer
Kort svar: Ja, det finnes mange.
[+] Skjult tekst

Kode: Velg alt

[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, \ldots$. 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.

Kode: Velg alt

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 :lol:
Bilde
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

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{cases} n_i/2 & n_i\, \text{er partall} \\ 3n_i+1 & n_i \, \text{er oddetall} \end{cases}$$

Eksempel: Collatz-følgen til $n=10$ er $10, 5, 16, 8, 4, 2, 1$ og inneholder $n$ selv.
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Mattebruker skrev: 10/08-2022 14:36 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
Weierstrass
Weierstrass
Innlegg: 457
Registrert: 26/02-2021 21:28

Her er vi heilt einige , Gustav.
Svar