Experimental mathematics at the University of Latvia

Online calculator of ||N|| up to 10^12: http://expmath.lumii.lv/wiki/index.php/Special:Complexity

Some publications

Harry Altman and Joshua Zelinsky. Numbers With Integer Complexity Close to the Lower Bound. INTEGERS, The John Selfridge Memorial Volume, Vol. 12A (2012) (preprint available online)

Continue at http://www-personal.umich.edu/~haltman/

J. Cernenoks, J. Iraids, M. Opmanis, R. Opmanis, K. Podnieks. Integer Complexity: Experimental and Analytical Results II. Proceedings of 17th International Workshop Descriptional Complexity of Formal Systems, DCFS 2015, Waterloo, Canada, June 25-27, 2015, Lecture Notes in Computer Science, Vol. 9118, Springer, 2015, pp. 58–69. DOI: 10.1007/978-3-319-19225-3_5 (preprint available online)

J. Iraids, K. Balodis, J. Cernenoks, M. Opmanis, R. Opmanis, K. Podnieks. Integer Complexity: Experimental and Analytical Results. Scientific Papers University of Latvia, Computer Science and Information Technologies, Vol. 787, 2012, pp. 153-179 (available online)

Eksperimentālā matemātika - tā ir dabas pētīšana.
Tikai šī daba atrodas mūsu datoros... (vairāk...)

Specseminārs datorzinātnē

Piektdienās, 16:30, LU MII 210.aud.

Last update 18.04.2015 8:45

Interesenti drīkst pieteikties jebkurā brīdī (var sākt ar e-pastu vai kā savādāk).
Lūdzu sūtīt e-pastu Karlis.Podnieks@lu.lv kā arī sk. podnieks.id.lv/.

Šībrīža dalībnieku sastāvs: Juris Čerņenoks, Jānis Iraids, Mārtiņš Opmanis, Rihards Opmanis, Kārlis Podnieks.

Referāts Ratniekos 2013.gada 5.augustā

Harry Altman and Joshua Zelinsky. Numbers With Integer Complexity Close to the Lower Bound. INTEGERS, The John Selfridge Memorial Volume, Vol. 12A (2012) (preprint available online)

Referāts LU 69. konferencē 2011.gada 4.februārī.

Vēsture: 2009.gada rudens semestra nodarbību konspekti. 2008.gada pavasara semestra nodarbību konspekti. 2007.gada rudens semestra nodarbību konspekti. Vēl senāka vēsture.

Spring Semester 2011

March 29, 2011

Janis Iraids has published a new web-page:

http://expmath.lumii.lv/wiki/index.php/Special:Complexity

Enter N (up to 10¹²) and obtain instantly the value of ||N|| and the shortest representation of N (one of them) as well. For example,

||999999999997|| = 84

((((3*2+1)*5*5*3*3*3*3*3*2+1)*(3*2+1)*3*2+1)*(3*3*3*3*3*3*3*2*2*2*2+1)*2+1)*2*2+1

Complexity of n, ||n|| = f(n) = A005245.

Table of ||n|| and rank(n) up to n=100000

Autumn Semester 2010

November 13, 2010

According to Janis Iraids, the hypothesis (R. Guy, F26):

if p is prime, then ||2p|| = f(2p) = min {||2p-1||+1, ||p||+2}

has been verified as false. The least falsifying prime:

p = 5 139 300 347
||2p||= ||10278600694||=72
2+||p|| = 2+||5139300347||=73
1+||2p-1|| = ||10278600693||+1=73

The hypothesis

if a+b+c>0 and c<=5, then ||2^a3^b5^c|| =2a+3b+5c has been verified and confirmed
until 10¹².

November 5, 2010

Janis Iraids announced the completion of his 2 ½ week long super-computer computation of the values of f(n) up to n=10¹². The results are stored as 1 TB file, the n-th byte of which represents the value of f(n).

The first hypotheses verified and confirmed on this data:

||2^k|| = f(2^k) = 2k for all k≤39;

Spring Semester 2010

Summary X (in Latvian)

Table of ||n|| and rank(n) up to n=100000

Complexity of n, ||n|| = f(n) = A005245

Smallest number of complexity n, a(n) = A005520

July 2, 2010

“Best of Altman”

Theorem. For any k>0: g(3k)=3^k, g(3k+1)=4*3^k-1, g(3k+2)=2*3^k.

A beautiful proof. Consider an expression E consisting of n ones, + and *. The following 2 operations retain the number of ones, but don't decrease the value of the expression:

If, in a subexpression x+y, x, y>1, then replace x+y by x*y (indeed, if x,y>1, then 1/x+1/y<=1 and x+y<=x*y).

Replace any subexpression x*y+1 by x*(y+1) .

Apply these operations to the expression E while possible. As the result, we will obtain a product of expressions 1+1 and 1+1+1 with the same total number of ones as E.

After this, since 2*2*2<3*3, replace any 2*2*2 by 3*3 (the number of ones is retained, again). As the result, we will obtain either 3^b, or 2*3^b, or 4*3^b. In any case, the number obtained is exactly g(n). Q.E.D.

June 18, 2010

Janis Iraids announced the results of his computation of f(n) for n<1 500 000 000.

1) The following hypotheses were verified until 1 500 000 000 and confirmed:

For all a, b, c, if c<=5, then f(2^a3^b5^c) = 2a+3b+5c.

For all n, f(n) = min {f(n-6)+5} U {f(n-1)+1} U {f(y)+f(z) | y*z=x}.

For all primes p, f(2p) = min(1+f(p-1), 2+f(p)). Indeed, see (2) below – none of the three numbers found is 2p.

2) Searching for numbers n for which the shortest expression is neither x*y, nor x+1, i.e. such that

f(n) < min {f(n-1)+1} U {f(y)+f(z) | y*z=x}.

Until 1 500 000 000, there are only 3 such numbers:

353 942 783 (prime) = 6+(1+2²3²)(2+3⁴(1+2*3¹⁰)), f=63, min=64, found by Fuller;

516 743 639 = 353*1463863 (2 prime factors) = 6+(1+2²3⁶)(2+3¹¹), f=63, min=64, found by Fuller;

1 163 385 647 (prime) = 6+(2+3⁷)(1+3³(1+3⁹)), f=66, min=67, found by Janis.

Fuller's program at: A005245.

3) Searching for primes p such that f(p)<f(p-1)+1. Until 1 500 000 000, there are only 2 such primes:

353 942 783 (prime) = 6+37(2+3⁴(1+2*3¹⁰)), f(p)=63, f(p-1)+1=64, found by Fuller;

1 163 385 647 (prime) = 6+(2+3⁷)(1+3³(1+3⁹)), f=66, f(p-1)+1=67, found by Janis.

4) Searching for numbers n for which there is i>1 such that f(n-i)+f(i) < f(n-1)+1.

n=21 080 618, f(6)+f(n-6)=54 < 55=f(n-1)+1, the smallest such number, found by CD_Eater (Igor).

See http://dxdy.ru/topic11665.html.

There are exactly 103 such numbers until 1 500 000 000, see the table generated by Janis' program.

June 11, 2010

Martins Opmanis announced the results of his computation of f(n) for n<997 000 000.

Until 997 000 000, the number p=353 942 783 found by Martin Fuller, is the only one prime such that f(p)<f(p-1)+1 (Martin Fuller).

Fuller's program at: A005245.

353 942 783 = 6+37(2+3⁴(1+2*3¹⁰))

What about printing out all the numbers n such that f(n-i)+f(i)<f(n-1)+1 for some i>1? The smallest number of this kind was found by CD_Eater (Igor):

n=21 080 618, f(6)+f(n-6)=54 < 55=f(n-1)+1.

See http://dxdy.ru/topic11665.html.

The following hypotheses were verified until 997 000 000 and confirmed:

For all primes p, f(2p) = min(1+f(p-1), 2+f(p)).

For all a, b, c, if c<=5, then f(2^a3^b5^c) = 2a+3b+5c.

June 4, 2010

Kaspars Balodis presented an improvement of his theorem about f(2ⁿ-1):

Theorem 1A. If n>1, then f(2ⁿ-1) ≤ 2n + [log₂(n)] + B₁(n) – 3, where B₁(n) – the number of 1-s in the binary representation of n.

Corollary. If n>1, then f(2ⁿ-1) ≤ 2n + 2log₂(n) – 2.

21.maijs

Rihards Opmanis prezentēja savu pierādījumu hipotēzei par otro lielāko skaitli, kam īsākās izteiksmes garums ir n.

Harry Altman savā rakstā HIGHEST FEW PRODUCTS AND SUMS OF ONE šo skaitli apzīmē ar g₂(n). Vislielāko skaitli viņš apzīmē ar g₁(n) vai vienkārši ar g(n).

Teorēma. g₂(3k+1)=2⁵*3^k-3(ja k>=3); g₂(3k+2)=2⁴*3^k-2(ja k>=2); g₂(3k+3)=2³*3^k-1 (ja k>=1).

Pierādījums. Indukcija pa k. Indukcijas bāze: k<=4. Te viss jāpārbauda ar konkrētiem aprēķiniem. Indukcijas solis: dotajam k>4 tiek aplūkoti visi iespējamie gadījumi. Sākam ar 3k+2 un aplūkojam izteiksmi no 3k+2 vieniniekiem. Pirmais gadījums: pēdējā operācija ir reizināšana un reizinātajos ir attiecīgi 3m+1 un 3(k-m)+1 vieninieki. Otrais gadījums: pēdējā operācija ir reizināšana un reizinātajos ir attiecīgi 3m un 3(k-m)+2 vieninieki. Trešais gadījums: pēdējā operācija ir saskaitīšana un saskaitāmajos ir attiecīgi 3m+1 un 3(k-m)+1 vieninieki. Ceturtais gadījums: pēdējā operācija ir saskaitīšana un saskaitāmajos ir attiecīgi 3m un 3(k-m)+2 vieninieki. Tālāk sk. tāfeles bildes.

Varētu mēģināt Riharda pierādījumu padarīt kompaktāku.

Ja k>=1, tad g(3k)=3^k; g(3k+1)=2²*3^k-1; g(3k+2)=2*3^k. Tātad:

g(n) = h(n mod 3)*3^{n
div 3},

kur h(0, 1, 2) = 1, 4/3, 2.

g₂(3k)=2³*3^k-2 (ja k>=2); g₂(3k+1)=2⁵*3^k-3(ja k>=3); g₂(3k+2)=2⁴*3^k-2(ja k>=2). Tātad:

g₂(n) = h₂(n mod 3)*3^{n
div 3},

kur h₂(0, 1, 2) = 8/9, 32/27, 16/9.

Secinājums: Ja n>=8, tad g₂(n) = (8/9) g(n).

Šo 13.aprīlī rakstīto Jāņa vēstuli es biju “pazaudējis pelnu mākonī”:

Sveiki!

Dažas vietnes, kuras mēs laikam neesam redzējuši.
http://religionsetspolitics.blogspot.com/2009/04/generalization-of-four-fours-problem.html
http://religionsetspolitics.blogspot.com/2009/08/revisiting-four-fours.html
http://religionsetspolitics.blogspot.com/2009/12/integer-complexity-why-blogging-is-fun.html
Tad mums ir Harry Altman, viņam blogā ir daudz ierakstu par f rēķināšanu
http://sniffnoy.livejournal.com/
Varbūt ir vērts izlasīt un saprast viņa rakstiņu (jau redzēto) iekš
http://www-personal.umich.edu/~haltman/canopy3.pdf
Tad vēl ir kaut kas mums ļoti pazīstams raksta formā
http://www.waset.ac.nz/journals/waset/v41/v41-119.pdf
Noderīgākais, ko izraku no šiem, ir tas, ka ir pierādīts, ka f(n) <= 2.65 log_2 n.
Kā arī Harijs un Džošua definē tādu A_k(x), kas ir kopu A_k un {1, 2, ..., x} šķēluma izmērs, kur A_k ir skaitļi, kuriem defekts(n) =def= f(n) - 3log_3 n <= k. Tad nu viņi ir novērtējuši A_k(x). Laikam kā O(x), kaut gan reāli izskatoties kaut kas līdzīgs (log x)^2.
Varbūt vajag mēģināt "apvienot spēkus"? Izskatās jau, ka šie par mums neko nav dzirdējuši.

Jānis

14.maijs

Te redzami Jura pārbaudītie pirmskaitļi formā 6m+5 līdz 10 000. Tādu ir pavisam 616, lielākajai daļai jau p^2 īsākā izteiksme ir īsāka par to, kuru var iegūt no p*p.

4 skaitļiem p^2 īsākā izteiksme ir iegūstama no p*p, bet p^3 īsākā izteiksme jau ir īsāka par to, kuru var iegūt no p*p*p.

Utt.

Vienīgi jāatceras, ka datu beigu daļā, kur p^k iznāk lielāks pat par Jāņa tabulā atrodamajiem skaitļiem, nevar droši apgalvot, ka, piemēram, 257^5 īsākā izteiksme nav īsāka par to, kuru var iegūt no p*p*p*p*p.

Te mēs aizdomājāmies līdz jautājumam: skaidrs, ka f(x^2)<=2f(x), bet vai eksistē bezgalīgi daudzi tādi x, kam f(x^2)<2f(x)?

Mazliet šo hipotēzi pastiprinot, nonākam līdz jautājumam: vai eksistē bezgalīgi daudzi tādi x, kam f(x+1)<f(x) un f(x-1)+1=f(x)? Liekas, ka eksistē.

Diemžēl, pierādīt mēs neprotam pat katru no abām daļām atsevišķi:

Hipotēze 1. Eksistē bezgalīgi daudzi tādi x, kam f(x+1)<f(x). Liekas, ka eksistē (citādi f(x), sākot ar kādu vietu, kļūtu monotona...).

Hipotēze 2. Eksistē bezgalīgi daudzi tādi x, kam f(x-1)+1=f(x). Liekas, ka eksistē (tādi ir visi pirmskaitļi līdz 300 000 000 vai tml.).

Radās cerība, ka pirmo hipotēzi varēsim pierādīt, ja pierādīsim hipotēzi par otrajiem lielākajiem skaitļiem ar doto f(x) vērtību. Atcerēsimies to:

Izteiksmes garums	1.lielākais (Mārtiņa teorēma)	2. lielākais (hipotēze)
3k+1	2²*3^k-1	2⁵*3^k-3
3k+2	2*3^k	2⁴*3^k-2
3k+3	3*3^k	2³*3^k-1

7.maijs

Kas ir Stephen Wolfram?

http://www.stephenwolfram.com/

http://en.wikipedia.org/wiki/Stephen_Wolfram

http://en.wikipedia.org/wiki/A_New_Kind_of_Science

Kārtējais Riharda atklājums:

Piemēram, ja WolframAlpha padod izteiksmi (6 x+5)^6-1, tad iegūst tās alternatīvu formu

36 (x+1) (3 x+2) (12 x^2+18 x+7) (36 x^2+66 x+31).

Tālāk, ja WA padod (12 x^2+18 x+7) (36 x^2+66 x+31)-1, tad iegūst alternatīvu formu

12 (x+1) (3 x+2) (12 x^2+20 x+9).

Tātad:

(6 x+5)^6 = 1+36 (x+1) (3 x+2)(1+12 (x+1) (3 x+2) (12 x^2+20 x+9)).

Pie x=0:

5^6 = 1+2*2*3*3*2(1+2*2*3*2*3*3), jeb 5⁶ = 1+2³3²(1+2³3³).

Tādā veidā esam ieguvuši to, ko saucam par Iraida efektu (citēju Jāņa vēstuli):

5⁶ =15625=1+2³*3²*217=1+2³*3²*(1+2³*3³), garums 29, rangs 5.

“Dabiskā” izteiksme 5*5*5*5*5*5 dod garumu 30 un rangu 2.

Ja to pašu atkārtojam ar (6 x+1)^6-1:

36 x (3 x+1) (12 x^2+6 x+1) (36 x^2+6 x+1)

12 x (3 x+1) (12 x^2+4 x+1)

(6 x+1)^6 = 1+36 x (3 x+1) (1+ 12 x (3 x+1) (12 x^2+4 x+1))

Pie x=1: 7^6 = 1+2*2*3*3*2*2(1+2*2*3*2*2*17), garums 36.

“Dabiskā” izteiksme 7^6 = (2*3+1)^6 arī dod garumu 36.

Utt.

23.aprīlis

9.aprīlī

Kaspars Balodis pierādītie rezultāti

Teorēma 1. Ja n>1, tad f(2ⁿ-1) ≤ 2n + 3log₂(n)-3 (ja n ir pārskaitlis, tad -4).

Pierādījums. Būvējam skaitļa 2ⁿ-1 izteiksmi, izmantojot divus piegājienus:

2²ⁿ-1 = (2ⁿ-1)*(2ⁿ+1); t.i. f(2²ⁿ-1) ≤ f(2ⁿ-1)+f(2ⁿ+1) ≤ f(2ⁿ-1)+2n+1;

2²ⁿ⁺¹-1 = 2*(2²ⁿ-1)+1; t.i. f(2²ⁿ⁺¹-1) ≤ f(2²ⁿ-1)+3.

Tālāk indukcija par n.

Ja n=2, tad f(2²-1)=3 ≤ 2*2+3*1-4 = 3.

Ja n=3, tad f(2³-1)=6 < 2*3+3*log₂3-3, jo 3*log₂3-3>0.

Ja n=4, tad f(2⁴-1)=8 < 2*4+3*2-4 = 10.

f(2²ⁿ-1) ≤ f(2ⁿ-1)+2n+1 ≤ 2n+3log₂(n)-2+2n+1 ≤ 2*2n+3log₂(2n)-3-2+1 (kopā -4).

f(2²ⁿ⁺¹-1) ≤ f(2²ⁿ-1)+3 ≤ 2*2n+3log₂(2n)-4+3 ≤ 2(2n+1)-2+3log₂(2n+1)-4+3 (kopā -3).

Q.E.D.

Teorēma 2. Ja N>1, tad f(N) ≤ 2B₀+3B₁-3; ja N>2, tad f(N) ≤ 3T₀+4T₁+5T₂-4, kur B un T apzīmē attiecīgo ciparu skaitu N binārajā un ternārajā pierakstā.

Jura pirmā vēstule: Par f(2^n - 1) + 1 uzvedību.

Sveiki!

Rezultāti

Uzrakstīju nelielu programmiņu [sk. rezultātus], kas cenšas konstruēt labāko izteiksmi dotam n ar pēdējo operāciju +1. Izmantojot šo programmu, es sarēķināju f(2^n) vērtības priekš n<=80. Protams, šīs vērtības ir tikai hipotētiskas, un to, cik lielā mērā tām var ticēt, es atstāju katra paša ziņā. Taču arī jāpiebilst, ka visas iespējamās n vērtības(n<=29) salīdzināju ar patiesajiem datiem un tās sakrīt; tas vieš kādu cerību arī par pārējām.

Pielikumā sūtu failu ar (n, f(2^n - 1) + 1 – 2n) grafiku un tabulu ar f(2^n - 1) + 1 vērtībām un izteiksmēm.

Dažos vārdos par manu algoritmu.

Tātad vajag atrast f(n).

sākumā uzdod [n, d, {kd, k(d-1), …, k1}] (k1 principā vienmēr būs 1)

rēķina f(n, d)

labākais = bezgalība

n = 2^a * 3^b * n1 + 1

labākais = 2*a + 3*b + min{labākais, f(n1, d-1)} + 1

labākais = 2*a + 3*b + min{labākais, f(m1, d-1) + f(m2, d-1)} + 1, pa visiem m1*m2 = n1

…

labākais = 2*a + 3*b + min{labākais, f(m1, d-1) + f(m2, d-1) +…+ f(mkd, d-1)} + 1, pa visiem m1*m2*…*mkd = n1

f(n, d) = labākais

rēķina f(n, 1)

ja n = 2^a*3^b + 1, tad f(n, 1) = 2*a + 3*b + 1

ja n = 3^b + 2, tad f(n, 1) = 3*b + 2

citos gadījumos f(n, 1) = bezgalīga

d es saucu par dziļumu, un tas laikam ir [rangs/2] +- 1.

Seminārā izstāstīšu detalizētāk un ar visām niansēm.

Juris

Jura otrā vēstule: "Iraida efekts" piecinieka pakāpēm turpina izpausties!

Sveiki!

Likās interesants tāds jautājums – vai „Iraida efekts” piecinieka pakāpi piemeklēs vēl kādreiz?

Apskatam 5^k. Ko mēs varam pateikt par f(5^k) patvaļīgam k ar to informāciju, kas mums bija zināma līdz šim? Laikam pareizs ir tāds secinājums:

k = 6a + b => f(5^k) = 29a + 5b.

Tagad apskatam gadījumu k = 36. Tātad f(5^36) vajadzētu būt 6 * 29 = 174.

Taču pavisam noteikti f(5^36) <=173, jo

5^36 = 2^4 * 3^3 * 247 * 244125001 * 558633785731 + 1, kur

247 = 3 * (3^4 + 1) + 1

244125001 = 2^3 * 3^2 * (2^3 * 3^3 + 1) * (2^3 * 3^2 * (2^3 * 3^3 + 1) + 1) + 1

558633785731 = 2 * 3 * (2^3 * 3^5 + 1) * (2 * 3^4 * (2^6 * 3^5 * (2 * 3^2 + 1) + 1) + 1) + 1

P.S. Vakar epastā tajā algoritma aprakstā mazliet kļūdījos. To 2a + 3b un 1 nest ārpus min nav nekāda pamatojuma. Pareizi jābūt tā

labākais = min{labākais, 2a + 3b + f(n1, d-1) + 1}

un citur analoģiski.

Līdz rītdienai,

Juris

26.marts

Sum of prime factors, jeb integer logarithm, jeb mūsu f2(x):
http://www.research.att.com/~njas/sequences/A001414
Sk. grafiku http://mathworld.wolfram.com/SumofPrimeFactors.html
Augšējais ierobežojums ir sopfr(x)<=x, tas tiek sasniegts pirmskaitļiem x.
Apakšējais: sopfr(x)>=3log3(x), tas tiek sasniegts trijnieka pakāpem.
Sk. http://www.mathpages.com/home/kmath006/part1/part1.htm
Tur Lemma 3.

Kā uzvedas f2(x)+f2(N-x) pie dotā N, piemēram, ja N=2^a? Kāds ir maksimums
pie dotā N?

Tas nedaudz atgādina Jāņa atrasto info:
Ja n=21 080 618, tad f(6)+f(n-6)=54 < 55=f(n-1)+1 (CD_Eater = Igor).

Bet kā vispār uzvedas f(x)+f(N-x)? Kāds ir maksimums pie dotā N?

Kāpēc es interersējos par f2(x)+f2N-x)? Tāpēc ka ceru, ka būs vieglāk
pierādīt f3(2^a)=2a, nevis uzreiz f(2^a)=2a.

Un f3(N)<=f2(x)+f2(N-x), f3(N)<=f2(x)+f2(y)+f2(N-x-y) utt.

Bet, varbūt, tas viss ir "garām"...

10.marts

Jāņa atrasta info: http://dxdy.ru/topic11665.html.

Te tiek pieņemts, ka f(1)=1.

Ja n=21 080 618, tad f(6)+f(n-6)=54 < 55=f(n-1)+1 (CD_Eater = Igor). Tas esot mazākais pretpiemērs hipotēzei, ka f(i)+f(n-i) ir vismazākais, ja i=1.

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.

Mārtiņa tabula a(n), n=1..59: http://www.research.att.com/~njas/sequences/b005520.txt

27.februārī

Kopsavilkums X

Mārtiņa aprēķini liecina, ka nav patiesa šāda KP hipotēze: īsāko skaitļa N izteiksmi bāzē {1,+,*} var iegūt ar šādu algoritmu: ja N dalās ar 2 vai 3 - izdalām, atkārtojam to, kamēr vairs nedalās, tad atņemam 1 un sākam no gala: ja dalās ar 2 vai 3 - izdalām, atkārtojam to, kamēr vairs nedalās, utt.

Pirmais skaitlis, kuram šī hipotēze neizpildās, ir 12594.

Ja rīkojamies pēc algoritma, tad iegūstam: 12594=2*3*2099=2*3*(1+2*(1+2³*(1+2*(1+2⁶)))), izteiksmes garums 31, rangs 10.

Bet arī: 12594=1+(1+2*3)²*(1+2⁸), garums 30, rangs 5.

24.februārī: Sveicināti!

Hipotēzē par n-to lielāko skaitli vārda "nepārsniedz" vietā jābūt "ir". Vismaz šajā brīdī liekas, ka tā būtu pareizi.
Hipotēzi esmu pārbaudījis rindai 3k+1 priekš n<=15 un abām pārējām priekš n<=30. Jāpiebilst, ka hipotēze ir atkarīga arī no k, un k vērtībām biju pārbaudījis visām iespējamām, kad man bija zināmas f vērtības kaut kur līdz 5*10^6. (Vispār ir doma sarēķināt f vērtības daudz tālāk, tad varētu pārbaudīt hipotēzi lielākā intervālā, tikai nezinu, uz kuru laiku to izdarīšu.)

Juris Čerņenoks

15.februārī

Literatūrā f(N) ir tradicionālais apzīmējums vieninieku skaitam īsākajā 1+* izteiksmē, kas attēlo skaitli N.

Ja starp skaitļa N īsākajām 1+* izteiksmēm atrod to, kam vismazākais rangs, tad iegūst skaitļa N rangu r(N).

Atceramies augstāk minēto

Ģenerālo Hipotēzi: r(N)=2 tad un tikai tad, ja N>=6 un N=2^a*3^b*5^c, kur a+b+c>1 un c<=5. Bez tam, šai gadījumā: f(2^a*3^b*5^c)=2a+3b+5c.

Savienojot abas idejas, varam ievest funkciju f_k(N) = vieninieku skaitam īsākajā 1+* izteiksmē, kuras rangs <=k.

Teorēma. f₁(N) = N.

Dāvja Krastiņa teorēma. f₂(N) = ∑p_i, kur p_i ir skaitļa N visi pirmreizinātāji.

Sekas: f₂(2^a*3^b*5^c)=2a+3b+5c, kur a+b+c>1 (c var būt arī lielāks par 5).

Hipotēze: f₃(2^a*3^b*5^c)=2a+3b+5c, kur a+b+c>1 un c<=5.

Šī hipotēze ir vājāka par Ģenerālo. Un tāpēc – vieglāk pierādāma? Un f₃(2^a)=2a arī ir vieglāk pierādīt nekā f(2^a)=2a?

Ja f(2^a-1)<2a, tad 2^a var uzrakstīt otru izteiksmi ar garumu <=2a. Tātad:

Hipotēze: f(2^a-1)>=2a.

Ģenerālo Hipotēzi vajadzētu pastiprināt: N>=6, N=2^a*3^b*5^c, kur c<=5. Īsākās izteiksmes garums tad ir 2a+3b+5c, rangs 2. Un īsākā izteikmse ir tikai viena!

8.februārī

-----------

29.janvārī

Jura atrastie raksti:

Complejidad de los numeros naturales, por J. Arias de Reyna, Gaceta de la Real Sociedad Matem?tica Espa?ola 3 (2000) 230-250.

HIGHEST FEW PRODUCTS AND SUMS OF ONE, by HARRY ALTMAN

http://www.research.att.com/~njas/sequences/A005245 - vai šo esat redzējuši?

Tāfeles bildes

---------

22.janvārī

log₃(2) = 0,6309; 1/log₃(2) = log₂(3) = 1,5850

3log₃(N) <=f(N)<= 3log₂(N)=4,7549log₃(N). Apakšējo robežu sasniedz trijnieka pakāpes.

Divnieka pakāpēm: f(N)=2log₂(N)=3,1699log₃(N).

Mārtiņš prezentēja tabulu, kurā attiecība f(N)/log₃(N) redzama visiem N līdz aptuveni 70*10⁶.

Izskatās, kas šai ziņā "vissliktākie" skaitļi ir:

1439 = 2⁵3²5-1; f(N)/log₃(N) = 3,92809, Hipotēze: visiem N, f(N)<= 3,92809log₃(N) (nevis 4,7549).

23 = 2³3-1; f(N)/log₃(N) = 3,854

719 = 2⁴3²5-1; f(N)/log₃(N) = 3,841

179 = 2²3²5-1; f(N)/log₃(N) = 3,812

4283 = 2²3²7*17-1; f(N)/log₃(N) = 3,809

Tālāk f(N)/log₃(N) = 3,7+ "beidzas" aptuveni pie 2*10⁶.

Katram N₀ eksistē mazākā konstante c(N₀) tāda, ka visiem N>=N₀: f(N)<= c(N₀)log₃(N). Aplūkosim kopu C no visiem skaitļiem c(N₀). Tad inf(C) >= 1. Kāda ir inf(C) precīzā vērtība? Izkatās, ka inf(C)<3,7?

Aplūkosim kopu D no visām attiecībām f(N)/log₃(N).

D mazākais elements ir 1, lielākais (hipotēze) 3,92809. No mūsu hipotēzes f(2^a3^b5^c)=2a+3b+5c (c<=5) seko, ka kopa D ir blīva segmentā no 1 līdz 2,1699. Tuvāk pie 3,92809, D vairs nav blīva. Kur atrodas D mazākais "caurums"?

Rihards prezentēja tabulu ar īsāko izteiksmju garumiem g(N) bāzē {1, +, -, *}.

Jura vēstule 24.janvārī:

Labvakar!

Balstoties uz Riharda novērojumiem, ka {1,+,-,*} problēmā labāku izteiksmes garumu nevar iegūt atņemot vairāk kā 1, pārveidot savu {1,+,*} problēmas kodu, lai pats iegūtu datus, nudien nebija grūti.
Piesaistnē pievienoju failu ar grafikiem (grafiki.pdf). Pirmais grafiks ir veidots tā, ka uz f(n) ir likts virsū g(n). Grafikā var redzēt, ka atņemšanas operācija nelielu ieguldījumu 1 skaita samazināšanas ziņā patiešām dod. Otrais grafiks ir (n, f(n) / log_3 n)(vienkārši likās interesants, tāpēc ieliku).
Svarīgs liekas Mārtiņa novērojums, ka katram n |g(n+1) – g(n)| ? 1.
Lūk, virknes, kuras i-tais loceklis ir mazākais n, kuram g(n) = i, pirmās 50 vērtības:

{1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 29, 41, 58, 67, 101, 131, 173, 262, 346, 461, 617, 787, 1123, 1571, 2077, 2767, 4153, 5443, 7963, 10733, 13997, 21101, 27997, 36643, 49747, 72103, 99317, 143239, 179107, 260213, 339323, 508987, 718603, 973373, 1291853, 1800103, 2421403, 3377981, 4831963, 6834397}

Likās, ka visi elementi sākot ar 26. varētu būt pirmskaitļi, taču 45. virknes loceklis ir 1291853 = 619 * 2087.
Seminārā izskanēja domas par šādu likumsakarību: 5 pieder kopai un 2*5 = 10 arī pieder; 11 pieder un 2*11 = 22 arī; 29 pieder un 2*29 = 58 arī; utt. Diemžēl tāda sakarība vēl ir vērojama tikai skaitļiem 131 un 173.
Beigās vēl neliela piebilde. Pēdējā seminārā noskaidrojām, ka neizpildās f(19^k) = 9k.
Gadījumā, kad k = 6 vajadzētu it kā būt 54 vieniniekiem, taču

19^6 = 2^3 * 3^2 * 7 * (2^5 * (2^2 * 3^6 + 1) + 1) + 1,

tātad f(19^6) ir ne vairāk kā 53.
Ja esmu ko svarīgu aizmirsis, tad, lūdzu, pierakstiet!

Visu labu!
Juris

Tāfeles bildes

---------

15.janvārī

log₃(2) = 0,6309

1/log₃(2) = log₂(3) = 1,5850

Kā redzam, viegli pierādīt, ka 3log₃(N) <=f(N)<= 3log₂(N)=4,7549log₃(N). Apakšējo robežu sasniedz trijnieka pakāpes. Divnieka pakāpēm: f(N)=2log₂(N)=3,1699log₃(N).

Cik daudz ir skaitļu, kas ir "sliktāki" par divnieka pakapēm, un kāda ir to "daba"?

Tāfeles bildes:

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

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

8.janvārī

KP: Jura lieliskais skaitlis (569 ir pirmskaitlis, abām izteiksmēm 1 skaits ir 26):

5121 = 9*569 = 2¹⁰*5+1 = 3²(3⁴(2*3+1)+2).

Pasūtīsim T-kreklus ar šo vienādību?

Jura tabula unikalie.pdf - skaitļi, kuriem ir tikai viena īsāka izteiksme bāzē {1, +, *}.

Kas tie par skaitļiem, kuriem bāzē {1, +, *} vienā no īsākajām izteiksmei (vai visām) ārējā operācija ir saskaitīšana?

Kas tie par skaitļiem, kuriem bāzē {1, +, *} ir vismaz divas īsākās izteiksmes - viena ar ārējo operāciju *, otra - ar +?

Jautājums: kā mainīsies mūsu eksperimentu vide, ja bāzi {1, +, *} papildināsim ar atņemšanu, t.i. aplūkosim bāzi {1, +, -, *}? Ja N=x-y ir N īsākā izteiksme, tad cik liels var būt x?

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

Daudzstāvu kāpināšana reāliem skaitļiem

Sk. http://en.wikipedia.org/wiki/Tetration un http://mathworld.wolfram.com/PowerTower.html (te ir daudz bilžu).

Var arī http://www.tetration.org/.

Summa x+x+...+x, kur x atkārtojas n reizes, dod reizinājumu x*n. Tādā veidā reizināšanas operācija it kā "rodas" no saskaitīšanas. Pēc tam reizinājumu x*y iemanās nodefinēt ne tikai tad, ja y ir naturāls skaitlis, bet arī patvaļīgam reālam skaitlim y. Atceraties, kā to dara?

Reizinājums x*x*...*x, kur x atkārtojas n reizes, dod pakāpi x^n (parasti gan raksta xⁿ). Tādā veidā kāpināšanas operācija it kā "rodas" no reizināšanas. Pēc tam pakāpi x^y (jeb x^y) iemanās nodefinēt ne tikai tad, ja y ir naturāls skaitlis, bet arī patvaļīgam reālam skaitlim y. Atceraties, kā to dara?

Tagad seko jaunums:

Pakāpe x^(x^(...^(x)...), kur x atkārtojas n reizes, dod operāciju x^^n, ko cilvēki nosaukuši par tetrāciju (tetration). Līdz šim nevienam vēl nav izdevies apmierinošā veidā nodefinēt x^^y patvaļīgam reālam skaitlim y. Piemēram, ko varētu nozīmēt x^^(1/2)?

x^^1 = x.

x^^2 = x^x, jeb: 1^^2=1, 2^^2=4, 3^^2=27, 4^^2=256, ...

x^^3 = x^(x^x), jeb: 1^^2=1, 2^^2=16, 3^^3=3²⁷, ...4^3=2⁵¹², ...

x^^4 = x^(x^(x^x)), jeb: 1^^4=1, 2^^4=2¹⁶=65536, 3^^4=3^3²⁷vairs nav aptverams, ...

...

Kāds varētu būt grūtību cēlonis? Saskaitīšana un reizināšana ir asociatīvas un komutatīvas operācijas. Bet kāpināšana vairs nav ne viena, ne otra. Piemēram, 2^3 = 2³ = 8, bet 3^2 = 3² = 9 (nekomutativitāte), bet (x^y)^z = x^(y*z), kas parasti nav vienāds ar x^(y^z) (neasociativitāte).

Tāpēc, kad mēs rakstām "pakāpe x^(x^(...^(x)...), kur x atkārtojas n reizes", tad ir ļoti svarīgi, ka iekavas ir saliktas no labās puses uz kreiso: x^^3 = x^(x^x). Ja mēs saliktu iekavas no kreisās uz labo: (x^x)^x, tad iegūtu x^(x*x), jeb vispārīgajā gadījumā x^(x^n), t.i. rezultāts būtu iegūstams ar divu kāpināšanu palīdzību. Bet vēl taču ir iespējams salikt iekavas arī citos veidos, piemēram, (x^x)^(x^x). Tas nozīmē, ka definējot x^^n, mēs iekavas speciāli saliekam tā, lai iegūtu vislielāko rezultātu.

Palasiet internetā atrodamos materiālus. Vai Jums rodas kāda ideja, kā būtu jādefinē x^^(1/2), x^^(1/3) utt.?

Vizualizācijas programmatūra

Gan esksperimentālajā matematikā, gan datizracē (data mining) viena no efektīvām pētniecības metodēm ir datu vizualizācija. Piemēram, ja ar t.s. Goldbaha hipotēzi saistītos datus attēlo vizuālai uztverei, tad iegūst t.s. Goldbaha komētu. Vērojot šādus attēlus, cilvēks dažreiz spēj izdarīt tālejošus secinājumus (sk. minēto saiti).

Kā tas iespējams? Esmu lasījis skaidrojumu, ka cilvēka smadzenēs vislielākais "orgāns" esot redzes centrs, t.i. tas laikam ir vissjaudīgākais no mūsu smadzenēs esošajiem "procesoriem". Tāpēc neesot jābrīnas, ka vērojot attēlus, cilvēks dažreiz spēj izdarīt tādus secinājumus, kas pat lielākajiem mūsdienu datoriem "sapņos nerādās".

Un tāpēc, risinot visdažādākos eksperimentālās matemātikas un datizraces uzdevumus, mums noderētu pietiekami universāla programmatūra, kas ļautu mums vienkārši un ātri vizualizēt, piemēram, funkciju grafikus. Runa vispirms būtu par naturālo skaitļu funkcijām f(x), kur x mainās, piemēram, no 0 līdz 1000000 (tieši tādā situācijā rodas Goldbaha komēta), bet mēs šādu funkciju grafikus gribētu redzēt, piemēram, 2 megapikseļu attēlā (2000x1000 pikseļi).

Kādu API šim uzdevumam mēs varētu vēlēties? Piedāvāju šādu minimumu:

CreatePicture(pikseļi par horizontāli, pikseļi pa vertikāli, min_X, max_X, min_Y, max_Y);

DeletePicture();

SavePicture();

SetPoint(X, Y); // ar šo ielādējam bildes punktus un pēc tam noglabājam kā JPG vai tml.

Ja vēlaties, varam papildus pielikt krāsu un fontu vadību utml.

Kā produktu noformēt? Vecais ieradums - kā Windows DLL. Kā to pieņemts darīt tagad?