Left

Adjust your browser window

Right

2009.gada rudens semestra nodarbību materiāli

 

18.decembrī

KP: mazliet nopucēju savu 13.novembra teorēmu, sk. zemāk. Varbūt, pavisam tukša tā tomēr nav?

Tāfeles bilde:

--------

--------

Jura vēstule 6.decembrī:

Sveiki!

Pirmkārt, nosūtu to tabulu par lielākajiem skaitļiem (tabula.doc) [Labojums! Hipotēzē par n-to lielāko skaitli rindā 3k+1 pareizi jābūt 3k-n+2 (3n-2+1).]
Otrkārt, kaut gan runājām, ka vismaz pagaidām nav vajadzības tabulu papildināt, es tomēr nenoturējos un parēķināju uz priekšu. Atceros, ka pirms kāda laika seminārā izskanēja tāda doma, ka varbūt tikai sākumā tur nav nekādu likumsakarību, bet vēlāk tomēr parādās. Liekas, ka tieši tā arī ir!
Eksperimentālo novērojumu rezultātā man izdevās izvirzīt hipotēzi par n-to lielāko skaitli. Nezinu, cik lielā mērā tā varētu būt patiesa pie lielākām n vērtībām, bet novērojumi rāda, ka tā ir. Hipotēze ir pievienotā faila beigās.
Beigās man ir lūgums! Vai kāds varētu atsūtīt pēc iespējas lielāku sarakstu ar skaitļiem, kuriem ir tikai viena īsākā izteiksme, jo gribētu pārbaudīt pāris idejas lielākā intervālā? Pietiktu, ja būtu visi skaitļi līdz 6*10^5, bet, protams, jo vairāk, jo labāk.

Ar cieņu,
Juris Čerņenoks



4.decembrī

Tāfeles bildes:

--------

--------

--------

--------

--------

--------

27.novembrī

Tāfeles bildes:

--------

--------

--------

20.novembrī

Tāfeles bildes:

--------

--------

--------

6.novembrī

KP vēstule 13.novembrī

Par 6.novembra lemmu. Tur bija nopietns defekts, kas visu ideju iznīcina.

|X| apzīmē skaitļa X īsākās izteiksmes garumu.

Ja X=aX+bX, tad |aX|>=3log3(aX), |bX|>=3log3(bX) un |aX|+|bX|>=3log3(abX2).Tātad, ja |X|<3log3(abXX), tad X=aX+bX nedos X īsāko izteiksmi. Citiem vārdiem:

Lemma 1. Ja 3|X| < (ab)3 X6, tad X=aX+bX nedos X īsāko izteiksmi.

6.novembrī man bija ab, nevis (ab)3, tur arī tas defekts.

Tā kā a, b >=1/X, tad (aptuveni) arī ab>=1/X un tātad:

Lemma 2. Ja 3|X| < X3, tad X=aX+bX nedos X īsāko izteiksmi.

Priekš X=2n mums |X|<=2n, tātad jāpierāda, ka 32n < 23n, jeb 9n < 8n, kas nav iespējams.

Sausais atlikums paliek:

Lemma 3. Ja X=aX+bX dod X īsāko izteiksmi, tad
(ab)
3 <= 3|X| / X6, jeb
(aX)b <= 3
|X|/3 / X, jeb
(aX)(bX) <= 3
|X|/3, jeb
aX(1-a) <= 3
|X|/3 / X jeb
aX(1-a) <= 3
|X|/3 / X jeb.

Priekš X=2n mums |X|<=2n, tātad (ab)3 <= 32n/26n = (9/64)n, tātad mazākais no a,b ir tuvu nullei, lielākais - tuvu 1. Liekot b=1:

(aX)b <= 3|X|/3 / X;
a2n <= 32n/3 / 2n <= 1,041n.

Teorēma. Ja 2n=A+B dod 2n īsāko izteiksmi, tad viens no saskaitāmajiem <=1,041n.

KP

Tāfeles bildes:

--------

--------

--------

--------

--------

30.oktobrī

Tāfeles bildes:

--------

--------

--------

--------

--------

--------

--------

23.oktobrī

Tāfeles bildes:

--------

-----------

------

------

------

9.oktobrī

Mārtiņa Opmaņa datnes: kopsavilk6.txt (3 MB), tg6.rar (30 MB)

Mārtiņa Opmaņa konspekts

Izmantojot iepriekš uzkrātos rezultātus (līdz 70640000), tika pārbaudītas grāmatā "R. K. Guy, Unsolved Problems in Number Theory. Second edition, Springer-Verlag, 1994, Problem F26." izvirzītās hipotēzes:

Ja p - pirmskaitlis un f(p) - vieninieku skaits īsākajā 1+* izteiksmē, tad f(p)=f(p-1)+1 un f(2p)=min(f(2p-1)+1,f(p)+2). Pagaidām šīs hipotēzes apstiprinās - t.i., nav pretpiemēru.

Izgāzās mana hipotēze, ka katram n,
f(n) = min(f(n-1)+1, f(n div n_mazākais_pirmreizinātājs)+f(n_mazakais_pirmreizinātājs)).
Pretpiemērs: 715 mazākais reizinātājs ir 5, bet f(143)+f(5) = f(13)+f(11)+f(5) = 8+8+5 = 21, savukārt f(55)+f(13) = (f(54)+1)+f(13) = 11+1+8 = 20.

Izgāzās arī otra hipotēze, ka f(x*3^k)=f(x)+3k.
Pretpiemērs: 321. f(107)+3 = 16+3 = 19, bet f(320)+1 = 17+1 = 18.

Pamatojoties uz iepriekšējā seminārā izvirzīto ideju, dotam n tika meklētas visas īsākās 1+* izteiksmes, kuru vērtība ir n.
Lai neģenerētu dublikātus, kas atšķiras tikai ar operandu secību, tika izvēleta pieeja, kas pieprasa, lai augšējā līmeņa operandi vienmēr būtu sakārtoti nedilstošā secībā - t.i., ja augšējā līmeņa izteiksme ir a1#a2#a3#...#ak, kur # ir + vai *, tad jāizpildās sakarībai: vērtība(a1)>=vērtība(a2)>=...>=vērtība(ak).
Aprēķini tika veikti bez īpašas optimizācijas, izķemmējot reizinātajus līdz kvadrātsaknei un saskaitāmos līdz pusei.
Paralēli vērtībai tika rēķināts arī mazakais iespējamais rangs izteiksmei ar vērtību n. Aprēķinu rezultāti līdz n=164965 ar izteiksmēm klasiskajā poļu pierakstā ir apkopoti failā tg6.
Failā kopsavilk6.rez ir dota tikai statistika bez pašām izteiksmēm.

Interesantākais novērojums: Vienlīdz labu izteiksmi garuma un ranga ziņā var iegūt divos dažādos reizinājumos, kur vienu reizinājumu nevar iegūt no otra, sadalot reizinātājus sīkāk un pārgrupējot:
49997 = 2941*17 = 289*173,
f(2941) = 25, f(289)=f(173)=17, f(17)=9, tāpēc f(49997)=25+9=17+17=34 (rangs abos gadījumos ir 6, kas ir mazākais iespējamais).
Ja tiktu izmantots "pilnais sadalījums reizinātājos" 17*17*173, tad rezultāts b?tu 9+9+17=35>34 .

Nobeigumā gribu piebilst, ka Mikus Grasmaņa izteiktais ieteikums rangu saistīt ar steka mašīnas izmantotās atmiņas daudzumu (steka izmēru) man šķiet absolūti ģeniāls, jo rangs mūsu izpratnē ir nepieciešamais_steka_izmērs-1 un tādejādi eleganti piešķir rangam jēgu.

M.O.

Tāfeles attēli:

-----

-----

------------