---

En hyggeopgave, til dem der keder sig.

<hyggeopgave>
Problem 1: Nine 9s

Combining nine 9s with any number of the operators +, -, *, /, (, ) , what
is the smallest positive integer that cannot be expressed?

Hints:
1)The answer isn't zero. You can express zero like this:
(9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
Also, zero isn't a positive integer.

2) The answer isn't one. You can express one like this:
9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9

3) It's not a trick question.

4) Be sure to handle parentheses correctly.

Notes:
You cannot exponentiate.
You cannot concatenate (for example, put two 9s together to make 99).
The - operator can be used in either its binary or unary form.
Assume base 10.
</hyggeopgave>

--
Jonas Kongslund <jonas(at)kongslund.dk> XNS: =Jonas Kongslund

When you want to change the world, you don't see the dawn by
getting up early - you see it by not sleeping through the night.

---

Scripsit Jonas Kongslund <gamma@post.tele.dk>

> En hyggeopgave, til dem der keder sig.

> Combining nine 9s with any number of the operators +, -, *, /, (, ) , what
> is the smallest positive integer that cannot be expressed?

Jeg har regnet og regnet, men efter at have fundet formler for alle
tal til og med 192 konkluderer jeg pr. induktion at samtlige naturlige
tal kan udtrykkes.

Man kunne fristes til at tro at dette er umuligt idet der kun er
endeligt mange forskellige udtryk, men idet det er tilladt at bruge
unært minus, kan man faktisk også lave uendeligt mange udtryk.

For at lave 138, 185 og 186 bliver jeg dog nødt til at have
ikke-hele mellemresultater, fx er 138 = 9 * (18 - (81-9)/27).
Er det tilladt?

> Assume base 10.

A'hva?


Hvis vi nu tillader ikke-hele resultater, hvad er så den bedste
tilnærmelse til pi man kan konstruere med ni nitaller?

--
Henning Makholm "PROV EN FORFRISKNING FRISKLAIL DEM"

---

Henning Makholm skrev:

> Hvis vi nu tillader ikke-hele resultater, hvad er så den bedste
> tilnærmelse til pi man kan konstruere med ni nitaller?

(9+9+9+9/9+(9/9)/9)/9 kommer ret tæt på: 3,1234567..., afvigelse
0,01813586

Thomas T.

---

Henning Makholm wrote:
> Jeg har regnet og regnet, men efter at have fundet formler for alle
> tal til og med 192 konkluderer jeg pr. induktion at samtlige naturlige
> tal kan udtrykkes.

Hvad med tallet 9*9*9*9*9*9*9*9*9+1? Min intuition siger mig at den ikke
kan konstrueres ud fra de gældende regler.

> Man kunne fristes til at tro at dette er umuligt idet der kun er
> endeligt mange forskellige udtryk, men idet det er tilladt at bruge
> unært minus, kan man faktisk også lave uendeligt mange udtryk.

Forklaring udbedes.

> For at lave 138, 185 og 186 bliver jeg dog nødt til at have
> ikke-hele mellemresultater, fx er 138 = 9 * (18 - (81-9)/27).
> Er det tilladt?

Jeg tror ikke det var hensigten, men siden der ikke står noget nævnt om
dette så står det dig frit for at gøre den antagelse.

>> Assume base 10.
> A'hva?

Opgaven må være stillet af en datalog

--
Jonas Kongslund <jonas(at)kongslund.dk> XNS: =Jonas Kongslund

When you want to change the world, you don't see the dawn by
getting up early - you see it by not sleeping through the night.

---

Henning Makholm <henning@makholm.net> writes:

> Man kunne fristes til at tro at dette er umuligt idet der kun er
> endeligt mange forskellige udtryk, men idet det er tilladt at bruge
> unært minus, kan man faktisk også lave uendeligt mange udtryk.

Jeg tror godt jeg kan sætte en øvre grænse for, hvor mange resultater
man kan få.

Først vælger jeg parenteserne i udtrykket. Det giver anledning til et
træ:

9 9 9 ... 9
\/ /
\ /
V ... /
\ /
\ /
V
resultat

Antallet af sådanne træer er et bestemt naturligt tal (niende
Catalantal, faktisk).

For at lave en formel skal man så vælge en komposition +,-,*,/ ved
hver forgrening i træet. Endvidere kan man indsætte unære minusser et
antal steder:

9 9 9
\ / /
"*" /
\ /
"+"

giver resultatet 90, hvorimod

9 9 9
\ / /
"*" "-"
\ /
"+"

giver 72. Men det er unødvendigt at indsætte mere end ét unært minus
på hver kant i træet. Så for hvert valg af træ samt operationer er der
højst 2^{antal kanter} måder at sætte unære minusser på.

Alt i alt bliver der kun endeligt mange mulige resultater.

--
Søren Galatius Smith http://www.imf.au.dk/~galatius/

---

Scripsit galatius+usenet@imf.au.dk (Søren Galatius Smith)
> Henning Makholm <henning@makholm.net> writes:

> > Man kunne fristes til at tro at dette er umuligt idet der kun er
> > endeligt mange forskellige udtryk, men idet det er tilladt at bruge
> > unært minus, kan man faktisk også lave uendeligt mange udtryk.

> Jeg tror godt jeg kan sætte en øvre grænse for, hvor mange resultater
> man kan få.

Selvfølgelig. Jeg forsøgte at være morsom (mest med min "induktive"
slutning), men det faldt vist lidt til jorden.

> Men det er unødvendigt at indsætte mere end ét unært minus
> på hver kant i træet.

Netop. Desuden behøver man heller ikke mere end et sæt parenteser for
hver gren i træet, så ialt kan ethvert udtryk let reduceres til et der
er højst 77 tegn langt - fra det endelige alfabet {+,-,*,/,(,),9}.

I øvrigt er det slet ikke nødvendigt at bruge unært minus overhovedet,
hvis man kun er ude efter positive resultater:

SÆTNING. Givet et aritmetisk udtryk U (med værdi u) opbygget af de
fire regningsarter, negation samt positive konstanter. Der findes
et udtryk U' (med værdi u') så
- u' = |u|
- konstanterne i U' er de samme (med multiplicitet) som dem i U
- ethvert deludtryk i U' har ikke-negativ værdi
(specielt har U' ingen ikke-trivielle negationer)

BEVIS. Uden tab af generalitet kan vi antage at U ikke indeholder
subtraktion idet a-b = a+(-b). Dernæst strukturel induktion over U:
1. U == konstant. Trivielt.
2. U == -V, U == V*W, U == V/W: simple anvendelser af induktionhypotsen.
3. U == W+V. Anvend induktionshypotesen på W og V. Alt efter værdierne
af W og V gælder en af
|w+v| = |w|+|v|
|w+v| = |w|-|v|
|w+v| = |v|-|w|
og U' kan konstrueres tilsvarende ud fra W' og V'

--
Henning Makholm "Nemo enim fere saltat sobrius, nisi forte insanit."

---

Et vilkårligt tal n kan udtrykkes som:
9-(9*9-9)/9 +
9-(9*9-9)/9 +
....
n styk
....
+9-(9*9-9)/9

---

Thomas Krog skrev:

> Et vilkårligt tal n kan udtrykkes som:
> 9-(9*9-9)/9 +
> 9-(9*9-9)/9 +
> ...
> n styk
> ...
> +9-(9*9-9)/9

Så bruger du mere end 9 9-taller.

Thomas T.

---

"Thomas Thorsen" <tt@thomasSLETDETTEthorsen.dk> wrote in message
news:EN4T7.10447$z4.1187852@news000.worldonline.dk...
> Thomas Krog skrev:
>
> > Et vilkårligt tal n kan udtrykkes som:
> > 9-(9*9-9)/9 +
> > 9-(9*9-9)/9 +
> > ...
> > n styk
> > ...
> > +9-(9*9-9)/9
>
> Så bruger du mere end 9 9-taller.

ups havde ikke læst opgaven ordentligt

---

Thomas Krog wrote:
>
> Et vilkårligt tal n kan udtrykkes som:
> 9-(9*9-9)/9 +
> 9-(9*9-9)/9 +
> ...
> n styk
> ...
> +9-(9*9-9)/9

eller måske lettere som: 9/9 + 9/9 + ... + 9/9.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jonas Kongslund <gamma@post.tele.dk> writes:

> En hyggeopgave, til dem der keder sig.
>
> <hyggeopgave>
> Problem 1: Nine 9s

51 - Hvis ellers mit program stemmer [Ja - jeg snød ].

for n 9 tal giver res (laveste positive hele tal der ikke kan dannes):

n| res
--------
1: 1
2: 2
3: 3
4: 5
5: 15
6: 24
7: 33
8: 42
9: 51
10: 104 [her holdt jeg op ... gad ikke at vente længere ]

Programmet kan iøvrigt ses på:
http://www.vindinggaard.dk/n9s2.py.html

--
Mvh. Kim Petersen /| Tlf: +4575831551 |\ Jomfru Ingefreds Vej 18
Software Engineer / | Fax: (none atm.) | \ 7100 Vejle
LSS / | Email: kim@vindinggaard.dk | \ DK - Danmark

---

Kim Petersen wrote:
> 51 - Hvis ellers mit program stemmer [Ja - jeg snød ].

51 = 9 * 9 - 9 - 9 - 9 - (9 + 9 + 9) / 9

--
Jonas Kongslund <jonas(at)kongslund.dk> XNS: =Jonas Kongslund

When you want to change the world, you don't see the dawn by
getting up early - you see it by not sleeping through the night.

---

Jonas Kongslund <gamma@post.tele.dk> writes:

> Kim Petersen wrote:
> > 51 - Hvis ellers mit program stemmer [Ja - jeg snød ].
>
> 51 = 9 * 9 - 9 - 9 - 9 - (9 + 9 + 9) / 9

Arrrgh!

Nu må jeg så se at finde ud af hvor f..... fejlen er

--
Mvh. Kim Petersen /| Tlf: +4575831551 |\ Jomfru Ingefreds Vej 18
Software Engineer / | Fax: (none atm.) | \ 7100 Vejle
LSS / | Email: kim@vindinggaard.dk | \ DK - Danmark

---

Jonas Kongslund <gamma@post.tele.dk> writes:

> Kim Petersen wrote:
> > 51 - Hvis ellers mit program stemmer [Ja - jeg snød ].
>
> 51 = 9 * 9 - 9 - 9 - 9 - (9 + 9 + 9) / 9

Fejlen rettet... jeg lavede ikke alle træerne:

n | res
--------
1 | 1
2 | 2
3 | 1 <-- her burde jeg have fanget fejlen.
4 | 5
5 | 15
6 | 24
7 | 33
8 | 123
9 | 195

nu er den desværre så langsom at jeg ikke orker at regne n=10 ud
html version: http://www.vindinggaard.dk/n9s3.py.html
python version: http://www.vindinggaard.dk/n9s3.py

Algoritme:

træ(dybde):
hvis dybde er 1:
resultat=[-9,9]
ellers:
resultat=[]
varier i fra 1 til dybde:
venstre=træ(i)
højre=træ(dybde-i+1)
for hvert element i venstre:
mellemres=beregn(element,højre)
udvid resultat med mellemres
returner resultat

beregn(konstant,liste):
returner en liste med konstanten (+,-,*,/) med hvert element i listen.

f.x: beregn(9,[-9,9]) -> [-81,-1,0,1,18,81]

--
Mvh. Kim Petersen /| Tlf: +4575831551 |\ Jomfru Ingefreds Vej 18
Software Engineer / | Fax: (none atm.) | \ 7100 Vejle
LSS / | Email: kim@vindinggaard.dk | \ DK - Danmark

---

Scripsit Kim Petersen <kim@vindinggaard.dk>

> nu er den desværre så langsom at jeg ikke orker at regne n=10 ud
> html version: http://www.vindinggaard.dk/n9s3.py.html
> python version: http://www.vindinggaard.dk/n9s3.py

Mit program fra i går i Standard ML findes på

http://www.diku.dk/~makholm/nitaller.sml

> træ(dybde):
....
> venstre=træ(i)
> højre=træ(dybde-i+1)

Argh! Det regner jo de samme mellemresultater ud mange gange. Mit
program bruger dynamisk programmering og kan nå de ni nitaller på
14 sekunder på den nærmeste linuxmaskine. Det gik en smule hurtigere
før jeg skrev det om til at foretrække "simple" former for samme facit
når der er flere at vælge imellem.

Der er ialt 35.330 forskellige ikke-negative facit (foruden "0/0", som
programmet lidt arbitrært bruger til at repræsentere formler der
dividerer med nul eller trækker store tal fra små).

Man kunne nok godt nå ti nitaller hvis ikke det var fordi jeg har
sprunget over hvor gærdet er lavest og brugt almindelige 32-bit
signed integers i stedet for bignums. Og 9^10 kan lige netop ikke
være under 2^31.

--
Henning Makholm "Al lykken er i ét ord: Overvægtig!"

---

On 16 Dec 2001 23:59:33 +0100
Kim Petersen <kim@vindinggaard.dk> wrote:
[snip]

> Programmet kan iøvrigt ses på:
> http://www.vindinggaard.dk/n9s2.py.html

jeg får en fejl i linje 20:

[kim@lifesuckz kim]$ python n9s.py
File "n9s.py", line 20
def __len__(self): return len(self.list)
^
IndentationError: unindent does not match any outer indentation level

forresten en ganske smart liste definition.
:wq
Kim Schulz


--
http://www.schulz.dk - En nørds bekendelser!
Nørdesnak, attitude og alverdens usexede nyheder for nørder

---

Kim Schulz <kim@schulz.dk> writes:

> On 16 Dec 2001 23:59:33 +0100
> Kim Petersen <kim@vindinggaard.dk> wrote:
> [snip]
>
> > Programmet kan iøvrigt ses på:
> > http://www.vindinggaard.dk/n9s2.py.html
>
> jeg får en fejl i linje 20:
>
> [kim@lifesuckz kim]$ python n9s.py
> File "n9s.py", line 20
> def __len__(self): return len(self.list)
> ^
> IndentationError: unindent does not match any outer indentation level

Du kan hente n9s.py ved at slette .html - der skulle indention gerne stemme.

http://www.vindinggaard.dk/n9s2.py.html

--
Mvh. Kim Petersen /| Tlf: +4575831551 |\ Jomfru Ingefreds Vej 18
Software Engineer / | Fax: (none atm.) | \ 7100 Vejle
LSS / | Email: kim@vindinggaard.dk | \ DK - Danmark

---

On 17 Dec 2001 00:17:30 +0100
Kim Petersen <kim@vindinggaard.dk> wrote:
[snip]
> Du kan hente n9s.py ved at slette .html - der skulle indention gerne
> stemme.

ja jeg opdagede også at det var copy-paste fra websiden der gav
problemer med identing. Det var dog kun 5-6 steder så det var hurtigt
rettet.

hvad gør denne linie ?
if __name__=="__main__":

Resten tror jeg godt jeg kan gennemskue uden at være haj til python

er det der __ __ måden hvor man tilgå klasser eller ?

MVH
Kim Schulz

--
http://www.schulz.dk - En nørds bekendelser!
Nørdesnak, attitude og alverdens usexede nyheder for nørder

---

Kim Schulz <kim@schulz.dk> writes:

> On 17 Dec 2001 00:17:30 +0100
> Kim Petersen <kim@vindinggaard.dk> wrote:
> [snip]
> > Du kan hente n9s.py ved at slette .html - der skulle indention gerne
> > stemme.
>
> ja jeg opdagede også at det var copy-paste fra websiden der gav
> problemer med identing. Det var dog kun 5-6 steder så det var hurtigt
> rettet.

Tænkte jeg nok - men jeg vidste ikke hvor mange der var

>
> hvad gør denne linie ?
> if __name__=="__main__":

standard linie - som sørger for at hvis du importer denne her - så bliver
resten ikke kørt. __name__ er navnet på aktuelt modul - hvis den er star-
tet fra kommandolinien hedder den "__main__". [smart måde at teste et lib
på f.eks.] equivalent til main() i C/C++.

>
> Resten tror jeg godt jeg kan gennemskue uden at være haj til python

hehe

>
> er det der __ __ måden hvor man tilgå klasser eller ?

__<metode>__ er overskrivninger af operatorer - f.eks: __add__(self,x)
vil blive kaldt når du adderer osv. Svarende til C++ operator+().

--
Mvh. Kim Petersen /| Tlf: +4575831551 |\ Jomfru Ingefreds Vej 18
Software Engineer / | Fax: (none atm.) | \ 7100 Vejle
LSS / | Email: kim@vindinggaard.dk | \ DK - Danmark

---

On 17 Dec 2001 01:23:01 +0100
Kim Petersen <kim@vindinggaard.dk> wrote:
> Jonas Kongslund <gamma@post.tele.dk> writes:
>
> > Kim Petersen wrote:
> > > 51 - Hvis ellers mit program stemmer [Ja - jeg snød ].
> >
> > 51 = 9 * 9 - 9 - 9 - 9 - (9 + 9 + 9) / 9
>
> Arrrgh!
>
> Nu må jeg så se at finde ud af hvor f..... fejlen er
>

kan du så samtidig ikke lige lave en option så man kan få printet
beregningerne ud: 0: (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9)
1: 9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9
....
så man man måske derfra udlede hvor fejlen ligger

:wq
Kim Schulz



--
http://www.schulz.dk - En nørds bekendelser!
Nørdesnak, attitude og alverdens usexede nyheder for nørder