Piedāvātais pirmais pētniecības virziens - nereducējamie skaitļi

Gribu ieteikt palūkoties uz pirmskaitļa jēdzienu no mazliet citādām pozīcijām.

Vienkāršākais veids kā kādu kādu naturālu skaitli reducēt uz mazākiem skaitļiem, ir šāds:

2=1+1, 3=1+1+1, 4=1+1+1+1, utt.

Sauksim to par pirmā veida pierakstu.

Teorēma 1. Skaitļa N pirmā veida pieraksta garums ir 2N-1.

Pierādījums. Pierakstā N=1+1+1+... ir N vieninieku un N-1 saskaitīšanas operāciju. Q.E.D.

Nākošais solis (otrā veida pieraksts): vispirms skaitli sadalīt reizinātājos, un tad reizinātājus attēlot kā 1+1+..., piemēram:

6=2*3=(1+1)*(1+1+1).

Ja neskaita iekavas, tad operāciju un operandu kopskaits te iznāk 9. Tas ir mazāk nekā pirmā veida izteiksmē 6=1+1+1+1+1+1, kur to ir 11.

Pirmskaitļiem otrā veida izteiksmju izmantošana pierakstu nesaīsina (jo tos nevar sadalīt reizinātājos). Viegli pārliecināties, ka šī īpašība piemīt tikai pirmskaitļiem un (nejauši) arī skaitļiem 1 un 4.

Tātad pirmskaitļus varētu definēt kā skaitļus, kuriem otrā veida pieraksts neiznāk īsāks par pirmā veida pierakstu (un kas nav vienādi ar 1 un 4), jeb kā 2-nereducējamus skaitļus.

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

Pierādījums. Tātad mums ir zināms, ka N=ab. Uzskatīsim, ka 2<=a<=b (jo N>1 un N nav pirmskaitlis). Bez tam, ka ja a=2, tad b>2 (jo N nav 4). Ja tagad uzrakstīsim N=A*B, kur A, B ir skaitļu a, b pirmā veida pieraksti, tad iegūsim N otrā veida pierakstu, kura garums ir gar(A)+gar(B)+1 = 2a-1+2b-1+1 = 2(a+b)-1. Skaitļa N pirmā veida pieraksta garums ir 2N-1=2ab-1. Atliek pierādīt, ka 2(a+b)-1<2ab-1, jeb a+b<ab.

Tiešām, ja a>2, tad a+b<=2b<ab. Ja a=2, tad 2+b<2b (jo b>2). Q.E.D.

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

Pierādījums. Pieņemsim, ka N=AB, kur A=1+1+1+.... Ja A nav 4 un nav pirmskaitlis, tad A eksistē īsāks otrā veida pieraksts par 1+1+1+.... Ievietojot to A vietā, iegūsim vēl īsāku N otrā veida pierakstu. 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.

Nākošais solis (trešā veida pieraksts): vispirms skaitli sadalīt saskaitāmajos, tad saskaitāmos - reizinātājos, bet tos - atkal saskaitāmajos. Piemēram:

7=6+1=3*2+1=(1+1+1)*(1+1)+1.

Ja iekavas neskaita, tad operāciju un operandu kopskaits te iznāk 11. Tas ir mazāk nekā pirmā (un otrā) veida izteiksmē 7=1+1+1+1+1+1+1, kur ir 13 operāciju un operandu.

Bet ir skaitļi, kuriem trešā veida pieraksts neiznāk īsāks par otrā veida pierakstu. Tos varētu saukt par 3-nereducējamiem skaitļiem (parastie pirmskaitļi ir 2-nereducējami skaitļi, tāds ir arī skaitlis 7, bet kā tikko redzējām - 7 nav 3-nereducējams). Eksperimenti it kā liecina, ka visas divnieka pakāpes ir 3-nereducējami skaitļi, kuriem īsākais pieraksts ir otrā veida: (1+1)*(1+1)*.... Bet 3-nereducējami ir vēl arī citi skaitļi: 3, 5, 6, 9, 10, 12, 14, 15, 18, 20, 21, 24, 25, 27, 30, 35, 36, ...

Teorēma 3. Visas divnieka pakāpes ir 3-nereducējami skaitļi. Skaitļa 2n (n>0) īsākais otrā (un trešā) veida pieraksta garums ir 4n-1.

Pierādījums. Vispirms, skaitlim 2n otrā veida pieraksta (1+1)*(1+1)*... garums tiešām ir 4n-1. Saskaņā ar Dāvja teorēmu 2, tas ir skaitļa 2n īsākais otrā veida pieraksts. Bet kā ar trešā veida pierakstu? Kāpēc tas nevar būt vēl īsāks?????? Kurš turpinās?

Problēma. Raksturot 3-nereducējamos skaitļus. Šķiet, ka vislabāk būtu sākt ar dator-eksperimentu, drukājot katram skaitlim viņa labākos otrā un trešā veida pierakstus (un to garumus), un tad atlasot 3-nereducējamos skaitļus. Aplūkojot pietiekami daudz datu, varam cerēt izvirzīt kādu hipotēzi. (Varbūt, vispirms mums būtu jāapspriežas, kāda veida algoritmu programmēt?). Pēc tam būtu jāmēģina hipotēzi pierādīt - vajadzētu iznākt diezgan skaistai teorēmai. Ja nespēsim pierādīt - mēģināsim eksperimentu paplašināt, aptverot arvien lielākus skaitļus un pārbaudot, vai arī šiem skaitļiem mūsu hipotēze izpildās.

Cik daudz 3-nereducējamu skaitļu ir starp skaitļiem 1, 2, ..., N? Ja šo jautājumu uzdod par parastajiem pirmskaitļiem, tad atbilde ir: starp skaitļiem 1, 2, ..., N ir aptuveni N/ln N pirmskaitļu (sk. jebkuru skaitļu teorijas mācību grāmatu). Varbūt, pietiekami plaši eksperimenti mums pateiks priekšā līdzīgu formulu 3-nereducējamiem skaitļiem?

Tālāk var pāriet pie ceturtā veida pierakstiem. Vai 4-nereducējamie skaitļi būs vēl interesantāki? Arī te darbs varētu beigties vai nu ar skaistu teorēmu, vai vizmaz ar iespaidīgu hipotēzi. Vai ir jēga iet vēl tālāk - pie piektā veida utt? Arī te atbildi var dot eksperimenti...

Vai no šī "pētniecības virziena" var sagaidīt arī kādus lietojumus? Matemātikā parasti to nevar iepriekš uzminēt. Parastos pirmskaitļus atklāja Senajā Grieķijā VI gs. p.m.ē. Bet šo skaitļu lietojums kriptogrāfijā tika atrasts tikai XX gs. pašās beigās. Tiesa, vairākus gadu desmitus pirms tam pirmskaitļi tika izmantoti informācijas kodēšanas teorijā.

Pirmo 16500 skaitļu dažādu pierakstu garumi (500 KB)- tos izdrukājusi mana vecā, nepilnīgā programma, kurai nevar pilnīgi droši ticēt. Izbaudiet eksperimentālā matemātiķa sajūtu - kādas hipotēzes par 3- un 4-nereducējamo skaitļu "dabu" Jums nāk prātā, aplūkojot šos eksperimentālos datus? Sk. tālāk vēl lielāku datu failu.

Manas programmas darba rezultāti līdz 64600 (4 MB). Tur pievienotas vēl piektā veida izteiksmes. Redzams, ka 5-nereducējamu skaitļu ir ļoti daudz.

Manas programmas darba rezultāti līdz 16500 (2 MB) un līdz 33000 (5 MB) - jaunajā Dāvja ieteiktajā formātā. Tur pievienotas vēl piektā līdz devītā veida izteiksmes. Redzams, ka gandrīz visi skaitļi ir 9-nereducējami skaitļi. Bet ne visi. Vai šo izņēmumu ir bezgalīgi daudz? Rodas arī citi interesanti secinājumi (t.i. hipotēzes). Piemēram, varbūt, VISI pietiekami lieli naturāli skaitļi tomēr ir vismaz 13-nereducējami?

Mana programma ir ļoti vienkārša:

Septiņos masīvos tiek uzkrāta mazākie dotā veida izteiksmju garumi skaitļiem 1, 2, 3, ..., MAX_NUMBER.

int Complexity1[MAX_NUMBER+1];
int Complexity2[MAX_NUMBER+1];
int Complexity3[MAX_NUMBER+1];
int Complexity4[MAX_NUMBER+1];
int Complexity5[MAX_NUMBER+1];
int Complexity6[MAX_NUMBER+1];
int Complexity7[MAX_NUMBER+1];

Sākumā aizpildām pirmo masīvu:

for (int i=0; i<=MAX_NUMBER; i++) Complexity1[i]=-1; // unknown
for (int i=0; i<=MAX_ARGUM; i++) Complexity1[i]=1; // arguments
modified = 1;
while (modified)
{
modified = 0;
for (int i=1; i<MAX_NUMBER; i++)
{
if (Complexity1[i]==-1) continue;
for (int j=1; j<=MAX_NUMBER; j++)
{
if (Complexity1[j]==-1) continue;
int n = i+j; // addition
if ((n<1)||(n>MAX_NUMBER)) continue;
int c = Complexity1[i]+Complexity1[j]+1;
if ((Complexity1[n]==-1)||(c<Complexity1[n]))
{ Complexity1[n] = c; modified = 1; continue; };
}; // j
}; // i
}; // while

Pēc tam otro:

for (int i=0; i<=MAX_NUMBER; i++) Complexity2[i]= Complexity1[i];
modified = 1;
while (modified)
{
modified = 0;
for (int i=1; i<MAX_NUMBER; i++)
{
if (Complexity2[i]==-1) continue;
for (int j=1; j<=MAX_NUMBER; j++)
{
if (Complexity2[j]==-1) continue;
int n = i*j; // multiplication
if ((n<1)||(n>MAX_NUMBER)) continue;
int c = Complexity2[i]+Complexity2[j]+1;
if ((Complexity2[n]==-1)||(c<Complexity2[n]))
{ Complexity2[n] = c; modified = 1; continue; };
}; // j
}; // i
}; // while

un tad - tieši tāpat - visus pārējos pēc kārtas.

Vai šī programma dara to, kas tai jādara - katram skaitlim 1, 2, 3, ..., MAX_NUMBER atrod īsākās 1, 2, 3, 4, 5, 6, 7 veida izteiksmes garumu? Redzat kādu kļūdu?

(24.novembrī) Nereducējamie skaitļi līdz 33000 (5 MB) - jaunais Dāvja ieteiktais formāts.

(1.decembrī) Dāvja jaunā programma (400 KB) nereducējamo skaitļu pētīšanai (parametri: m - līdz kuram skaitlim rēķināt, n - līmeņu skaits).

Turpinājums sekos.


Dāvja Krastiņa 16.septembra vēstule

Sveiki visiem,

šeit īsumā izklāstīšu savus pārdomu rezultātus par otro tēmu t.i. savdabīgo
skatījumu uz pirmskaitļiem un trešajiem pirmskaitļiem..
Necentīšos formalizēt un izklāstīt precīzus pierādījumus, pirmkārt tāpēc, ka
daļai secinājumu/pieņēmumu to pagaidām nav, otrkārt tāpēc, ka
to ērtāk ir izdarīt klātienē.

Tātad atgādinot par ko ir runa saīsināts citāts no lapas:

-----
Vienkāršākais veids kā kādu kādu naturālu skaitli reducēt uz mazākiem
skaitļiem, ir šāds:
2=1+1, 3=1+1+1, 4=1+1+1+1, utt.
Nākošais solis (otrā veida pieraksts): vispirms skaitli sadalīt
reizinātājos, un tad reizinātājus attēlot kā 1+1+..., piemēram:
6=2*3=(1+1)*(1+1+1).
Pirmskaitļus varētu definēt kā skaitļus, kuriem otrā veida pieraksts neiznāk
īsāks par pirmā veida pierakstu (un kas nav vienādi ar 1 un 4).
Nākošais solis (trešā veida pieraksts): vispirms skaitli sadalīt
saskaitāmajos, tad saskaitāmos - reizinātājos, bet tos - atkal
saskaitāmajos. Piemēram:
19=9+10=3*3+2*5=(1+1+1)*(1+1+1)+(1+1)*(1+1+1+1+1).
Ja iekavas neskaita, tad operāciju un operandu kopskaits te iznāk 25. Tas ir
mazāk nekā pirmā (un otrā) veida izteiksmē 19=1+1+1+1+1+1+..., kur to ir 37.
Bet ir skaitļi, kuriem trešā veida pieraksts neiznāk īsāks par otrā veida
pierakstu. Tos varētu saukt par *trešā veida pirmskaitļiem *(parastie
pirmskaitļi tad būtu otrā veida pirmskaitļi). Eksperimenti liecina, ka tādas
ir divnieka pakāpes, kurām īsākais pieraksts ir otrā veida: (1+1)*(1+1)*....
Bet tādi ir vēl arī citi skaitļi: 3, 5, 6, 7, 9, 10, 12, 14, 18, 20, 21, 24,
25, 27, 30, 35, 36, ...
-----
Vispirms ievērosim, ka izsakot skaitli jebkura veida pierakstā pēdējā solī
mēs aizvietosim visus virknes skaitļus ar vieninieku summu.
Tālāk daži secinājumi:
1. Jebkura veida pierakstā operatoru un operandu summa, būs atkarīga no
pirms pēdējā soļa izvirzījumā esošo skaitļu summas. Ja šo summu apzīmējam ar
S tad operandu un operatoru skaits pēc pēdējā soļa pielietošanas būs vienāds
ar 2S-1
Sekas: Jebkura veida pierakstā izdevīgākais izvirzījums būs tāds, kurā šī
summa pirms pēdējā soļa būs vismazākā.

Tālāk ievērosim, ka otrā veida pieraksts ir reizinājums no pirmā veida
pierakstiem un tāpēc:
2.Veicot izvirzījumu otrā veida pierakstā jebkuram skaitlim N
visizdevīgākais izvirzījums būs tieši viens - tas kur pirms pēdējā soļa
virknē atradīsies skaitļa N pirmreizinātāji. Šis secinājums seko no tā, ka
tikai pirmskaitļus ir neizdevīgi izteikt otrā veida pierakstā un tāpēc dalot
skaitli reizinātājos ir jāapstājas tikai pie tā sadalījuma pirmreizinātājos.

Gluži tāpat - trešā veida pieraksts ir summa no otrā veida pierakstiem un
tāpēc:
3.Veicot izvirzījumu trešā veida pierakstā skaitlim N visizdevīgākais
izvirzījums būs tāds, kurā pirms pēdējā soļā virknē būs tikai trešā veida
pirmskaitļi (t.i. skaitļi kurus nav izdevīgi izteikt trešajā pieraksta
formā(parastie pirmskaitļi mūsu terminoloģijā ir otrā veida pirmskaitļi, jo
tos nav izdevīgi izteikt otrajā pieraksta formā)). Arī šis secinājums izriet
no tā, ka skaitli būs izdevīgi dalīt saskaitāmajos tik ilgi, kamēr katrs
saskaitāmais nebūs trešā veida pirmskaitlis, jo pretējā gadījumā to
saskaitāmo, kas nav trešā veida pirmskaitlis ir izdevīgi sadalīt vēl sīkākos
saskaitāmajos.

Tāpat ceturtā veida pieraksts(ja pareizi saprotu) ir reizinājums no trešā
veida pierakstiem tāpēc:
4. Veicot ceturtā veida izvirzījumu jebkuram skaitlim N arī vērts apstāties
būs tikai tad, kad katrs no reizinātājiem būs skaitlis, kuru ceturtā veida
pierakstā nav izdevīgi izteikt t.i. ceturtā veida pirmskaitlis un tāpēc N
izdevigakais izvirzijums pirms pedeja solja saturees tikai 4taa veida
izvirzijumus..

Taapat kaa rekursiivi veidojam jaunus pierakstus, taapat arii varam
turpinaat veidot šādas teorēmas.. redzams, ka šeit būtībā var izdarīt
vispārīgu secinājumu - jebkurā pieraksta veidā, visizdevīgākais izvirzījums
konkrētam skaitlim, pirms pēdējā soļa saturēs tikai šī pieraksta veidam
atbilstošos pirmskaitļus. Tas izreit no tā kā tiek veidoti paši pieraksti.
Svarīgi gan pieminēt, ka visos pierakstos aiz otrā pieraksta veida, nevar
garantēt(vismaz pagaidām), ka izdevīgākais izvirzījums būs tikai viens.. Bet
var garantēt vismaz to, ka būs visviens izvirzījums, kurš būs vismaz tikpat
izdevīgs kā pārējie, un kurā visi skaitļi pirms pēdējā soļa būs atbilstošā
veida pirmskaitļi.

Tālāk var novērot, ka sadalot skaitli N divos rezinātājos, jo tuvāki
reizinātāji būs viens otram, jo mazāka būs to summa. Attiecīgi, ja no N var
izvilkt kvadrātsakni, tad divi vienādi reizinātāji dos vismazāko summu. Šo
varam vispārināt arī uz vairākiem reizinātājiem. Jo tuvāk vairāki skaitļa N
reizinātāji atrodas viens otram, jo mazāka ir to summa(ja salidzina ar ta
pasha skaitlja sadalijumu citos reizinataajos, kuri atrodas taalaak viens no
otra). Piem: 16 = 8*2 un 8+2 =10, bet 16=4*4 un 4+4=8

5. No augstāk aprakstītā var izsecināt: jo skaitlja N pirmreizinaataaji
atrodas tuvaaks viens otram(jo mazaaka ir videeja nobiide no to videejaas
veertiibas), jo izdeviigaaks skaitlim N buus otrais pieraksta veids. Tālāk -
jo izdevīgāks ir skaitlim ir tā otrais pieraksta veids, jo intuitīvi mazākas
cerības, ka trešajā pieraksta veidā to varēs izvirzīt vēl izdevīgāk. Un
tātad, jo mazāka ir skaitļa N pirmreizinātāju vidējā nobīde no to vidējās
vērtības, jo lielāka ir iespēja, ka šis skaitlis ir treša veida
pirmskaitlis..(šis secinājums neattiecas uz pirmskaitļiem)
Attiecīgi visām pirmskaitļu pakāpēm, kas lielākas par 2, šī nobīde ir 0(piem
2*2*2*2 vai 3*3*3*3 vai 17*17*17*17 utt). un tātad ir maksimāla varbūtība,
ka šie skaitļi ir trešā veida pirmskaitļi. Tas manuprāt izskaidro kāpēc
visas divnieka pakāpes(ar patoloģiskiem gadījumiem) ir treša veida
pirmskaitļi un izvirza arī hipotēzi, ka visas pirmskaitļu pakāpes(atskaitot
nulto un pirmo) ir trešā veida pirmskaitļi.

Uz doto brīdi nav pārliecinošu rezultātu par to kurā virzienā būtu meklējams
patvaļīga skaitļa trešā veida pieraksts - bet vajadzētu tos iegūt, lai
varētu uzrakstīt optimālāku algoritmu eksperimenta veikšanai..

Tas laikam uz doto brīdi arī viss, ja esmu ko būtisku aizmirsis tad gan jau
atcerēšos un papildināšu šo email.

Dawis