Wiskunde Olympiade

[arnem_]

Ik ben wel benieuwd naar de gevonden resultaten van andere deelnemers dus open ik het oude topic maar weer opnieuw.

Wat vraag 12/13 betreft, dit hebben wij gevonden:

Is vast te laat heh

antwoord op vraag 12 waar wij de kleinste afwijking mee konden vinden:

ondergrens: C(n) >= ²log_n naar boven afgerond
bovengrens: C(n) =< (²log_n naar beneden afgerond) * 2

antwoord op vraag 13 (als deze niet goed is )
18

je kunt (als dit het goede antwoord is) dit vrij gemakkelijk vinden door 8127 te delen door door n en dit uit te zetten in een tabel. Je zoekt dan de gehele getallen er uit en zoekt het getal uit dat zo hoog mogelijk en zo dicht mogelijk bij een macht van 2 zit.
Je vind de volgende resultaten:
3 - 2703
7 - 1161
9 - 903
21 - 387
27 - 301
43 - 189
63 - 129

In principe moet je een zo hoog mogelijk getal zoeken uit de macht van 2, dan kun je de maximale verdubbeling zo lang mogelijk volhouden. Maar in dit geval kom je later niet uit om dat de getallen boven 129 ver van een macht van 2 af liggen.
Dus de rij gaat zo 1, 2, 4, 8, 16 ,32, 64, 128 129, 258, 516, 1032, 2064, 4128,
6192, 7224, 7740, 7998, 8127

De complexiteit van 8127 is dus 18.
Bij grotere getallen zal het nog wel wat ingewikkelder liggen maar denk dat dit voor dit getal wel op gaat.

Zeker voor vraag 12 zal er een beter antwoord te vinden. Ik wil wel eens weten welke!

[Anoniem: 39441]

Met ons algoritme kwamen we op 19. Voor dat getal was ie echter niet zo optimaal.

17 is zeker mogelijk (via wat priemgetallen geloof ik). Die had ik ook op papier staan, maar die heb ik niet meer

[ Voor 12% gewijzigd door Anoniem: 39441 op 29-11-2002 23:08 ]

[Anoniem: 28926]

HE? wij hadden gewoon 16: 1,2,3,5,10,20,30,60,63,126,252,504,1008,2016,4032,8064,8127. je moest gewoon op die 63 uitkomen want dat is het getal waarmee je door verdubbelen het dichtst bij komt. bij 8064 moest je dan nog eens 63 erbij doen en dan heb je het.

[Lord Daemon]

Weet iemand hoe je c(n) kan bepalen voor willekeurige n?

Ik heb er gisteren even naar zitten kijken, en twee vermoedens geformuleerd die ik echter nog niet bewezen heb:

Vermoeden 1

Voor elke p is priem geldt dat c(p) = n + m - 2 met n het aantal getallen en m het aantal 1-en in de binaire representatie van p.

Vermoeden 2

Voor elk getal q geldt dat c(q) kleiner dan of gelijk aan de som van c(p_i) is, met p_i de priemfactoren van q.

Wie zich geroepen voelt mag ze weerleggen of bewijzen.

[Lord Daemon]

Vermoeden 3

Als een getal q geschreven kan worden als 2^k * p, met k een willekeurig getal en p een priemgetal (of 1), dan geldt c(q) = c(p) + k.

Stelling 1

Het 'greedy algorithm', dat zo snel mogelijk een zo hoog mogelijk getal probeert te produceren, is niet het perfecte algoritme. Voorbeeld waarin het dat wel is: 1 - 2 - 4 - 8 - 16 - 17, en c(17) is inderdaad 5.

Bewijs: 1 - 2 - 4 - 8 - 12 - 14 - 15, is de greedy oplossing voor 15. Echter, 1 - 2 - 3 - 5 - 10 - 15 is een stap sneller.

Stelling 2

Het greedy algorithm produceert een getal q in n + m - 2 stappen, met n het aantal getallen en m het aantal 1-en in de binaire representatie van q.

Bewijs: het algoritme zal eerst n - 1 keer met twee vermenigvuldigen, en heeft dan alle machten van 2 tot 2^n-1 geproduceerd. Dat er vervolgens nog m - 1 maal een van de kleinere getallen bij het grootste getal moet wordne opgeteld is evident als je het getal binair beschouwt.

Gevolg 1

c(q) =< n + m - 2 stappen, met n het aantal getallen en m het aantal 1-en in de binaire representatie van q.

Vermoeden 1 (alt. versie)

Dit vermoeden is nu te herformuleren als: het greedy algorithm is het perfecte algoritme voor elke p is priem.

Vermoeden 1 + 3 (alt. versie)

Deze vermoedens zijn nu samen te herformuleren als: Als een getal q geschreven kan worden als 2^k * p, met k een willekeurig getal en p een priemgetal (of 1), dan is het perfecte algoritme als volgt: construeer p met het greedy algorithm, en vermenigvuldig dit vervolgens k maal met 2.

[ Voor 93% gewijzigd door Lord Daemon op 30-11-2002 13:14 ]

[FCA]

Zou iemand mij kunnen vertellen wat de opgaves zijn, of waar die te vinden zijn?
Dan kunnen niet-middelbare scholieren misschien ook meepraten.

[Lord Daemon]

FCA schreef op 30 november 2002 @ 13:25:
Zou iemand mij kunnen vertellen wat de opgaves zijn, of waar die te vinden zijn?
Dan kunnen niet-middelbare scholieren misschien ook meepraten.

De opgaves ken ik niet, maar het idee is het volgende:

Maak een reeks F volgens de volgende voorschriften:
1) F₀ = 1.
2) F_n = F_n-1 + F_i, met i < n.

c(q) is gedefinieerd als het kleinste getal n waarvoor er een reeks is met F_n = q.

Voorbeeld van een reeks:
1 - 2 - 4 - 8 - 12 - 13

c(1) = 0, c(2) = 1, c(3) = 2, c(4) = 2, c(5) = 3, etcetera.

[ Voor 11% gewijzigd door Lord Daemon op 30-11-2002 15:44 ]

[FCA]

Helaas, Lord Daemon, je vermoeden over c(p) voor p priem gaat niet op.
Voor p=31, geldt
c(31) = 7 , terwijl n=5, m=5 dus n+m-2=8
1 - 2 - 4 - 8 - 9 - 18 - 27 - 31 terwijl de 'greedy algorithm'
1 - 2 - 4 - 8 - 16 - 24 - 28 - 30 - 31 geeft.

Ik begin steeds meer het idee te krijgen dat er geen simpele oplossing is voor het berekenen van c(p). wel voor het vinden van een bovengrens, en ook een ondergrens, maar de boven en ondergrens liggen helaas niet dicht bij elkaar.
Vermoeden 2 en 3 zijn juist, dat is niet zo heel erg moeilijk te bewijzen.
Ben nu een Mathematica programmaatje aan het construeren dat voor de eerste 1000 ofzo getallen de c(q) berekent. Brute force...

[Anoniem: 27677]

het kan aan mij liggen, maar is dit de olympiade van dit jaar? want dan mogen jullie even doorgaan! ik krijg dat namelijk pas vrijdag !! en m'n leraar zei ook al dat hier nog geen oplossing voor was gevonden.. dus je had het goede vermoeden dat er geen simpele oplossing voor was FCA

[Virgol]

Drie stellingen die eenvoudig te bewijzen zijn:
c(n+1)=<c(n)+1
c(n+2)=<c(n)+1
c(n*2)=<c(n)+1

En volgens mij geld deze ook:
c(a^k*p)=<k*c(a)+c(p)

edit:

Volgens mij volgt die laatste stelling gewoon uit:
c(a*b)=<c(a)+c(b)

[ Voor 28% gewijzigd door Virgol op 01-12-2002 20:46 ]

[Virgol]

Reeks A = a₁,a₂,a₂....a_n
c(a_n) = n-1
Reeks B = b₁,b₂,b₃....b_k
c(b_k) = k-1
Reeks D = a₁,a₂,a₃.....a_n,a_n*b₂,a_n*b₃.....a_n*b_k
c(d_n+k-1) = c(a_n*b_k) =< n+k-2 = c(a_n)+c(b_k)

Het bewijs van mijn laatste stelling. Nu alleen nog iemand die dat kleiner dan teken weg kan werken

[FCA]

Dat kan helaas niet. Goed voorbeeld: (met dank aan BroxThaMan)
8127.
8127 = 3³ * 7 * 43
c(3) = 2
c(7) = 4
c(43) = 8
1 - 2 - 4 - 6- 7 - 14 - 28 - 42 - 43
1 - 2 - 4 - 8 - 16 - 32 - 40 - 42 - 43
1 - 2 - 3 - 6 - 12 - 24 - 36 - 42 - 43
Dus c(8127) =< 3* 2 + 4 + 8 = 18
Echter c(8127) =< 16
1 - 2 - 3 - 5 - 10 - 20 - 40 - 60 - 63 - 126 - 252 - 504 - 1008 - 2016 - 4032 - 8064 - 8127
Trouwens, het is nog best lastig een brute-force algoritme hiervoor te maken. Kom er nog niet echt uit.

[ Voor 4% gewijzigd door FCA op 01-12-2002 21:54 ]

[FCA]

Laat die brute-force algoritme maar zitten.
elke n-de stap zijn er n mogelijkheden, dus de complexiteit is ongeveer n!, en dat is veelsteveel.
Hier mijn eerste handmatige probeersel:

code:

n=1    2       3       4        5
----------------------------------------------
1 2     3   4   5   6
                7
                8
                9
                10
             6  7
                8
                9
                10
                12
            7   8
                9 
                10
                11
                14
            8   9
                10
                11
                12
                16
        5   6   7
                8
                9
                11
                12
            7   8
                9
                10
                12
                14
            8   9
                10
                11
                13
                16
            10  11
                12
                13
                15
                20
        6   7   8
                9
                10
                13
                14
            8   9
                10
                11
                14
                16
            9   10
                11
                12
                15
                18
            12  13
                14
                15
                18
                24
    4   5   6   7
                8
                10
                11
                12
            7   8
                9
                11
                12
                14
            9   10
                11
                13
                14
                18
            10  11
                12
                14
                15
                20
         6  7   8
                9
                11
                13
                14
            8   9
                10
                12
                14
                16
            10  11
                12
                14
                16
                20
            12  13
                14
                16
                18
                24
         8  9   10
                11
                13
                17
                18
            10  11
                12
                14
                18
                20
            12  13
                14
                16
                20
                24
            16  17
                18
                20
                24
                32

[Virgol]

Virgol schreef op 01 december 2002 @ 21:31:Het bewijs van mijn laatste stelling. Nu alleen nog iemand die dat kleiner dan teken weg kan werken

Ik zie het want het is idd niet exact. Het klopt al niet voor 33. Maar samen met de andere maximale waarden kom je volgens mij een heel eind. Helaas kom ik nog niet lager dan 18 bij 8127.

[Virgol]

Nog een handige voor p is priem die uit andere volgt:
c(p) =< c(p-1)+1
c(p) =< c(p-2)+1

[blinkymichiel]

Anoniem: 28926 schreef op 30 november 2002 @ 01:29:
HE? wij hadden gewoon 16: 1,2,3,5,10,20,30,60,63,126,252,504,1008,2016,4032,8064,8127. je moest gewoon op die 63 uitkomen want dat is het getal waarmee je door verdubbelen het dichtst bij komt. bij 8064 moest je dan nog eens 63 erbij doen en dan heb je het.

Virgol, hier zie je dat 16 toch het laagste getal is..

Ik vind het allemaal wel mooi dat wij als middelbare scholieren dit mogen oplossen

Wat ook hard is, behalve als je de 'prefecte' oplossing geeft die hier eigenlijk niet voor te vinden is, zeker niet door zoals ik zei, 'normale' middelbare scholieren, is dat het ook onmogelijk is om een 10 te halen...

Wel jammer

[Virgol]

Ik heb nu pas de vraag echt gelezen. Die manier van factoriseren en de c(n) van de factoren optellen werkt alleen voor de getallen waar de factor methode de snelste is. Verder zijn er getallen waar de gready het best werkt zoals voor 33 en dan zijn er nog de getallen waar je een combinatie moet gebruiken zoals 8127 dat zijn getallen waar een aantal priemfactoren vermedervuldigen tot een 2^k+2^n met k>n. Ben nu aan het kijken hoe ver ik kom met brute force.

[ Voor 48% gewijzigd door Virgol op 02-12-2002 17:44 ]

[Anoniem: 43971]

Hier stond onzin...

[ Voor 85% gewijzigd door Anoniem: 43971 op 02-12-2002 19:13 ]

[arnem_]

In de inleidende opgave stond dat het vinden van een formule vrijwel onmogelijk was, aangezien dit op wetenschappelijk niveau nog niet eens gelukt is.
Voor het vinden van priemagetallen is bijv. ook nog steeds geen formule gevonden.
als iemand dat hier voor elkaar krijgt.

Eén van de opdrachten was dan ook om een ondergrens en een bovengrens te bepalen die zo dicht mogelijk bij het exacte antwoord zou liggen. In mijn eerste post heb ik een aanzetje gegeven (ons ingevulde antwoord) maar ik weet zeker dat een exactere onder- bovengrens te bepalen is.

[Lord Daemon]

arnem_ schreef op 03 december 2002 @ 19:42:
In de inleidende opgave stond dat het vinden van een formule vrijwel onmogelijk was, aangezien dit op wetenschappelijk niveau nog niet eens gelukt is.

In de inleiding stond onzin, namelijk dat het zelfs met de snelste computer ter wereld niet mogelijk was om binnen een dag alle korste rijtjes tot en met n=50 te vinden. Nu, dat zijn iets van de orde van 7! of 8! rijtjes, dus dat is gewoon onwaar. Dat kan ik ook wel met de hand op een regenachtige zondagmiddag.

Voor het vinden van priemagetallen is bijv. ook nog steeds geen formule gevonden.
als iemand dat hier voor elkaar krijgt.

Uh? Voor het vinden van priemgetallen is een polynomiaal algoritme bekend. Voor het vinden van deze rijtjes zijn we nog niet verder dan log(n)!, dat is niet erg goed.

[FCA]

OK, ik heb nu een brute-force methode. Hieronder de c(q) voor alle q tussen de 1 en de 70.
Eerste getal is q, tweede getal is c(q):

{{1, 0}, {2, 1}, {3, 2}, {4, 2}, {5, 3}, {6, 3}, {7, 4}, {8, 3}, {9, 4}, {10, 4}, {11, 5}, {12, 4}, {13, 5}, {14, 5}, {15, 5}, {16, 4}, {17, 5},
{18, 5}, {19, 6}, {20, 5}, {21, 6}, {22, 6}, {23, 6}, {24, 5}, {25, 6}, {26, 6}, {27, 6}, {28, 6}, {29, 7}, {30, 6}, {31, 7}, {32, 5}, {33, 6},
{34, 6}, {35, 7}, {36, 6}, {37, 7}, {38, 7}, {39, 7}, {40, 6}, {41, 7}, {42, 7}, {43, 7}, {44, 7}, {45, 7}, {46, 7}, {47, 8}, {48, 6}, {49, 7},
{50, 7}, {51, 7}, {52, 7}, {53, 8}, {54, 7}, {55, 8}, {56, 7}, {57, 8}, {58, 8}, {59, 8}, {60, 7}, {61, 8}, {62, 8}, {63, 8}, {64, 6}}

Echter, dit kostte op een redelijk moderne PC toch wel zo'n kwartiertje rekenwerk.
Misschien kan iemand mijn brute-force methode verbeteren? Hij schaalt echt ontzettend slecht, aangezien mijn methode O(n!) stappen kost.

Gebruikte methode:

code:

tabel = {{1}, {1, 2}};
For[
    i = 2,
    i < 7!,
    i++,
    For[
               j = 1,
               j <= Length[tabel[[i]]],
               j++,
               tabel = Append[
                     tabel, 
                             Append[
                                   tabel[[i]], 
                                   tabel[[i, Length[tabel[[i]]]]] + tabel[[i, j]]
                                   ]
                             ]
            ]
    ]
lengte = Sort[
      Table[{Last[tabel[[i]]], Length[tabel[[i]]] - 1}, {i, 1, 
          Length[tabel]}]];
c[q_] := Min[
    Table[If[First[lengte[[i]]] == q, Last[lengte[[i]]], 100], {i, 
        Length[lengte]}]]
Table[{j, c[j]}, {j, 1, 64}]

[ Voor 6% gewijzigd door FCA op 04-12-2002 13:32 . Reden: lay-out aangepast ]

[FCA]

Voor de geinteresseerden: de afwijking van c(q) met n+m-2, gedefinieerd door LD


{{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}, {7, 0}, {8, 0}, {9, 0}, {10, 0}, {11, 0}, {12, 0}, {13, 0}, {14, 0}, {15, -1}, {16, 0}, {17, 0}, {18, 0}, {19, 0}, {20, 0}, {21, 0}, {22, 0}, {23, -1}, {24, 0}, {25, 0}, {26, 0}, {27, -1}, {28, 0}, {29, 0}, {30, -1}, {31, -1}, {32, 0}, {33, 0}, {34, 0}, {35, 0}, {36, 0}, {37, 0}, {38, 0}, {39, -1}, {40, 0}, {41, 0}, {42, 0}, {43, -1}, {44, 0}, {45, -1}, {46, -1}, {47, -1}, {48, 0}, {49, 0}, {50, 0}, {51, -1}, {52, 0}, {53, 0}, {54, -1}, {55, -1}, {56, 0}, {57, 0}, {58, 0}, {59, -1}, {60, -1}, {61, -1}, {62, -1}, {63, -2}, {64, 0}, {65, 0}, {66, 0}, {67, 0}, {68, 0}, {69, 0}, {70, 0}}


Verder LD zul je 8! mogelijkheden niet op een zondagmiddag uitwerken, aangezien 8! = 40320....

[ Voor 7% gewijzigd door FCA op 04-12-2002 13:51 ]

[Lord Daemon]

FCA schreef op 04 December 2002 @ 13:50:
Verder LD zul je 8! mogelijkheden niet op een zondagmiddag uitwerken, aangezien 8! = 40320....

Ik denk dat ik het met wat slimme gedachten toch wel kan in een middagje, hoor. Je hoeft namelijk lang niet al die rijtjes te maken. Maar ik ga het niet uitproberen.

Overigens laat jouw schema zien dat ik maar 7! rijtjes zou hoeven doen, dus dat is mooi.

[FCA]

Hmm... OK, ik heb weer wat interessante dingen:
Als c(p)<m+n-2, dan is c(2*p) ook< m + n - 2 en c(2*p +1) en ook. Algemener
Als c(p) = m + n - 2 - h , dan is c(2^k * p) < m + n - 2 - h en c(2^k * p + g) < m + n - 2 - h
Waarin g < 2^k
Zo krijg je series achter elkaar waarvoor de waarde can c(p) lager is dan je op grond van het m + n - 2 criterium verwacht.
Nu nog een methode vinden waarvoor de starters van zulke series vallen uit te rekenen.

[Anoniem: 27677]

kan iemand de vragen misschien even helemaal uitwerken! heel graag! want dan haal ik morgen ook nog een beetje ene goed cijfer voor m'n po!(als po moeten we de wiskunde olympiade maken)

[Christiaan]

Anoniem: 27677 schreef op 05 december 2002 @ 18:54:
kan iemand de vragen misschien even helemaal uitwerken! heel graag! want dan haal ik morgen ook nog een beetje ene goed cijfer voor m'n po!(als po moeten we de wiskunde olympiade maken)

W&L is niet 'voor al uw schoolvereisten' .

Maar even serieus; dit is nu al de derde post die je hebt gepost met de vraag of W&L-ers een wiskunde probleem voor je op kunnen lossen (of over iets gerelateerds - zoals luchtweerstand bij golfballen) dat je voor school moet doen. Het is niet echt de bedoeling om W&L daarvoor te gebruiken eigenlijk

[ Voor 37% gewijzigd door Christiaan op 05-12-2002 18:57 ]

[Anoniem: 27677]

ChristiaanVerwijs schreef op 05 December 2002 @ 18:56:
[...]


W&L is niet 'voor al uw schoolvereisten' .

Maar even serieus; dit is nu al de derde post die je hebt gepost met de vraag of W&L-ers een wiskunde probleem voor je op kunnen lossen (of over iets gerelateerds - zoals luchtweerstand bij golfballen) dat je voor school moet doen. Het is niet echt de bedoeling om W&L daarvoor te gebruiken eigenlijk

ja, maar toch hier kan toch sowieso niemand mee praten die het niet voor zich heeft gezien.. er is in 2 regels de opdracht uit gelegd.. terwijl er in totaal 12 vragen zijn..dan kun je toch niet mee praten als je het nog nooit hebt gezien...en 1tje over golfballen was fout die is ook gesloten. de 2e is gewoon een mooie discussie uitgekomen en was niet voor school...
maar goed even ontopic dan: ik denk niet dat ik het antwoord op de vraag voor jullie kan uitkoken...zo goed?

[Virgol]

Nee het uitwerken van de vragen laat ik graag aan jou over

Gready bovengrens:

code:

gc[x_] := 2*DigitCount[x, 2][[1]] + DigitCount[x, 2][[2]] - 2

{{1, 0}, {2, 1}, {3, 2}, {4, 2}, {5, 3}, {6, 3}, {7, 4}, {8, 3}, { 9, 4}, {10, 4}, {11, 5}, {12, 4}, {13, 5}, {14, 5}, {15, 6}, {16, 4}, {17, 5}, {18, 5}, {19, 6}, {20, 5}, {21, 6}, { 22, 6}, {23, 7}, {24, 5}, {25, 6}, {26, 6}, {27, 7}, {28, 6}, {29, 7}, { 30, 7}, {31, 8}, {32, 5}, {33, 6}, {34, 6}, {35, 7}, {36, 6}, {37, 7}, {38, 7}, {39, 8}, {40, 6}, {41, 7}, {42, 7}, {43, 8}, {44, 7}, {45, 8}, { 46, 8}, {47, 9}, {48, 6}, {49, 7}, {50, 7}, {51, 8}, {52, 7}, {53, 8}, { 54, 8}, {55, 9}, {56, 7}, {57, 8}, {58, 8}, {59, 9}, {60, 8}, {61, 9}, {62, 9}, {63, 10}, {64, 6}, {65, 7}, {66, 7}, {67, 8}, {68, 7}, {69, 8}, {70, 8}, {71, 9}, {72, 7}, {73, 8}, {74, 8}, {75, 9}, {76, 8}, {77, 9}, {78, 9}, {79, 10}, {80, 7}, {81, 8}, {82, 8}, {83, 9}, {84, 8}, {85, 9}, {86, 9}, {87, 10}, {88, 8}, {89, 9}, {90, 9}, {91, 10}, {92, 9}, {93,10}, {94, 10}, {95, 11}, {96, 7}, {97, 8}, {98, 8}, {99, 9}, {100,}}

Factor bovengrens:

code:

f[x_] := Module[{tabel = {}, plijst = {}, i, fm = 0},
    If[x == 2, tabel = Append[tabel, 1],
      plijst = FactorInteger[x];
      If[(Length[plijst] == 1 ) && (plijst[[1, 2]] == 1), tabel = Append[
      tabel, f[x - 1] + 1],
        For[{i = 1}, i ≤ Length[plijst], i++,
          fm = fm + plijst[[i, 2]]*f[plijst[[i, 1]] ];
          ];
        tabel = Append[tabel, fm];
        ];];
    Min[tabel]
    ]

{{1, 0}, {2, 1}, {3, 2}, {4, 2}, {5, 3}, {6, 3}, {7, 4}, {8, 3}, { 9, 4}, {10, 4}, {11, 5}, {12, 4}, {13, 5}, {14, 5}, {15, 5}, {16, 4}, {17, 5}, {18, 5}, {19, 6}, {20, 5}, {21, 6}, { 22, 6}, {23, 7}, {24, 5}, {25, 6}, {26, 6}, {27, 6}, {28, 6}, {29, 7}, { 30, 6}, {31, 7}, {32, 5}, {33, 7}, {34, 6}, {35, 7}, {36, 6}, {37, 7}, {38, 7}, {39, 7}, {40, 6}, {41, 7}, {42, 7}, {43, 8}, {44, 7}, {45, 7}, {46, 8}, {47, 9}, {48, 6}, {49, 8}, {50, 7}, {51, 7}, {52, 7}, {53, 8}, {54, 7}, {55, 8}, {56, 7}, {57, 8}, {58, 8}, {59, 9}, {60, 7}, {61, 8}, { 62, 8}, {63, 8}, {64, 6}, {65, 8}, {66, 8}, {67, 9}, {68, 7}, {69, 9}, {70, 8}, {71, 9}, {72, 7}, {73, 8}, {74, 8}, {75, 8}, {76, 8}, {77, 9}, { 78, 8}, {79, 9}, {80, 7}, {81, 8}, {82, 8}, {83, 9}, {84, 8}, {85, 8}, {86, 9}, {87, 9}, {88, 8}, {89, 9}, {90, 8}, {91, 9}, {92, 9}, {93, 9}, {94, 10}, {95, 9}, {96, 7}, {97, 8}, {98, 9}, {99, 9}, {100, 8}}

Het hinderlijkste vind ik nog dat ik geen enkele manier heb kunnen verzinnen om de bovengens van 23 nog lager te krijgen. 33,66 en 65,130 enzo kun je nog omlaag krijgen door het mixen van bijde bovengrenzen maar voor priemgetallen zit ik nog echt vast..

[Virgol]

Gready en Factor methoden samen:

code:

f3[x_] := Module[{tabel = {}, plijst = {}, i, fm = 0, j, plijst2 = {}, a, b},
    If[x == 2, tabel = Append[tabel, 1],
      plijst = FactorInteger[x];
      For[
    i = 1, i ≤ Length[plijst], i++, For[j =
         1, j ≤ plijst[[i, 2]], j++, plijst2 = Append[
      plijst2, plijst[[i, 1]]]]];
      If[Length[plijst2] < 8,
        tabel = Append[tabel, gc[x]];
        If[(Length[plijst2] == 1 ), tabel = Append[tabel, f3[x - 1] + 1],
          For[i = 1 , i &#8804; (2^(Length[plijst2] - 1) - 1), i++,
              For[a = 1; b = 1; j = 1, j &#8804; Length[IntegerDigits[1, 2, Length[
      plijst2]]], j++,
                If[IntegerDigits[i, 2, Length[
        plijst2]][[j]] == 1, a = a*plijst2[[j]], b = b*plijst2[[j]]]
                ];
              tabel = Append[tabel, f3[a] + f3[b] ];
              ];
          ], tabel = Append[tabel, -100]];
      ];
    Min[tabel]
    ]

{{1, 0}, {2, 1}, {3, 2}, {4, 2}, {5, 3}, {6, 3}, {7, 4}, {8, 3}, { 9, 4}, {10, 4}, {11, 5}, {12, 4}, {13, 5}, {14, 5}, {15, 5}, {16, 4}, {17, 5}, {18, 5}, {19, 6}, {20, 5}, {21, 6}, { 22, 6}, {23, 7}, {24, 5}, {25, 6}, {26, 6}, {27, 6}, {28, 6}, {29, 7}, {30, 6}, {31, 7}, {32, 5}, {33, 6}, {34, 6}, {35, 7}, {36, 6}, {37, 7}, {38, 7}, {39, 7}, {40, 6}, {41, 7}, {42, 7}, {43, 8}, {44, 7}, {45, 7}, {46, 8}, {47, 9}, {48, 6}, {49, 7}, {50, 7}, {51, 7}, {52, 7}, {53, 8}, {54, 7}, {55, 8}, {56, 7}, {57, 8}, {58, 8}, {59, 9}, {60, 7}, {61, 8}, {62, 8}, {63, 8}, {64, 6}, {65, 7}, {66, 7}, {67, 8}, {68, 7}, {69, 8}, {70, 8}, {71, 9}, {72, 7}, {73, 8}, {74, 8}, {75, 8}, {76, 8}, {77, 9}, {78, 8}, {79, 9}, {80, 7}, {81, 8}, {82, 8}, {83, 9}, {84, 8}, {85, 8}, {86, 9}, {87, 9}, {88, 8}, {89, 9}, {90, 8}, {91, 9}, {92, 9}, {93, 9}, {94, 10}, {95, 9}, {96, 7}, {97, 8}, {98, 8}, {99, 8}, {100, 8}}

Helaas gaat het nog steeds fout voor priemgetallen zoals 23

[FCA]

Dat komt waarschijnlijk omdat de de reeks voor 23 zo raar is opgebouwd:
1 - 2 - 4 - 5 - 9 - 18 - 23

Hoe lang duurt dit rekenwerk eigenlijk bij jou? (ik heb even geen Mathematica tot m'n beschikking)
Misschien is het trouwens ook een optie om bij een brute-force na elke reeksuitbreiding (dus als de c(n) 1tje omhoog gaat) alle sub-optimale reeksen (waarvoor lengte(n) > c(n) is) weg te laten gooien. Scheelt misschien een hele zooi rekenwerk, maar ik moet nog bewijzen dat ie dan niet essentiele reeksen weggooit. (anders gezegd, geldt voor elke deelreeks van een optimale reeks dat het een optimale reeks is? )

[Anoniem: 27677]

nou ik had hem dus ook eindelijk vandaag... misschien te makkelijk gedacht, maar wij hadden voor even getallen
c(2n)=c(a) + c(b) + 1 als n=a*b voor even getallen
c(0.5n)=c(a) + c(b) - 1 als n=a*b voor oneven, maar geen priem
en c(n)=2logn voor tweemachten

en we kwamen bij 8127 daar bij uit op c(8127)= 16
op dit getal kwamen we ook uit met de factoor manier ofzow, kwete niet meer hoe ie heet

voor priem getallen dus nog nix bedacht

[ Voor 6% gewijzigd door Anoniem: 27677 op 06-12-2002 23:58 ]

[FCA]

Ik snap je uitwerking niet helemaal?
Je zegt c(0.5n)= c(a) + c(b) - 1 als n=a*b en n oneven, maar niet priem, maar dan is 0.5n geen geheel getal.

[Lord Daemon]

Anoniem: 27677 schreef op 06 December 2002 @ 23:47:
c(2n)=c(a) + c(b) + 1 als n=a*b voor even getallen

Dat klopt niet. Neem n = 33. Dan geldt dat c(2n) = c(66) =< c(33) + 1 = 7

Maar volgens jouw formule, met a = 3 en b = 11:

c(66) = c(3) + c(11) + 1 = 2 + 5 + 1 = 8

Dus dat klopt niet, want 8 =< 7 geldt natuurlijk niet.

[Anoniem: 27677]

FCA schreef op 07 december 2002 @ 00:09:
Ik snap je uitwerking niet helemaal?
Je zegt c(0.5n)= c(a) + c(b) - 1 als n=a*b en n oneven, maar niet priem, maar dan is 0.5n geen geheel getal.

waar staat dat n oneven moet zijn? ik zeg alleen dat 0,5n on even is... althans dat bedoelde ik

[Anoniem: 27677]

Wat hier stond klopte niet

lord deamon je hebt gelijk, het viel ons ok al op dat voor opvolgers van 11( ik bedoel... 11,22,33,44 enzo.. er verkeerde antwoorden uitkomen, we zijn dit alleen vergeten te zeggen bedenk ik me nu! ..dus we zulleen helaas die rij ook moeten uitsluiten... maar voor de REST , is ie volgens mij wel sluitend.... haha...blijft niet veel over, maar toch..
heeft dat 22, 33 enzo er misschien mee te maken, dat dat allene uit het priemgetal 11 kan worden gemaakt door te vermenig vuldigen.. en dat het daardoor niet klopt?

[ Voor 210% gewijzigd door Anoniem: 27677 op 07-12-2002 01:04 ]

[Lord Daemon]

Anoniem: 27677 schreef op 07 December 2002 @ 00:42:
Wat hier stond klopte niet

lord deamon je hebt gelijk, het viel ons ok al op dat voor opvolgers van 11( ik bedoel... 11,22,33,44 enzo.. er verkeerde antwoorden uitkomen, we zijn dit alleen vergeten te zeggen bedenk ik me nu! ..dus we zulleen helaas die rij ook moeten uitsluiten... maar voor de REST , is ie volgens mij wel sluitend.... haha...blijft niet veel over, maar toch..
heeft dat 22, 33 enzo er misschien mee te maken, dat dat allene uit het priemgetal 11 kan worden gemaakt door te vermenig vuldigen.. en dat het daardoor niet klopt?

Het heeft er mee te maken dat de complexiteit van 33 niet gelijk is aan de som van de complexiteiten van zijn priemdelers. Voor elk getal waarvoor dat geldt (en ik ben bang dat dat er veel zijn) gaat jouw formule niet op... (Je formule geeft trouwens wel een accurate bovengrens.)

[ Voor 4% gewijzigd door Lord Daemon op 07-12-2002 01:09 ]

[Anoniem: 27677]

jah nee ok, maar dat d8 ik, verder is ie wel heel goed! nu nog iets voor priemgetallen, en die etter getallen als 33 en 66 enzo... die mogen jullie voor me doen
want jullie maken wel mooi die proggie's, maar het gaat om de formule!
hoe maken jullie trouwens dat factoor proggie, want we hadden wel voro vremeningvuldigins ding, maar niet voor die andere, want dat kost nog al wat tijd en computer kracht

[ Voor 43% gewijzigd door Anoniem: 27677 op 07-12-2002 18:11 ]

[Virgol]

Het resultaat van een middagje brute forcen

{2,1}{3,2}{4,2}{5,3}{6,3}{7,4}{8,3}{9,4}{10,4}{11,5}{12,4}{13,5}{14,5}{15,5}{16,4}{17,5}{18,5}{19,6}{20,5}{21,6}{22,6}{23,6}{24,5}{25,6}{26,6}
{27,6}{28,6}{29,7}{30,6}{31,7}{32,5}{33,6}{34,6}{35,7}{36,6}{37,7}{38,7}{39,7}{40,6}{41,7}{42,7}{43,7}{44,7}{45,7}{46,7}{47,8}{48,6}{49,7}
{50,7}{51,7}{52,7}{53,8}{54,7}{55,8}{56,7}{57,8}{58,8}{59,8}{60,7}{61,8}{62,8}{63,8}{64,6}{65,7}{66,7}{67,8}{68,7}{69,8}{70,8}{71,9}{72,7}
{73,8}{74,8}{75,8}{76,8}{77,8}{78,8}{79,9}{80,7}{81,8}{82,8}{83,8}{84,8}{85,8}{86,8}{87,9}{88,8}{89,9}{90,8}{91,9}{92,8}{93,9}{94,9}{95,9}
{96,7}{97,8}{98,8}{99,8}{100,8}{101,9}{102,8}{103,9}{104,8}{105,9}{106,9}{107,9}{108,8}{109,9}{110,9}{111,9}{112,8}{113,9}{114,9}{115,9}
{116,9}{117,9}{118,9}{119,9}{120,8}{121,9}{122,9}{123,9}{124,9}{125,9}{126,9}{127,10}{128,7}{129,8}{130,8}{131,9}{132,8}{133,9}{134,9}{135,9}
{136,8}{137,9}{138,9}{139,10}{140,9}{141,10}{142,10}{143,10}{144,8}{145,9}{146,9}{147,9}{148,9}{149,9}{150,9}{151,10}{152,9}{153,9}{154,9}
{155,10}{156,9}{157,10}{158,10}{159,10}{160,8}{161,9}{162,9}{163,9}{164,9}{165,9}{166,9}{167,10}{168,9}{169,10}{170,9}{171,10}{172,9}{173,10}
{174,10}{175,10}{176,9}{177,10}{178,10}{179,10}{180,9}{181,10}{182,10}{183,10}{184,9}{185,10}{186,10}{187,10}{188,10}{189,10}{190,10}{191,11}
{192,8}{193,9}{194,9}{195,9}{196,9}{197,10}{198,9}{199,10}{200,9}{201,10}{202,10}{203,10}{204,9}{205,10}{206,10}{207,10}{208,9}{209,10}{210,10}
{211,10}{212,10}{213,10}{214,10}{215,10}{216,9}{217,10}{218,10}{219,10}{220,10}{221,10}{222,10}{223,11}{224,9}{225,10}{226,10}{227,10}{228,10}
{229,10}{230,10}{231,10}{232,10}{233,10}{234,10}{235,11}{236,10}{237,11}{238,10}{239,11}{240,9}{241,10}{242,10}{243,10}{244,10}{245,10}{246,10}
{247,11}{248,10}{249,10}{250,10}{251,11}{252,10}{253,11}{254,11}{255,10}{256,8}{257,9}{258,9}{259,10}{260,9}{261,10}{262,10}{263,11}{264,9}
{265,10}{266,10}{267,11}{268,10}{269,11}{270,10}{271,11}{272,9}{273,10}{274,10}{275,11}{276,10}{277,11}{278,11}{279,11}{280,10}{281,10}{282,11}
{283,11}{284,11}{285,11}{286,11}{287,11}{288,9}{289,10}{290,10}{291,10}{292,10}{293,10}{294,10}{295,11}{296,10}{297,10}{298,10}{299,11}{300,10}
{301,11}{302,11}{303,11}{304,10}{305,11}{306,10}{307,11}{308,10}{309,11}{310,11}{311,11}{312,10}{313,11}{314,11}{315,11}{316,11}{317,11}{318,11}
{319,11}{320,9}{321,10}{322,10}{323,10}{324,10}{325,10}{326,10}{327,11}{328,10}{329,11}{330,10}{331,11}{332,10}{333,11}{334,11}
{335,11}{336,10},{337,11}{338,11}{339,11}{340,10}

[Virgol]

Grmbl wat zuigt mathematica echt super traag....
Ben overgestapt naar delphi

8127 heeft inderdaat 16 stappen nodig

code:

type
  TLijst= Array[0..255] of integer;

function TForm1.bf(Const x,max:LongInt;Const a:TLijst):LongInt;
var
  i,max2 : LongInt;
  b : TLijst;
  s : string;
begin
  If a[a[0]]=x then
  begin
//    s := '';
//    For i := 1 to a[0] do s := s +' '+IntToStr(a[i]);
//    Memo1.Lines.add(IntToStr(a[0])+' '+s);
//    Memo1.Repaint;
    bf := a[0];
  end else begin
    If (a[0] > max) or (a[a[0]]>x) then bf := max
    else begin
      If (a[a[0]] shl (max-a[0]))<x then bf:=max
      else begin
        max2 := max;
        b := a;
        For i := a[0] downto 1 do begin
          b[0] := a[0]+1;
          b[b[0]] := b[b[0]-1]+b[i];
          max2 := bf(x,max2,b);
          If max2>max then max2:=max;
        end;
        bf := max2;
      end;
    end;
  end;
end;

function TForm1.Gready(x:Integer):integer;
var
  i : integer;
  bitcount : Integer;
begin
  i := 0;
  bitcount := 0;
  repeat
    if ((1 shl i) and x)=(1 shl i)then bitcount := bitcount+1;
    i := i + 1;
  until (1 shl i)>x;
  Gready := bitcount+i-2;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  a : TLijst;
begin
  ListBox1.Items.Clear;
  a[0] := 2;
  a[1] := 1;
  a[2] := 2;
  label1.caption := IntToStr(bf(SpinEdit1.Value,Gready(SpinEdit1.Value)+1,a)-1);
end;