Binomni teorem i matematička indukcija u SAGE-u

verzija: SageMath 9.4

Računanje faktorijela

5!=120

In [1]:
factorial(5)
Out[1]:
120

0!=1

In [2]:
factorial(0)
Out[2]:
1

100! jednako je ??  :-)

In [3]:
factorial(100)
Out[3]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Računanje binomnih koeficijenata

$\displaystyle\binom{6}{4}=15$

In [4]:
binomial(6,4)
Out[4]:
15

$\displaystyle\binom{100}{98}=4950$

In [5]:
binomial(100,98)
Out[5]:
4950

$\displaystyle\binom{n}{0}=1$

In [6]:
var('n')
binomial(n,0)
Out[6]:
1

$\displaystyle\binom{n}{1}=n$

In [7]:
binomial(n,1)
Out[7]:
n

$\displaystyle\binom{n}{n}=1$

In [8]:
binomial(n,n)
Out[8]:
1

$\displaystyle\binom{n}{3}=\frac{1}{6}n(n-1)(n-2)$

In [9]:
%display latex
binomial(n,3)
Out[9]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{6} \, {\left(n - 1\right)} {\left(n - 2\right)} n\]

Svojstvo simetrije

In [10]:
binomial(n,3)==binomial(n,n-3)
Out[10]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{6} \, {\left(n - 1\right)} {\left(n - 2\right)} n = \frac{1}{6} \, {\left(n - 1\right)} {\left(n - 2\right)} n\]
In [11]:
%display plain
binomial(n,3)-binomial(n,n-3)
Out[11]:
0
In [12]:
bool(binomial(n,3)==binomial(n,n-3))
Out[12]:
True

Binomni teorem

In [13]:
var('x,y')
Out[13]:
(x, y)

$(x+y)^5=x^5+5x^4y+10x^3y^2+10x^2y^3+5xy^4+y^5$

In [14]:
%display latex
expand((x+y)^5)
Out[14]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}x^{5} + 5 \, x^{4} y + 10 \, x^{3} y^{2} + 10 \, x^{2} y^{3} + 5 \, x y^{4} + y^{5}\]

$(x+y)^{50}=\cdots$  :-)

In [15]:
expand((x+y)^50)
Out[15]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}x^{50} + 50 \, x^{49} y + 1225 \, x^{48} y^{2} + 19600 \, x^{47} y^{3} + 230300 \, x^{46} y^{4} + 2118760 \, x^{45} y^{5} + 15890700 \, x^{44} y^{6} + 99884400 \, x^{43} y^{7} + 536878650 \, x^{42} y^{8} + 2505433700 \, x^{41} y^{9} + 10272278170 \, x^{40} y^{10} + 37353738800 \, x^{39} y^{11} + 121399651100 \, x^{38} y^{12} + 354860518600 \, x^{37} y^{13} + 937845656300 \, x^{36} y^{14} + 2250829575120 \, x^{35} y^{15} + 4923689695575 \, x^{34} y^{16} + 9847379391150 \, x^{33} y^{17} + 18053528883775 \, x^{32} y^{18} + 30405943383200 \, x^{31} y^{19} + 47129212243960 \, x^{30} y^{20} + 67327446062800 \, x^{29} y^{21} + 88749815264600 \, x^{28} y^{22} + 108043253365600 \, x^{27} y^{23} + 121548660036300 \, x^{26} y^{24} + 126410606437752 \, x^{25} y^{25} + 121548660036300 \, x^{24} y^{26} + 108043253365600 \, x^{23} y^{27} + 88749815264600 \, x^{22} y^{28} + 67327446062800 \, x^{21} y^{29} + 47129212243960 \, x^{20} y^{30} + 30405943383200 \, x^{19} y^{31} + 18053528883775 \, x^{18} y^{32} + 9847379391150 \, x^{17} y^{33} + 4923689695575 \, x^{16} y^{34} + 2250829575120 \, x^{15} y^{35} + 937845656300 \, x^{14} y^{36} + 354860518600 \, x^{13} y^{37} + 121399651100 \, x^{12} y^{38} + 37353738800 \, x^{11} y^{39} + 10272278170 \, x^{10} y^{40} + 2505433700 \, x^{9} y^{41} + 536878650 \, x^{8} y^{42} + 99884400 \, x^{7} y^{43} + 15890700 \, x^{6} y^{44} + 2118760 \, x^{5} y^{45} + 230300 \, x^{4} y^{46} + 19600 \, x^{3} y^{47} + 1225 \, x^{2} y^{48} + 50 \, x y^{49} + y^{50}\]

Zadatak

Pomoću binomnog teorema raspišite izraz $(\sqrt[3]{x}+x^2)^4$.

In [16]:
expand((x^(1/3)+x^2)^4)
Out[16]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}x^{8} + 4 \, x^{\frac{19}{3}} + 6 \, x^{\frac{14}{3}} + 4 \, x^{3} + x^{\frac{4}{3}}\]

Zadatak

Pomoću binomnog teorema raspišite izraz $(\sqrt[3]{x}-x^2)^4$.

In [17]:
expand((x^(1/3)-x^2)^4)
Out[17]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}x^{8} - 4 \, x^{\frac{19}{3}} + 6 \, x^{\frac{14}{3}} - 4 \, x^{3} + x^{\frac{4}{3}}\]

Zadatak

Zadan je binom $\Big(\sqrt[3]{x^2}+\sqrt[4]{x^3}\Big)^{11}$.

  • Odredite član uz $x^8$.
  • Odredite peti član u razvoju tog binoma
  • Da li postoji član u tom razvoju koji ne sadrži $x$?

član uz $x^8$

In [18]:
f=expand((x^(2/3)+x^(3/4))^11)
f.coefficient(x^8)
Out[18]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}165\]

peti član

In [19]:
f
Out[19]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}x^{\frac{33}{4}} + 11 \, x^{\frac{49}{6}} + 55 \, x^{\frac{97}{12}} + 165 \, x^{8} + 330 \, x^{\frac{95}{12}} + 462 \, x^{\frac{47}{6}} + 462 \, x^{\frac{31}{4}} + 330 \, x^{\frac{23}{3}} + 165 \, x^{\frac{91}{12}} + 55 \, x^{\frac{15}{2}} + 11 \, x^{\frac{89}{12}} + x^{\frac{22}{3}}\]
In [20]:
f.operands()
Out[20]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[x^{\frac{33}{4}}, 11 \, x^{\frac{49}{6}}, 55 \, x^{\frac{97}{12}}, 165 \, x^{8}, 330 \, x^{\frac{95}{12}}, 462 \, x^{\frac{47}{6}}, 462 \, x^{\frac{31}{4}}, 330 \, x^{\frac{23}{3}}, 165 \, x^{\frac{91}{12}}, 55 \, x^{\frac{15}{2}}, 11 \, x^{\frac{89}{12}}, x^{\frac{22}{3}}\right]\]

Sage ima svoj raspored elemenata (sortira po padajućim potencijama) pa se njegov peti član ne mora popudarati s našim petim članom (to je stvar definicije i dogovora jer mi sortiramo članove po brojaču po kojemu ide suma u binomnoj formuli.

In [21]:
f.operands()[4]
Out[21]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}330 \, x^{\frac{95}{12}}\]

Stoga definiramo funkciju koja će biti u skladu s našom definicijom

In [22]:
def KTIclan(a,b,n,k):
    return binomial(n,k-1)*a^(n-k+1)*b^(k-1)
In [23]:
KTIclan(x^(2/3),x^(3/4),11,5)
Out[23]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}330 \, x^{\frac{23}{3}}\]

nema člana koji ne sadrži $x$

In [24]:
f.coefficient(x^0)
Out[24]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}0\]

Zadatak

Pomoću binomnog teorema raspišite i sredite izraz $\Big(\frac{1}{\sqrt[4]{y^3}}-\sqrt{y}\Big)^4$.

In [25]:
expand((1/(y^(3/4))-y^(1/2))^4)
Out[25]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}y^{2} - 4 \, y^{\frac{3}{4}} + \frac{6}{\sqrt{y}} - \frac{4}{y^{\frac{7}{4}}} + \frac{1}{y^{3}}\]

Zadatak

Odredite sve prirodne brojeve $n\in\mathbb{N}$ za koje vrijedi $\binom{n}{4}+2\binom{n}{2}=\binom{n+1}{4}$.

In [26]:
solve(binomial(n,4)+2*binomial(n,2)==binomial(n+1,4),n)
Out[26]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[n = 0, n = 1, n = 8\right]\]

Napomena. Na Matematici 1 se binomni koeficijent $\binom{n}{k}$ definira samo za $n\in\mathbb{N}$, $k\in\mathbb{N}\cup\{0\}$ i uz pretpostavku da je $k\leq n$. Stoga bi u našem slučaju gornja rješenja $n=0$ i $n=1$ otpala i jednadžba ima samo jedno rješenje $n=8$. Međutim, općenito se binomni koeficijent $\binom{\alpha}{k}$ može definirati za bilo koji $\alpha\in\mathbb{R}$ i $k\in\mathbb{N}\cup\{0\}$. Naravno, SAGE zna tu definiciju i zato daje tri korektna rješenja.

$\displaystyle\binom{0}{4}=0$

In [27]:
binomial(0,4)
Out[27]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}0\]

$\displaystyle\binom{1}{4}=0$

In [28]:
binomial(1,4)
Out[28]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}0\]

$\displaystyle\binom{-\frac{1}{2}}{5}=-\frac{63}{256}$

In [29]:
binomial(-1/2,5)
Out[29]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}-\frac{63}{256}\]

Općenitija definicija binomnog koeficijenta je


$$\displaystyle\binom{\alpha}{0}=1,\quad\binom{\alpha}{k}=\frac{\alpha\cdot(\alpha-1)\cdot(\alpha-2)\cdots(\alpha-k+2)\cdot(\alpha-k+1)}{k!}, \quad\alpha\in\mathbb{R},\quad k\in\mathbb{N}$$

Matematička indukcija

Naravno da SAGE nije svjestan principa matematičke indukcije, niti pak računalo može biti tako kreativno i samostalno u donošenju zaključaka kao čovjek. Ovdje je namjera da pokažemo kako je SAGE "jako pametan", tj. da "zna računati" sume određenih $n$ brojeva čiju istinitost dokazujemo matematičkom indukcijom. Dakle, iako je za otkrivanje formula određenih suma $n$ brojeva potrebna kreativnost, ipak postoje algoritmi koji mogu tu kreativnost automatizirati, tako da je i računalo tada "sposobno" otkrivati takve formule.

In [30]:
var('k,n')
Out[30]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left(k, n\right)\]

$1+2+3+\cdots+n=\frac{n(n+1)}{2}$

In [31]:
sum(k,k,1,n)
Out[31]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{2} \, n^{2} + \frac{1}{2} \, n\]
In [32]:
sum(k,k,1,n).factor()
Out[32]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{2} \, {\left(n + 1\right)} n\]

$1^2+2^2+3^2+\cdots+n^2=\frac{1}{6}n(n+1)(2n+1)$

In [33]:
sum(k^2,k,1,n)
Out[33]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{3} \, n^{3} + \frac{1}{2} \, n^{2} + \frac{1}{6} \, n\]
In [34]:
sum(k^2,k,1,n).factor()
Out[34]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{6} \, {\left(2 \, n + 1\right)} {\left(n + 1\right)} n\]

$1^3+2^3+3^3+\cdots+n^3=\frac{n^2(n+1)^2}{4}$

In [35]:
sum(k^3,k,1,n)
Out[35]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{4} \, n^{4} + \frac{1}{2} \, n^{3} + \frac{1}{4} \, n^{2}\]
In [36]:
sum(k^3,k,1,n).factor()
Out[36]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{4} \, {\left(n + 1\right)}^{2} n^{2}\]

$1+3+5+\cdots+(2n-1)=n^2$

In [37]:
sum(2*k-1,k,1,n)
Out[37]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}n^{2}\]

$4+20+48+\cdots+2n(3n-1)=2n^2(n+1)$

In [38]:
sum(2*k*(3*k-1),k,1,n)
Out[38]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}2 \, n^{3} + 2 \, n^{2}\]
In [39]:
sum(2*k*(3*k-1),k,1,n).factor()
Out[39]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}2 \, {\left(n + 1\right)} n^{2}\]

$\displaystyle\sum_{k=0}^n{(6k^2-4k^3)}=n(n+1)(1+n-n^2)$

In [40]:
sum(6*k^2-4*k^3,k,0,n)
Out[40]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}-n^{4} + 2 \, n^{2} + n\]
In [41]:
sum(6*k^2-4*k^3,k,0,n).factor()
Out[41]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}-{\left(n^{2} - n - 1\right)} {\left(n + 1\right)} n\]

Iako na računalu ne možemo provesti matematičku indukciju, možemo provesti nepotpunu indukciju, tj. tvrdnju provjeriti za puno prirodnih brojeva. Naravno, to nije dokaz, nego samo eksperiment, a matematika eksperiment ne priznaje kao dokaz.

$19\mid 7\cdot 5^{2n}+12\cdot 6^n$

Napravimo listu brojeva oblika $7\cdot 5^{2n}+12\cdot 6^n$ za $n\in\{1,2,3,\ldots,99,100\}$. Vidimo da ti brojevi brzo rastu, a to je zbog toga što eksponencijalna funkcija brzo raste.

In [42]:
print([7*5^(2*n)+12*6^n for n in range(1,101)])

[247, 4807, 111967, 2749927, 68452687, 1709544247, 42727968607, 1068135389767, 26703001791727, 667572747078487, 16689304890674047, 417232539549122407, 10430812992421687567, 260770321832703953527, 6519258027950569424287, 162981450591562059123847, 4074536264145838419196207, 101863406599786682126505367, 2546585164971511383042235327, 63664629124148850555333490087, 1591615728102887659759002893647, 39790393202567189869229066190007, 994759830064149736982250617843167, 24868995751603563366065409224637127, 621724893790088003800690093287275887, 15543122344752193612911581508209983447, 388578058618804801430155512761418103807, 9714451465470119802398083669372463700967, 242861286636752993659817266836333659158927, 6071532165918824833094622721520473878781687, 151788304147970620776960714341684641368393247, 3794707603699265519121588736364152800602937607, 94867690092481637976225143676036040613432078767, 2371692252312040949394741143502494338925953800727, 59292306307801023734803203897171918414689756007487, 1482307657695025593369688149286955320016489366123047, 37057691442375639834239852043319827158307706948691407, 926442286059390995855982190949871343905065510490976567, 23161057151484774896399470112948037587310874782916562527, 579026428787119372409986244858908463620877291696766953287, 14475660719677984310249653073683956734150564825162291172847, 361891517991949607756241308555366389215535915825515983365207, 9047287949798740193906032604163764555559028666816651808394367, 226182198744968504847650814445771742839999501297488808555444327, 5654554968624212621191270357194359344706130240199655293959619087, 141363874215605315529781758906159378259890112251565992829431542647, 3534096855390132888244543972511786824350673943768597483618434959007, 88352421384753322206113599311941484815887375419091623067756752332167, 2208810534618833055152839982793418005639907546426550692557694078446127, 55220263365470826378820999569804735452454027626359328009125003582004887, 1380506584136770659470524989244934098180088724453156564399220999275232447, 34512664603419266486763124731122246725714646314093954295007100440231472807, 862816615085481662169078118278049533770140727068939098485336963755890789967, 21570415377137041554226952956951198538017165592023018908794380810397893567927, 539260384428426038855673823923779724613011024292372721399825260558951082110687, 13481509610710650971391845598094491682300766914260101527075425955767799510242247, 337037740267766274284796139952362283459372120698207239129364415544959122500906607, 8425943506694156857119903498809057034895420704505409183948982988528562870991767767, 210648587667353921427997587470226425562852223734936598833013810312641580625608809727, 5266214691683848035699939686755660637214105830107223186231080671412604568745107936487, 131655367292096200892498492168891515919209447173083428948211429266894504537257024572047, 3291384182302405022312462304222287897913376987849502819459892206561838955343201571260407, 82284604557560125557811557605557197447433269547372073061024944013382831935050695023265567, 2057115113939003138945288940138929936183424807791108841972789433430591946685091310032171527, 51427877848475078473632223503473248404571178609418563142002730834340925556980226357507482287, 1285696946211876961840805587586831210114192815723309131106166240849979900263623320577906221847, 32142423655296924046020139689670780252854300496009798592990743841198238074625288984288970534207, 803560591382423101150503492241769506321354393017807386716788122949648395273840460426272153283367, 20089014784560577528762587306044237658033841109150559199271820235259364542295260925571091171653327, 502225369614014438219064682651105941450845915430996227169908208850593041520077019628763003328748087, 12555634240350360955476617066277648536271147211988299162376381439079479605778098469655989427443191647, 313890856008759023886915426656941213406778676256987839958181593283874911551109499615021221751426728007, 7847271400218975597172885666423530335169466882168378164347172175938200317217679717617259460177749821167, 196181785005474389929322141660588258379236671908671547101035098461502973101081646303881860002796235255127, 4904544625136859748233053541514706459480916796843561235480012225915862118550879077777748741060020819733887, 122613615628421493705826338537867661487022919915849666234725114234166279709915004465527931972441210123481447, 3065340390710537342645658463446691537175572997864805467954476707371775353224733276764703579986674390867841807, 76633509767763433566141461586167288429389324946431519571380010793400093993479480909876621183720724598380878967, 1915837744194085839153536539654182210734733123659656286519608828489636610814153916691469719697341303919630976927, 47895943604852145978838413491354555268368328091484616946400872064168720836216849280954068133059471731751428439687, 1197398590121303649470960337283863881709208202287074682360485709715784854300599240205855654170242428096349635091247, 29934964753032591236774008432096597042730205057176622611214926191564022357886049054238415059318594511224124421875607, 748374118825814780919350210802414926068255126429414098593589855481116964949377634650512518713340065633495411814456767, 18709352970645369522983755270060373151706378160735343664719046591180022559747799316030125821215752857954739102966818727, 467733824266134238074593881751509328792659454018383538817251966004413154609775133599357022650687328751572600419802865487, 11693345606653355951864847043787733219816486350459588153626953957459804408940859244175548828988944262605539747568866021047, 292333640166333898796621176094693330495412158761489701939847777780591963485700366529538460301054172828035842111664416829407, 7308341004158347469915529402367333262385303969037242537091238017579380206715582475789359944984337718278280143326267018554567, 182708525103958686747888235059183331559632599225931063358851211877871991885328001770039389249356343342421308126364615050780527, 4567713127598967168697205876479583288990814980648276583560701865577124717437830683502817074982395985873318530418363013791011287, 114192828189974179217430146911989582224770374516206914586554076051210067457773550923081420937050824060709678224014561169904270847, 2854820704749354480435753672799739555619259362905172864649071077750943383575305476090101487801216148001002245381696944198380703207, 71370517618733862010893841819993488890481484072629321616138092002597734772168437120330932981280076978924617873230421094664161172367, 1784262940468346550272346045499837222262037101815733040402920190417888270400925729316743699249499964146512817262888512304831890862327, 44606573511708663756808651137495930556550927545393326010069812102564876166603432040769414729542487341703204654164980717250164440877087, 1115164337792716593920216278437398263913773188634833150251726146616827920604567533866340301728392112970822421689681125389030314037840647, 27879108444817914848005406960934956597844329715870828756293038729736934113751078743741137144148782400840014374255367779472415069041497007, 696977711120447871200135174023373914946108242896770718907325278629320769435598310976024206209353437480417082348464232355290320034610310167, 17424442778011196780003379350584347873652706072419267972683127828048403735440885828695579820867639201766927396664086036093137660716695064127, 435611069450279919500084483764608696841317651810481699317078170875102400383327714043159343515493799632712186944317032265593719477026000462887]

Pogledajmo ostake koje daju prvih 100 brojeva oblika $7\cdot 5^{2n}+12\cdot 6^n$ pri dijeljenju s 19

In [43]:
[mod(7*5^(2*n)+12*6^n,19) for n in range(1,101)]
Out[43]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\right]\]

Možemo tvrdnju provjeriti i za prvih 1000 brojeva oblika $7\cdot 5^{2n}+12\cdot 6^n$

In [44]:
[mod(7*5^(2*n)+12*6^n,19) for n in range(1,1001)]
Out[44]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\right]\]

Dakle, za prvih 1000 prirodnih brojeva vrijedi tvrdnja $19\mid 7\cdot 5^{2n}+12\cdot 6^n$. Međutim, to još uvijek nije dokaz da tvrdnja vrijedi za svaki prirodni broj $n$, iako je ona provjerena za "puno" prirodnih brojeva.

Eulerovi prosti brojevi

Brojevi oblika $n^2+n+41$ su prosti za svaki $n\in\mathbb{N}$.

U današnje vrijeme, kada imamo tako jaka računala i tako prekrasne besplatne alate kao što je SAGE, Eulerovu tvrdnju je lako opovrgnuti, tj. dokazati da ona nije istinita.

Prvih 39 takvih brojeva

In [45]:
[n^2+n+41 for n in range(1,40)]
Out[45]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601\right]\]

jesu zaista prosti

In [46]:
[is_prime(n^2+n+41) for n in range(1,40)]
Out[46]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[\mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}, \mathrm{True}\right]\]

No, za $n=40$ i $n=41$ brojevi oblika $n^2+n+41$ su složeni

In [47]:
[is_prime(n^2+n+41) for n in [40,41]]
Out[47]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}\left[\mathrm{False}, \mathrm{False}\right]\]

No, ima još dosta $n$-ova za koje su brojevi oblika $n^2+n+41$ složeni. Pogledajmo koliko među prvih 1000 brojeva tog oblika ima složenih.

In [48]:
lista1000=[is_prime(n^2+n+41) for n in range(1,1001)]
print(lista1000)

[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False, False, True, True, False, True, True, True, True, False, True, True, True, True, True, True, False, True, True, True, True, True, True, True, True, False, True, True, True, True, True, True, True, True, True, True, False, True, True, True, True, False, False, True, False, True, True, False, True, False, True, False, True, True, True, True, False, True, True, True, True, True, False, True, False, True, True, True, True, False, True, True, True, True, True, True, True, False, True, True, True, False, False, False, True, True, False, False, True, True, False, True, True, True, True, True, False, True, False, True, False, True, True, False, True, True, True, False, True, True, True, True, True, True, True, False, True, True, True, False, True, False, False, False, False, True, True, True, True, True, False, True, False, False, True, True, True, True, False, True, True, True, True, True, False, False, False, False, True, True, False, True, True, True, True, True, True, True, True, True, True, False, True, True, False, False, True, False, False, False, True, True, True, False, True, False, False, False, False, True, True, True, True, True, True, True, True, True, True, True, True, True, False, True, False, True, False, False, True, False, True, True, False, True, False, False, False, True, False, False, True, False, False, True, True, False, False, True, True, False, True, False, True, True, True, False, False, True, False, True, False, False, True, True, True, True, True, True, False, False, True, True, True, False, False, True, False, False, True, False, True, False, True, True, True, False, False, True, False, False, False, False, False, True, True, True, True, True, True, False, True, True, False, True, False, True, True, True, True, True, True, False, True, True, True, False, False, False, False, False, False, False, True, True, False, True, False, True, False, True, True, True, False, True, False, False, True, False, True, False, True, True, True, True, True, True, True, False, True, True, False, False, True, True, False, True, True, False, False, False, False, True, True, False, False, True, True, True, False, True, False, False, True, False, True, False, True, True, False, False, True, True, True, True, True, False, True, True, True, False, True, False, False, True, True, True, False, False, False, False, False, True, True, True, True, True, False, True, False, True, False, False, False, True, True, False, True, False, False, True, True, False, False, True, True, True, True, True, True, True, False, True, False, False, True, False, True, True, True, False, False, False, True, True, False, True, True, True, True, False, False, True, True, False, True, True, False, False, True, True, True, False, False, False, False, True, True, False, True, True, False, False, True, False, True, True, True, False, True, False, True, False, False, True, False, True, False, True, True, True, False, True, False, True, False, True, False, False, True, True, True, True, True, True, False, True, False, False, True, False, True, True, True, True, False, True, False, False, True, True, False, False, False, False, True, True, True, True, True, True, True, True, True, True, False, False, False, False, True, True, True, True, True, False, True, True, False, False, True, True, False, False, False, False, True, True, False, True, True, False, False, False, True, False, False, True, True, False, False, False, True, True, False, False, True, False, False, False, True, False, True, True, True, False, True, True, True, True, True, True, False, True, True, False, True, False, True, True, False, False, True, False, False, False, False, False, False, True, True, True, False, True, False, True, False, True, True, True, False, True, False, True, False, False, True, True, False, True, True, False, True, True, False, False, False, False, False, True, True, True, True, True, False, True, True, False, False, False, True, True, False, False, False, False, False, False, False, True, True, False, False, False, True, True, True, False, False, True, True, False, False, True, False, True, True, False, False, True, True, False, True, True, False, False, True, True, False, False, True, False, True, False, False, False, False, True, True, False, True, True, True, False, True, True, True, False, False, True, True, True, True, False, True, True, True, True, True, False, True, False, True, True, False, False, False, True, False, False, False, False, False, True, True, True, False, False, True, False, True, False, False, True, False, False, False, True, True, True, False, True, True, False, True, True, False, False, True, False, False, False, True, True, False, False, True, False, False, True, False, False, True, True, False, False, False, True, False, True, False, True, False, False, True, True, True, False, False, False, False, False, False, False, True, False, True, True, True, False, True, True, True, True, True, True, False, False, False, True, False, False, False, True, False, False, False, False, True, False, True, True, True, True, True, True, False, False, False, True, True, True, True, True, True, False, False, True, False, False, False, False, True, False, True, False, False, True, False, False, False, True, False, False, True, True, True, False, True, False, True, False, True, True, True, True, False, True, False, True, False, True, False, False, True, True, True, False, True, True, True, True, False, False, False, True, True, False, False, False, False, True, True, False, False, True, False, False, False, False, True, True, False, True, False, True, True, False, False, False, False, False, True, True, False, True, False, False, False, True, False, True, True, True, True, True, True, True, True, False, True, True, False, True, False, False, False, True, True, False, True, True, False, False, True, True, True, False, False, False, True, False, True, True, False, False, True, True, False, True, True, True, True, False, False, True, True, True, True, False, False, True, False, False, False, False, False, True, False, False, False, False, False, True, True, True, True, False, True, False, True, False, True]

Vidimo da na dosta mjesta piše False, što znači da je broj složen, tj. da nije prost. No, da mi ručno ne brojimo koliko ih stvarno ima, neka SAGE to prebroji.

In [49]:
lista1000.count(False)
Out[49]:
\[\newcommand{\Bold}[1]{\mathbf{#1}}419\]

Dakle, među prvih 1000 brojeva oblika $n^2+n+41$, čak njih 419 su složeni, tj. nisu prosti. Ugrubo rečeno, među prvih 1000 takvih brojeva, oko 40% njih su složeni brojevi, a to je dosta daleko od Eulerove hipoteze da su svi oni prosti. Eh, da je Euler imao današnja računala i SAGE, ne bi napravio takvu pogrešku. No, lako je sada biti pametan. :-)

In [ ]: