2005/2006 gada sezona


Teorēma 1. Skaitļa N īsakā pirmā ranga pieraksta garums ir N.

Pierādījums. Pierakstā N=1+1+1+... ir N vieninieku. Q.E.D.

Teorēma 2A. Ja skaitlis N ir 1, 4 vai pirmskaitlis, tad tam neviens otrā ranga pieraksts nav īsāks par pirmā veida pierakstu.

Teorēma 2B. Ja skaitlis N nav 1, nav 4 un nav pirmskaitlis, tad tam eksistē otrā ranga pieraksts, kas īsāks par pirmā ranga pierakstu.

Dāvja Krastiņa teorēma. Jebkuram skaitlim N>1 visīsākais otrā ranga pieraksts ir iegūstams no tā sadalījuma pirmreizinātājos, katru pirmskaitli attēlojot pirmā ranga pierakstā. Piemēram, skaitļa 12 īsākais otrā ranga pieraksts ir 3*2*2=(1+1+1)*(1+1)*(1+1).

Pierādījums. Pieņemsim, ka N=AB, kur A=1+1+1+..., ir īsākais N otrā ranga pieraksts. Ja A nav 4 un nav pirmskaitlis, tad A eksistē īsāks otrā ranga pieraksts par 1+1+1+.... Ievietojot to A vietā, iegūsim vēl īsāku N otrā ranga pierakstu, kas nav iespējams. Tātad A=4 vai A – pirmskaitlis. Ja A=4, tad 2*2=(1+1)*(1+1) ir tikpat garš pieraksts kā 1+1+1+1, t.i. liekot to A vietā, mēs pierakstu nepagarināsim. Q.E.D.

Hipotēze. Visām divnieka pakāpēm 2n (n>0) neviens trešā ranga pieraksts nav īsāks par īsāko otrā ranga pierakstu (1+1)*(1+1)*...

Varbūt vismaz ŠO hipotēzi mēs spēsim pierādīt? Jo te nav runa, ka vispār neeksistē īsāks pieraksts, bet tikai trešā ranga pieraksts.

Par trijnieka pakāpēm 3n toreiz netika iedomāts nemaz!



2007.gada rudens semestris


Vispirms bija diskusija par Dāvja Krastiņa divus gadus veco hipotēzi: visām divnieka pakāpēm labākā trešā ranga izteiksme nav īsāka par labāko otrā ranga izteiksmi. Asoc.prof. Kārlis Čerāns apšaubīja, ka tā varētu būt patiesa, jo vajadzētu būt situācijām, kad 2n = 3m+K, kur K nav pārāk liels skaitlis, bet trijnieka pakāpes otrā ranga pierakstā attēlojas "ekonomiskāk" nekā divnieka pakāpes.

Tiešām, N=3m = (1+1+1)*(1+1+1)*..., t.i. šīs izteiksmes garums ir 3m, jeb 3log3N. Tai pat laikā divnieka pakāpēm N=2m sanāk: (1+1)*(1+1)*..., t.i. garums 2m, jeb 2log2N, kas ir lielāks par 3log3N. Pārliecināsimies par to: 2log2N > 3log3N = 3log32*log2N, jeb 2>3log32, un 32>23. Q.E.D.

Teorēma 3. Jebkuram naturālam skaitlim N, īsākās otrā ranga izteiksmes garums ir >= 3log3N.

Uzdevums. Pierādiet, ka ja N nedalās ar 3, tad īsākās otrā ranga izteiksmes garums >= 2log2N.

Vai šo uzdevumu mēs tagad prastu pierādīt?

Hipotēze 3A. Trijnieka pakāpēm labākā trešā ranga izteiksme nav īsāka par labāko otrā ranga izteiksmi (1+1+1)*(1+1+1)*...

Toreiz tā vēl netika pierādīta...



Mārtiņa Opmaņa eksperimentu rezultāti, attēlojot skaitļus ar visīsāko izteiksmi no 1, + un *.

Šis uzdevums atšķiras no mūsu "nereducējamo skaitļu teorijas", jo katram skaitlim tiek meklēta nevis īsākā otrā veida izteiksme, trešā veida izteiksme utt. bet absolūti visīsākā izteiksme no 1, + un *. Tāda k-nereducējamu skaitļu jēdziena te vairs nav, tā vietā katram skaitlim piekārto rangu - visīsākās izteiksmes "dziļumu". Piemēram, rangs(1)=0, rangs(2)=1 (jo 2=1+1), rangs(6)=2 (jo 6=(1+1+1)*(1+1) un īsāk nevar), utt.

Tā mums pirmo reizi parādījās jēdziens, kuru no tā laika esam pētījuši visvairāk. Un kuru, kā izrādās, bija pētījuši arī citi...

Par izteiksmju par garumiem (hipotēzes izvirzīšanā piedalījas arī Kārlis Čerāns un Jāņa Iraida programma). Mārtiņa pierādījums, ka vislielākais skaitlis, kam postfiksās [1,+,*]-izteiksmes garums nepārsniedz n, ir (to apzīmē kā funkciju g(n)):

Par izteiksmju rangiem. Mārtiņa programmas rezultāti: pirmais n, kam īsākās izteiksmes rangs ir k (šie dati sakrīt ar Jāņa programmas datiem, sk. zemāk):

k    n
------
0   1
1   2
2   6
3   7
4   14
5   23
6   86
7   179
8   538
9   1439
10   9566
11   21383
12   122847
13   777419
14   1965374
15   5230427
16   19860278
17   26489579

Rangs 18 pagaidām (kad ir "pārrakts" līdz 48690000) neatrodas.

Vēl viens Jāņa Iraida novērojums - ja x ir mazākais skaitlis, kura pierakstam vajadzīgi garums y, tad (aptuveni):
y = 3,3889ln(x)-0,0745 = 3,723log
3(x)-0,0745 = 2,349log2(x)-0,0745. [Par to nav jābrīnās, jo g(n)=h(n)3[n/3], kur h(n) pieņem tikai vērtības 1, 4/3 un 2.]

Tādu pat grafiku var uzzīmēt funkcijai "x ir mazākais skaitlis, kura pierakstam vajadzīga kārta y" (sk. tabulu). Vai mēs pratīsim atrast arī šai funkcijai kādu formulu?



Teorēma 3A. Skaitlim 3k (k>=1) īsākā izteiksme ir (1+1+1)*(1+1+1)*..., tās garums ir 3k, rangs 2.

Pierādījums. Saskaņā ar Mārtiņa teorēmu, vislielākais skaitlis, ko var attēlot ar izteiksmi garumā līdz 3k-1, ir 2*3k-1, kas ir mazāks par 3k. Tātad 3k nevar attēlot ar izteiksmi, kas īsāka par 3k . Q.E.D.

Teorēma 3B. Skaitlim 2*3k (k>=1) īsākā izteiksme ir (1+1)*(1+1+1)*..., tās garums ir 3k+2, rangs 2.

Pierādījums. Saskaņā ar Mārtiņa teorēmu, vislielākais skaitlis, ko var attēlot ar izteiksmi garumā līdz 3k+1, ir 4*3k-1, kas ir mazāks par 2*3k. Tātad 2*3k nevar attēlot ar izteiksmi, kas īsāka par 3k+2. Q.E.D.

Teorēma 3C. Skaitlim 4*3k (k>=1) īsākā izteiksme ir (1+1)*(1+1)*(1+1+1)*..., tās garums ir 3k+4, rangs 2.

Pierādījums. Saskaņā ar Mārtiņa teorēmu, vislielākais skaitlis, ko var attēlot ar izteiksmi garumā līdz 3k+3, ir 3*3k, kas ir mazāks par 4*3k. Tātad 4*3k nevar attēlot ar izteiksmi, kas īsāka par 3k+4. Q.E.D.

Teorēma 3D. Skaitlim 5*3k (k>=1) īsākā izteiksme ir (1+1+1+1+1)*(1+1+1)*..., tās garums ir 3k+5, rangs 2.

Pierādījums. Saskaņā ar Mārtiņa teorēmu, vislielākais skaitlis, ko var attēlot ar izteiksmi garumā līdz 3k+4, ir 4*3k, kas ir mazāks par 5*3k. Tātad 5*3k nevar attēlot ar izteiksmi, kas īsāka par 3k+5. Q.E.D.

Teorēma 3X (Rihards). Ja 0<=a<=10, un skaitlis 2a*3b nav mazāks par 6, īsākā izteiksme ir (1+1)*...*(1+1+1)*..., tās garums ir 2a+3b, rangs 2.

Pierādījuma piemērs. Skaitlim 210*3b izteiksme ir (1+1)*(1+1)*... *(1+1+1)*(1+1+1)*..., tās garums ir 20+3b. Saskaņā ar Mārtiņa teorēmu, vislielākais skaitlis, ko var attēlot ar ar izteiksmi garumā līdz 19+3b=3(b+5)+4, ir 4*3b+5 = 4*243*3b = 972*3b, kas ir mazāks par 1024*3b. Tātad 210*3b nevar attēlot ar izteiksmi, kas īsāka par 20+3b. Q.E.D.

Teorēma 3Y. Skaitļiem 2a*3b*5 (a=1,2,3) īsākās izteiksmes ir 2,3,5 reizinājumi, to garumi ir 2a+3b+5, rangs 2.

Jāņa Iraida 2007.gada 29.oktobra vēstule:

"Ja pareizi atceros, Mārtiņa Opmaņa hipotēze bija, ka visi tie un tikai tie skaitļi, kuru pirmreizinātāji ir tikai 2, 3 vai 5 tālak par otro kārtu nereducējas. Tā nav patiesa. Interesanti, ka līdz miljonam hipotēzi apgāza tikai skaitļi 56 * 2a * 3b * 5c.kur a, b, c = 0... Respektīvi, 56 var vēl noreducēt 5. kārtā, savukārt pārejos var noreducēt 6.kārtā (tā ir reizināšana), kur acīm redzot viens reizinātājs ir 56. Viens variants īsāks par 30 vieniniekiem ir

56 = (1 + 1)3 * (1 + 1 + 1)2 * ((1 + 1)3 * (1 + 1 + 1)3 + 1) + 1,

kurš sastāv no 29 vieniniekiem."

56 =15625=1+23 *32 *217=1+23 *32 *(1+23 *33), garums 29, rangs 5.

Teorēma 4A (Rihards). Visi 2.ranga skaitļi ir izsakāmi formā 2a*3b*5c, t.i. 2.ranga skaitļi nedalās ar pirmsskaitļiem, lielākiem par 5.

Pierādījums. Pirmskaitlis p, kas lielāks par 5, ir attēlojams kā p=(1+1)*(1+1+...)+1, kur vieninieku skaits ir 2+(p-1)/2+1, kas ir mazāks nekā p (jo p>5). Tātad, ja skaitlis N dalās ar p, tad tā labāko otrā ranga izteiksmi (pirmskaitļu reizinājumu) var saīsināt, p vietā ieliekot minēto izteiksmi. Rezultātā skaitlim N radīsies trešā ranga izteiksme, kas īsāka par labāko otrā ranga izteiksmi. Q.E.D.

Teorēma 4B. Ja c>=6, tad 2a*3b*5c NAV 2.kārtas skaitlis.

Pierādījums. Kā jau Jānis bija pamanījis, skaitlim 56 = 15625 bez otrā veida izteiksmes (1+1+1+1+1)*..., kuras garums ir 30, ir īsāka piektā veida izteiksme 56 = 1+23*32*217 = 1+23*32*(1+23*33)) – tās garums ir 29 (ļoti smalks novērojums!). Tātad, ja skaitlis N dalās ar 56, tad tā labāko otrā ranga izteiksmi (pirmskaitļu reizinājumu) var saīsināt, 56 vietā ieliekot minēto izteiksmi. Q.E.D.

Ģenerālā Hipotēze. N ir otrā ranga skaitlis (t.i. tā īsākā izteiksme ir pirmskaitļu reizinājums) tad un tikai tad, ja N>=6, N=2a*3b*5c, kur c<=5. Īsākās izteiksmes garums tad ir 2a+3b+5c, rangs 2.

Vislielākais izaicinājums, protams, ir gadījums b=c=0: vai 2n īsākā izteiksme tiešām ir (1+1)*(1+1)*...?

Pierādīta šī hipotēze mums ir priekš: (c=0, a=0, 1,2, ..., 10) un (c=1, a=0, 1, 2, 3).



2008.gada pavasara semestris



Mārtiņa hipotēze: ja skaitļa n īsākajā [1,+,*]-izteiksmē augšējā ("ārējā") operācija ir saskaitīšana, tad vismaz vienā no šīm īsākajām izteiksmēm kāds no saskaitāmajiem ir 1: n = (n-1)+1.

Mārtiņa vēstule 2008.gada 25.februārī

Sveiki!

Ko dators ir iespējis starpsesiju pārtraukumā "1+*" izteiksmju jomā:

Ir skrupulozi pārbaudītas vērtības līdz 47700000, meklējot īsāko iespējamo izteiksmi. Ja dažādām izteiksmēm garumi bija vienādi, tad tika ņemta tā, kas ir ar mazāku rangu (+* koka dziļumu).

Labās ziņas: Visas vērtības formā 2a*3b*5c, kur c<6, tiešām ir 2.ranga izteiksmes (izņēmumi ir 4 un 5, kas ir pirmā ranga izteiksmes).

Ir atradusies viena vērtība, kurai labākā izteiksme ir iegūstama, piecreiz pēc kārtas pielietojot "+1":
21080617 (rangs 5, garums 54).
Ja necenstos pēc labākā ranga, bet skatītos tikai garumu, tad šī sērija pārtrūktu pie trim secīgiem "+1", jo 21080616 var iegūt ar "*2" ar to pašu kopgarumu.

Ir atradušās četras vērtības, kur labākā izteiksme beidzas ar "+6" (jeb +2*3) :
 22697747 (5,55)
 31288319 (7,57)
 37419479 (7,57)
 38441122 (5,55)
Visos četros minētajos gadījumos nostrādāja "ranga uzlabošana" - t.i. izteiksmi ar šādu pat garumu ir iespējams iegūt ar "+1", bet rangs būtu lielāks.

Priecē, ka lielākus reizinājumus kā beidzamo saskaitāmo nav bijis izdevīgi pielietot.

Līdz ar to varētu uzturēt spēkā hipotēzi par "+1" pietiekamību, ja neskatās uz mazāko rangu,  bet tikai garumu,  vai arī  papildināt iespējamo saskaitāmo klāstu ar  "+6" . Otrais rezultāts, protams, būtu skaistāks.



Būtu jāinventarizē arī rezultāti 4 kvadrātu problēmā. Riharda rezultāti 2008 pavasara semestrī ir ļoti iespaidīgi!



2009.gada rudens semestris



Mārtiņa Opmaņa konspekts 2009.gada 9.oktobrī.

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.

[2010.gada 10.martā Jānis atrada info, ka pirmā no šīm hiptēzēm ir apgāžama: Ja p=353 942 783 (tas ir pirmskaitlis), tad f(p)<f(p-1)+1 (Martin Fuller). Tas esot mazākais pretpiemērs hipotēzei, ka f(p)=f(p-1)+1 visiem pirmskaitļiem p. Sk. http://www.research.att.com/~njas/sequences/a005245.c.txt. Te ir arī Fullera programms teksts, kas rēķina f(n), jeb A005245.]

...

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.



23.oktobra tāfeles bildē redzam, ka izmantojot hipotēzi par otriem lielākajiem skaitļiem, varētu Ģenerālo Hipotēzi pierādīt priekš: (c=2, a=0, 1, 2, 3), t.i. skaitļiem 3b52 , 213b52, 223b52, 23*3b52.

Agrāk šī hipotēze mums bija pierādīta (un bez kādām hipotēzēm) priekš: (c=0, a=0, 1,2, ..., 10) un (c=1, a=0, 1, 2, 3).



log3(2) = 0,6309; 1/log3(2) = log2(3) = 1,5850

Teorēma: 3log3(N) <=f(N)<= 3log2(N)=4,7549log3(N). Apakšējo robežu sasniedz trijnieka pakāpes.

Divnieka pakāpēm (hipotēze): f(N)=2log2(N)=3,1699log3(N).



Sausais atlikums no 6.novembra ilūzijām:

Lemma. Ja N=A+B ir skaitļa N īsākā izteiksme bāzē {1, +, *}, tad AB<=3f(N)/3.

Pierādījums. f(N)=f(A)+f(B)>=3log3A+3log3B=3log3(AB). Q.E.D.

Secinājums 1. Ja N=A+B ir skaitļa N īsākā izteiksme bāzē {1, +, *}, tad AB<=Nlog2(3)<N1,5851.

Pierādījums. f(N)<=3log2N=3log2(3)log3(N), tālāk - lemma. Q.E.D.

Secinājums 2 (iegūts 2010.gada 22.februāra nodarbībā). Ja N=A+B ir skaitļa N īsākā izteiksme bāzē {1, +, *}, tad mazākais no saskaitāmajiem A, B nepārsniedz aptuveni N0,5851.

Pierādījums. Ja AB=A(N-A)<=C, tad A<=2C/(N+sqrt(N2-4C)), kas ir aptuveni C/N (ja C ir mazs pret N). Q.E.D.



4.decembrī Juris prezentēja savus eksperimentālos datus par 4-to, 5-to, ..., 9-to lielāko skaitli, ko var attēlot ar bāzes {1, +, *} izteiksmi, ne garāku par n.

Kopā ar mūsu agrāk iegūtajiem datiem, sanāk šāda hipotēžu tabula:



Izteiksmes garums

1.lielākais
(teorēma)

2. lielākais
(hipotēze)

3. lielākais
(hipotēze)

4. lielākais
(hipotēze)

5. lielākais
(hipotēze)

3k+1

22*3k-1

25*3k-3

2*3k-2*5

(k>=3)

28*3k-5

22*3k-3*7

(k>=5)

3k+2

2*3k

24*3k-2

3k-1*5

(k>=2)

27*3k-4

2*3k-2*7

(k>=4)

3k+3

3*3k

23*3k-1

26*3k-3

3k-1*7

(k>=3)

22 *3k-2*5

(k>=3)

---

Izteiksmes garums

6. lielākais
(hipotēze)

7. lielākais
(hipotēze)

8. lielākais
(hipotēze)

9. lielākais
(hipotēze)

10. lielākais
(hipotēze)

3k+1

2*3k-4*41

(k>=5)

22*3k-5*61

2*3k-6*5*73

22*3k-7*547

2*3k-8*17*193

3k+2

23*3k-3*5

(k>=4)

3k-2*13

(k>=4)

2*3k-3*19

(k>=4)

210 *3k-6

24*3k-4*7

(k>=6)

3k+3

3k-2*19

(k>=3)

29 *3k-5

23 *3k-3*7

(k>=5)

3k-3*5*11

(k>=5)

22*3k-4*41

(k>=5)



Uz šo datu pamata Juris izvirza šādu hipotēzi:

1) Ja n>=7, tad n-tais lielākais skaitlis, kura izteiksmes garums nepārsniedz (vai: vienāds ar?) 3k+1, ir 3k-n+2 (3n-2+1).

2) Ja n>=16, tad n-tais lielākais skaitlis, kura izteiksmes garums nepārsniedz (vai: vienāds ar?) 3k+2, ir:

ja n=3m-2, tad 3k-m(4*3m-1+4);

ja n=3m, tad 3k-m(4*3m-1+2);

ja n=3m+2, tad 3k-m(4*3m-1+1) (k>=m+1).

3) Ja n>=12, tad n-tais lielākais skaitlis, kura izteiksmes garums nepārsniedz (vai: vienāds ar?) 3k+3, ir:

ja n=2m, tad 3k-m+1*2(3m-1+1);

ja n=2m+1, tad 3k-m+1(2(3m-1+1)-1).



Turpinājums sekos.