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: 456
Registrert: 26/02-2021 21:28

N = 963919 treffer 62 primtal i sin Colatz-følge. Kan dette stemme ?

Kode: Velg alt

from pylab import *
#
#  Registrer odde primtal mindre enn 5000
#
ptal = zeros(1000)
nummer = 3; ptal[1] = 3; ptal[2] = 5; ptal[3] = 7
for i in range(11,5001,2):
  faktor = 3; treff = True
  while ( treff == True) and (faktor < sqrt(i)):
    if (i/faktor) == floor(i/faktor):
      treff = False
    else:
      faktor = faktor + 2
  if treff == True:
    nummer = nummer + 1
    ptal[nummer] = i
#
# Tel opp antal primtal i Colatz-følgja med startverdi N = start,
# samt oppdaterer høgste antal gjennom variablen maks
# 
maks = 0
for start in range(40000, 50000):
  a = zeros(1000); nummer = 1 ; a[nummer] = start; antal = 0
  tal = start
  while ( tal > 1):
    nummer = nummer + 1
    if(tal/2) == floor(tal/2):
      tal = tal/2
    else:
      tal = 3*tal + 1
    a[nummer] = tal
  for i in range(1, nummer + 1):
    if (a[i]/2)!= floor(a[i]/2):
      j = 1; faktor = ptal[j]; treff = True;
      while ( faktor < sqrt(a[i])) and (treff == True):
        if (a[i]/faktor) == floor(a[i]/faktor):
          treff = False
        else:
          j = j +1
          faktor = ptal[j]
      if ( treff == True):
        antal = antal + 1
  if ( antal > maks):
    maks = antal
    taltreff = start
print( taltreff, "  ", maks )    
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Dårlig gjennomtenkt fra min side, men jeg improviserte oppgaven før jeg hadde en løsning selv.

Jeg har kodet en løsning nå, men den vil ta noen timer å gjennomføre. (Enda dårligere gjennomtenkt.)

Så får vi sammenlikne svar :)

Hvor lang tid bruker koden din på å finne svaret?
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Interessant tilbakemelding , Aleks !
Har gjort same erfaringa som du. Kjem aldri i mål når startverdien( N ) sveipar over heile talområdet frå 10 opp til 999999. Men eg har funne ut at problemet let seg løyse ved å dele opp talmengda i blokker , kvar på 10000. Då tek det omlag 2 minutt å få ut eit delresultat, dvs. den N-verdien som treffer flest primtal i sin Colatz-følge.
Her er nokre eksempel:
Heiltalsområdet [990000,999999] kjem ut med makstal 54 treff for N = 990379
Heiltalsområdet [980000 , 990000] kjem ut med 52 treff for N = 987081
Heiltalsområdet [970000 , 980000] kjem ut med 62 treff for N = 970599
Heiltalsområdet [960000 , 970000 ] kjem ut med 62 treff for N = 963919
Heiltalsområdet [950000 , 960000 ] kjem ut med 60 treff for N = 950943
Heiltalsområdet [940000 , 950000 ] kjem ut med 54 treff for N = 940097
Heiltalsområdet [930000 , 940000 ] kjem ut med 60 treff for N = 938143
Heiltalsområdet [920000 , 930000 ] kjem ut med 56 treff for N = 927457
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Skjønner!

Jeg kjører over hele $n \in [1, 10^6]$ for ordens skyld, men jeg ser nå at den må få gå over natta. Etter nesten 3 timer har den kommet til $n=397,000$, og tidsbruken er nok ikke konstant.

Collatz-følgene har en morsom tendens i at små tall kan ha fryktelig mye lengre følger enn tall som er vesentlig større. Det er også en finurlighet man kan observere, fordi jeg ser at tempoet på primtallskalkulasjonene er variabel. Den stopper opp i litt lengre perioder enkelte ganger, og det er uavhengig av størrelsen på $n$, men mer fordi den har funnet en $n$ som har en mye lengre følge enn naboene sine.
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 ?
Min løsning på sannsynlighetsproblemet:

La $q=1-\frac{{60\choose 20}}{70\choose 20}$ angi sannsynligheten for at en gitt farge er med i uttrekningen. Sannsynligheten for at $n$ farger er med blir $p(n)={7\choose n}q^n(1-q)^{7-n}$.

Forventningsverdien blir derfor $\sum_{n=2}^7np(n)=\sum_{n=2}^7 n {7\choose n}q^n(1-q)^{7-n}\approx 6.81874180$ som, ifølge Aleks, er det samme som $7q$.
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

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.
Problemet her er at sannsynlighetene du har fått er feil. P(X=2) skal være ${7\choose 2}q^2(1-q)^5$ der $q=1-\frac{60\choose 20}{70\choose 20}$
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Aksepterer fullt ut Gustav si forklaring som tek utgangspunkt i ei binomisk sannsynsfordeling. Greier likevel ikkje å innsjå at det blir feil å bruke ei fordeling som
baserer seg på "antal gunstige utfall/antal mulege utfall".
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Mattebruker skrev: 16/08-2022 21:32 Aksepterer fullt ut Gustav si forklaring som tek utgangspunkt i ei binomisk sannsynsfordeling. Greier likevel ikkje å innsjå at det blir feil å bruke ei fordeling som
baserer seg på "antal gunstige utfall/antal mulege utfall".
Problemet er nok at du har regnet feil et sted på gunstige og/eller mulige utfall, tror jeg. Klarer ikke helt se hva tallene burde vært nå, men..

Den mest elegante løsningen er vel å la $X_i$ være stokastiske variabler som betegner om farge $i$ blir trukket ut eller ikke, og benytte seg av lineariteten til forventningsverdien, slik Aleks har gjort: $E(\sum_i X_i)=\sum_i E(X_i)=7q$
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

Aleks855 skrev: 15/08-2022 22:50 Skjønner!

Jeg kjører over hele $n \in [1, 10^6]$ for ordens skyld, men jeg ser nå at den må få gå over natta. Etter nesten 3 timer har den kommet til $n=397,000$, og tidsbruken er nok ikke konstant.

Collatz-følgene har en morsom tendens i at små tall kan ha fryktelig mye lengre følger enn tall som er vesentlig større. Det er også en finurlighet man kan observere, fordi jeg ser at tempoet på primtallskalkulasjonene er variabel. Den stopper opp i litt lengre perioder enkelte ganger, og det er uavhengig av størrelsen på $n$, men mer fordi den har funnet en $n$ som har en mye lengre følge enn naboene sine.
Har du fått noe svar på dette problemet?
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Ah, jeg glemte å sjekke outputen.

Jeg får faktisk 70009 som svar, og at den har 45 primtall i sin Collatz-følge.

70009 steps over 45 primes: [70009, 88607, 132911, 106451, 59879, 89819, 85259, 95917, 35969, 20233, 25609, 19207, 32413, 18233, 6491, 16433, 2311, 3467, 587, 881, 661, 31, 47, 71, 107, 137, 103, 233, 263, 593, 167, 251, 283, 479, 719, 1619, 911, 1367, 577, 433, 61, 23, 53, 5, 2]

Jeg har verifisert at alle disse er primtall, men det virker usannsynlig at et tall $n < 10^5$ skal ha vært den beste, gitt at vi sjekker alle $n < 10^6$.

Jeg skal feilsøke litt når jeg kommer hjem fra jobb.

Mattebruker: Du fikk en kandidat med flere primtall. Har du mulighet til å printe dem ut?
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Hallo ! Har sjekka kandidaten ( 70009 ) du oppgir, og det stemmer at dette talet treffer på 45 odde primtal.
Eg har to kandidatar ( 970599 og 963919 ) med 61 odde primtal kvar.
Viser elles til mitt innlegg datert 15. august. I denne lista har eg også rekna med talet 2 som eit primtal ( per definisjon ).
Men dette blir kanskje litt uinteressant ettersom alle Collatz-følger har dette talet som nest siste ledd.
Elles er det verd å merke seg at Collatz-følga terminerer straks den treffer på ein toar-potens, eks. 1024
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Jeg registrerer også at de to tallene du nevner har 61 primtallsfaktorer hver (inkludert 2), som var raskt å finne når man tester enkelttall, så det betyr at den første koden jeg skrev var defekt. Jeg skal jobbe litt videre på den og se om jeg finner noe som kjører på noe mindre enn en dag :D

I mellomtiden, har du en oppfølger?
Bilde
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Oppfølgar
Lag eit program som reknar ut ein tilnærma verdi( 5 desimalar ) for summen av den uendelege rekkja

1 + 1/1 + 1/1*2 + 1/1*2*3 + 1/1*2*3*4 + ................

Programmet avsluttast når neste ledd er mindre enn 10^( -6 )

P.S. Ønskeleg å få med fleire( nye ) deltakarar ! Da blir det meir interessant og inspirerande å vere med på denne leiken.
SveinR
Abel
Abel
Innlegg: 635
Registrert: 22/05-2018 22:12

Mattebruker skrev: 19/08-2022 20:35P.S. Ønskeleg å få med fleire( nye ) deltakarar ! Da blir det meir interessant og inspirerande å vere med på denne leiken.
Ok, får slenge meg på da :)

Kode: Velg alt

result = 1 #summen

denom = 1 #nevner i neste brøk
factor = 1 #siste faktor i neste nevner

while denom < 10**6:
  result += 1/denom
  
  factor += 1
  denom *= factor

print(result)
Gir, kanskje ikke så overraskende, $e$ til fem desimalers nøyaktiget (eller seks faktisk): $2.7182815255731922$


Oppfølger: Lag et program som finner tilnærmede sannsynligheter for følgende situasjon: I en oppgave skal 8 figurer kobles korrekt til 8 ulike alternativer (f.eks. figur 1 -> alternativ A, osv.). Ved ren gjetning, hva er sannsynligheten for å få hhv. 0 rette, 1 rett, 2 rette, osv.?
Mattebruker
Weierstrass
Weierstrass
Innlegg: 456
Registrert: 26/02-2021 21:28

Velkommen i det gode selskap , SveinR. Interessant problem du presenterer. Vikla meg inn i ein irrgang ved første forsøk, men brått fekk eg ein fiks ide:
Kvart av dei 8 alternativa ( A , B , ..................., G , H ) har eitt gunstig utfall av 8 mulege (1 , 2 , .................., 7 , 8 ). Det gir ei binomisk fordeling med suksessannsyn
p = [tex]\frac{1}{8}[/tex]. La X vere talet på rette gjetningar. Da er

P( X = n ) = [tex]\binom{8}{n}[/tex] ([tex]\frac{1}{8}[/tex])[tex]^{n}[/tex]( 1 - [tex]\frac{1}{8}[/tex])[tex]^{8 - n}[/tex] , n [tex]\in[/tex]{ 0 , 1 ,.................., 7 , 8 }

Python har ganske sikkert ein eigen kode for binomialkoeffisienten. Når denne er kjent , er det fort gjort å lage eit program som reknar ut og presenterer
sannsynsfordelinga. Eksempel: P( X = 0 ) = ([tex]\frac{7}{8}[/tex] )[tex]^{8}[/tex] = 0.3436 [tex]\approx[/tex] 34.4 %

Er spent på om mi tolking er korrekt. Kva seier innsendar ?
Svar