Binomni poučak i matematička indukcija u pythonu

In [1]:
import platform
In [2]:
platform.platform()
Out[2]:
'Linux-4.17.19-1-MANJARO-x86_64-with-arch-Manjaro-Linux'
In [3]:
platform.python_version()
Out[3]:
'3.7.0'
In [4]:
import sympy as sp
In [5]:
sp.__version__
Out[5]:
'1.2'
In [6]:
sp.init_printing()

Funkcija za kontrolirani ispis po retcima

In [7]:
def ispis(objekt,br):
    objekt=str(objekt)
    d=len(objekt)
    red=d // br
    ostatak=d % br
    za_ispis=""
    for k in range(red):
        za_ispis=za_ispis+objekt[k*br:(k+1)*br]+"\n"
    if ostatak == 0:
        za_ispis = za_ispis[:-1]
    else:
        za_ispis = za_ispis+objekt[red*br:]
    print(za_ispis)

Računanje faktorijela

$5!=120$

In [8]:
sp.factorial(5)
Out[8]:
$$120$$

$0!=1$

In [9]:
sp.factorial(0)
Out[9]:
$$1$$

$100!$ jednako je ?? :-)

In [10]:
sp.factorial(100)
Out[10]:
$$93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000$$
In [11]:
sp.pprint(sp.factorial(100))

933262154439441526816992388562667004907159682643816214685929638952175999932299
156089414639761565182862536979208272237582511852109168640000000000000000000000
00

Računanje binomnih koeficijenata

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

In [12]:
sp.binomial(6,4)
Out[12]:
$$15$$

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

In [13]:
sp.binomial(100,98)
Out[13]:
$$4950$$

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

In [14]:
n = sp.symbols('n', integer=True)
sp.binomial(n,0)
Out[14]:
$$1$$

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

In [15]:
sp.binomial(n,1)
Out[15]:
$$n$$

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

In [16]:
sp.binomial(n,n).expand(func=True)
Out[16]:
$${\binom{n}{n}}$$
In [17]:
sp.binomial(n,3).expand(func=True)
Out[17]:
$$\frac{n^{3}}{6} - \frac{n^{2}}{2} + \frac{n}{3}$$

Svi binomni koeficijenti oblika $\binom{5}{k}$ za $k\in\{0,1,2,3,4,5\}$

In [18]:
sp.binomial_coefficients(5)
Out[18]:
$$\left \{ \left ( 0, \quad 5\right ) : 1, \quad \left ( 1, \quad 4\right ) : 5, \quad \left ( 2, \quad 3\right ) : 10, \quad \left ( 3, \quad 2\right ) : 10, \quad \left ( 4, \quad 1\right ) : 5, \quad \left ( 5, \quad 0\right ) : 1\right \}$$
In [19]:
sp.binomial_coefficients_list(5)
Out[19]:
$$\left [ 1, \quad 5, \quad 10, \quad 10, \quad 5, \quad 1\right ]$$

Binomni teorem

In [20]:
sp.var('x y');

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

In [21]:
sp.expand((x+y)**5)
Out[21]:
$$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 [22]:
ispis(sp.expand((x+y)**50),80)

x**50 + 50*x**49*y + 1225*x**48*y**2 + 19600*x**47*y**3 + 230300*x**46*y**4 + 21
18760*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 + 10804325
3365600*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 + 30405943383
200*x**19*y**31 + 18053528883775*x**18*y**32 + 9847379391150*x**17*y**33 + 49236
89695575*x**16*y**34 + 2250829575120*x**15*y**35 + 937845656300*x**14*y**36 + 35
4860518600*x**13*y**37 + 121399651100*x**12*y**38 + 37353738800*x**11*y**39 + 10
272278170*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 + 1960
0*x**3*y**47 + 1225*x**2*y**48 + 50*x*y**49 + y**50

Zadatak

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

In [23]:
sp.expand((x**sp.Rational(1,3)+x**2)**4)
Out[23]:
$$4 x^{\frac{19}{3}} + 6 x^{\frac{14}{3}} + x^{\frac{4}{3}} + x^{8} + 4 x^{3}$$

Zadatak

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

In [24]:
sp.expand((x**sp.Rational(1,3)-x**2)**4)
Out[24]:
$$- 4 x^{\frac{19}{3}} + 6 x^{\frac{14}{3}} + x^{\frac{4}{3}} + x^{8} - 4 x^{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 koji ne sadrži $x$
In [25]:
f=sp.expand((x**sp.Rational(2,3)+x**sp.Rational(3,4))**11)

koeficijent uz $x^8$

In [26]:
f.coeff(x**8)
Out[26]:
$$165$$

SymPy ima svoj raspored članova

In [27]:
f.args
Out[27]:
$$\left ( x^{\frac{22}{3}}, \quad x^{\frac{33}{4}}, \quad 11 x^{\frac{49}{6}}, \quad 11 x^{\frac{89}{12}}, \quad 55 x^{\frac{15}{2}}, \quad 55 x^{\frac{97}{12}}, \quad 165 x^{8}, \quad 165 x^{\frac{91}{12}}, \quad 330 x^{\frac{23}{3}}, \quad 330 x^{\frac{95}{12}}, \quad 462 x^{\frac{31}{4}}, \quad 462 x^{\frac{47}{6}}\right )$$

Stoga je najbolje da definiramo svoju funkciju

In [28]:
def KTIclan(a,b,n,k): 
    return sp.binomial(n,k-1)*a**(n-k+1)*b**(k-1)

peti član

In [29]:
KTIclan(x**sp.Rational(2,3),x**sp.Rational(3,4),11,5)
Out[29]:
$$330 x^{\frac{23}{3}}$$

Ne postoji član koji ne sadrži $x$, tj. svi članovi sadrže neku potenciju od $x^r$ za $r\neq 0$.

In [30]:
[t.has(x) for t in f.args]
Out[30]:
[True, True, True, True, True, True, True, True, True, True, True, True]

Zadatak

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

In [31]:
sp.expand((y**sp.Rational(-3,4)-y**sp.Rational(1,2))**4)
Out[31]:
$$- 4 y^{\frac{3}{4}} + y^{2} + \frac{1}{y^{3}} + \frac{6}{\sqrt{y}} - \frac{4}{y^{\frac{7}{4}}}$$

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\leqslant 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 $\alpha\in\mathbb{R}$ i $k\in\mathbb{N}\cup\{0\}$. Naravno, SymPy zna tu definiciju i zato daje tri korektna rješenja.

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

In [32]:
sp.binomial(0,4)
Out[32]:
$$0$$

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

In [33]:
sp.binomial(1,4)
Out[33]:
$$0$$

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

In [34]:
sp.binomial(sp.Rational(-1,2),5)
Out[34]:
$$- \frac{63}{256}$$

Općenita definicija binomnog koeficijenta glasi

$$\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},\ k\in\mathbb{N}$$

Matematička indukcija

Naravno da SymPy 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 SymPy "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 [35]:
sp.var('k n');

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

In [36]:
sp.summation(k,(k,1,n))
Out[36]:
$$\frac{n^{2}}{2} + \frac{n}{2}$$
In [37]:
sp.summation(k,(k,1,n)).factor()
Out[37]:
$$\frac{n \left(n + 1\right)}{2}$$

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

In [38]:
sp.summation(k**2,(k,1,n))
Out[38]:
$$\frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6}$$
In [39]:
sp.summation(k**2,(k,1,n)).factor()
Out[39]:
$$\frac{n \left(n + 1\right) \left(2 n + 1\right)}{6}$$

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

In [40]:
sp.summation(k**3,(k,1,n))
Out[40]:
$$\frac{n^{4}}{4} + \frac{n^{3}}{2} + \frac{n^{2}}{4}$$
In [41]:
sp.summation(k**3,(k,1,n)).factor()
Out[41]:
$$\frac{n^{2} \left(n + 1\right)^{2}}{4}$$

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

In [42]:
sp.summation(2*k-1,(k,1,n))
Out[42]:
$$n^{2}$$

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

In [43]:
sp.summation(2*k*(3*k-1),(k,1,n))
Out[43]:
$$2 n^{3} + 2 n^{2}$$
In [44]:
sp.summation(2*k*(3*k-1),(k,1,n)).factor()
Out[44]:
$$2 n^{2} \left(n + 1\right)$$

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

In [45]:
sp.summation(6*k**2-4*k**3,(k,1,n))
Out[45]:
$$- n^{4} + 2 n^{2} + n$$
In [46]:
sp.summation(6*k**2-4*k**3,(k,1,n)).factor()
Out[46]:
$$- n \left(n + 1\right) \left(n^{2} - n - 1\right)$$

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 [47]:
ispis([7*5**(2*n)+12*6**n for n in range(1,101)],120)

[247, 4807, 111967, 2749927, 68452687, 1709544247, 42727968607, 1068135389767, 26703001791727, 667572747078487, 16689304
890674047, 417232539549122407, 10430812992421687567, 260770321832703953527, 6519258027950569424287, 16298145059156205912
3847, 4074536264145838419196207, 101863406599786682126505367, 2546585164971511383042235327, 6366462912414885055533349008
7, 1591615728102887659759002893647, 39790393202567189869229066190007, 994759830064149736982250617843167, 248689957516035
63366065409224637127, 621724893790088003800690093287275887, 15543122344752193612911581508209983447, 38857805861880480143
0155512761418103807, 9714451465470119802398083669372463700967, 242861286636752993659817266836333659158927, 6071532165918
824833094622721520473878781687, 151788304147970620776960714341684641368393247, 37947076036992655191215887363641528006029
37607, 94867690092481637976225143676036040613432078767, 2371692252312040949394741143502494338925953800727, 5929230630780
1023734803203897171918414689756007487, 1482307657695025593369688149286955320016489366123047, 370576914423756398342398520
43319827158307706948691407, 926442286059390995855982190949871343905065510490976567, 231610571514847748963994701129480375
87310874782916562527, 579026428787119372409986244858908463620877291696766953287, 144756607196779843102496530736839567341
50564825162291172847, 361891517991949607756241308555366389215535915825515983365207, 904728794979874019390603260416376455
5559028666816651808394367, 226182198744968504847650814445771742839999501297488808555444327, 5654554968624212621191270357
194359344706130240199655293959619087, 141363874215605315529781758906159378259890112251565992829431542647, 35340968553901
32888244543972511786824350673943768597483618434959007, 88352421384753322206113599311941484815887375419091623067756752332
167, 2208810534618833055152839982793418005639907546426550692557694078446127, 5522026336547082637882099956980473545245402
7626359328009125003582004887, 1380506584136770659470524989244934098180088724453156564399220999275232447, 345126646034192
66486763124731122246725714646314093954295007100440231472807, 86281661508548166216907811827804953377014072706893909848533
6963755890789967, 21570415377137041554226952956951198538017165592023018908794380810397893567927, 53926038442842603885567
3823923779724613011024292372721399825260558951082110687, 134815096107106509713918455980944916823007669142601015270754259
55767799510242247, 337037740267766274284796139952362283459372120698207239129364415544959122500906607, 842594350669415685
7119903498809057034895420704505409183948982988528562870991767767, 210648587667353921427997587470226425562852223734936598
833013810312641580625608809727, 5266214691683848035699939686755660637214105830107223186231080671412604568745107936487, 1
31655367292096200892498492168891515919209447173083428948211429266894504537257024572047, 32913841823024050223124623042222
87897913376987849502819459892206561838955343201571260407, 82284604557560125557811557605557197447433269547372073061024944
013382831935050695023265567, 2057115113939003138945288940138929936183424807791108841972789433430591946685091310032171527
, 51427877848475078473632223503473248404571178609418563142002730834340925556980226357507482287, 128569694621187696184080
5587586831210114192815723309131106166240849979900263623320577906221847, 321424236552969240460201396896707802528543004960
09798592990743841198238074625288984288970534207, 80356059138242310115050349224176950632135439301780738671678812294964839
5273840460426272153283367, 200890147845605775287625873060442376580338411091505591992718202352593645422952609255710911716
53327, 502225369614014438219064682651105941450845915430996227169908208850593041520077019628763003328748087, 125556342403
50360955476617066277648536271147211988299162376381439079479605778098469655989427443191647, 31389085600875902388691542665
6941213406778676256987839958181593283874911551109499615021221751426728007, 784727140021897559717288566642353033516946688
2168378164347172175938200317217679717617259460177749821167, 196181785005474389929322141660588258379236671908671547101035
098461502973101081646303881860002796235255127, 4904544625136859748233053541514706459480916796843561235480012225915862118
550879077777748741060020819733887, 1226136156284214937058263385378676614870229199158496662347251142341662797099150044655
27931972441210123481447, 30653403907105373426456584634466915371755729978648054679544767073717753532247332767647035799866
74390867841807, 76633509767763433566141461586167288429389324946431519571380010793400093993479480909876621183720724598380
878967, 1915837744194085839153536539654182210734733123659656286519608828489636610814153916691469719697341303919630976927
, 47895943604852145978838413491354555268368328091484616946400872064168720836216849280954068133059471731751428439687, 119
7398590121303649470960337283863881709208202287074682360485709715784854300599240205855654170242428096349635091247, 299349
64753032591236774008432096597042730205057176622611214926191564022357886049054238415059318594511224124421875607, 74837411
8825814780919350210802414926068255126429414098593589855481116964949377634650512518713340065633495411814456767, 187093529
70645369522983755270060373151706378160735343664719046591180022559747799316030125821215752857954739102966818727, 46773382
4266134238074593881751509328792659454018383538817251966004413154609775133599357022650687328751572600419802865487, 116933
45606653355951864847043787733219816486350459588153626953957459804408940859244175548828988944262605539747568866021047, 29
233364016633389879662117609469333049541215876148970193984777778059196348570036652953846030105417282803584211166441682940
7, 730834100415834746991552940236733326238530396903724253709123801757938020671558247578935994498433771827828014332626701
8554567, 182708525103958686747888235059183331559632599225931063358851211877871991885328001770039389249356343342421308126
364615050780527, 4567713127598967168697205876479583288990814980648276583560701865577124717437830683502817074982395985873
318530418363013791011287, 1141928281899741792174301469119895822247703745162069145865540760512100674577735509230814209370
50824060709678224014561169904270847, 28548207047493544804357536727997395556192593629051728646490710777509433835753054760
90101487801216148001002245381696944198380703207, 71370517618733862010893841819993488890481484072629321616138092002597734
772168437120330932981280076978924617873230421094664161172367, 1784262940468346550272346045499837222262037101815733040402
920190417888270400925729316743699249499964146512817262888512304831890862327, 4460657351170866375680865113749593055655092
7545393326010069812102564876166603432040769414729542487341703204654164980717250164440877087, 111516433779271659392021627
8437398263913773188634833150251726146616827920604567533866340301728392112970822421689681125389030314037840647, 278791084
448179148480054069609349565978443297158708287562930387297369341137510787437411371441487824008400143742553677794724150690
41497007, 69697771112044787120013517402337391494610824289677071890732527862932076943559831097602420620935343748041708234
8464232355290320034610310167, 174244427780111967800033793505843478736527060724192679726831278280484037354408858286955798
20867639201766927396664086036093137660716695064127, 43561106945027991950008448376460869684131765181048169931707817087510
2400383327714043159343515493799632712186944317032265593719477026000462887]

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

In [48]:
ispis([(7*5**(2*n)+12*6**n)%19 for n in range(1,101)],80)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

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

In [49]:
ispis([(7*5**(2*n)+12*6**n)%19 for n in range(1,1001)],80) 

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

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 Python i SymPy, Eulerovu tvrdnju je lako opovrgnuti, tj. dokazati da ona nije istinita.

Prvih $39$ takvih brojeva

In [50]:
ispis([n**2+n+41 for n in range(1,40)],80)

[43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 3
83, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163
, 1231, 1301, 1373, 1447, 1523, 1601]

jesu zaista prosti

In [51]:
ispis([sp.isprime(n**2+n+41) for n in range(1,40)],80)

[True, True, True, True, True, True, True, True, True, True, True, True, True, T
rue, True, True, True, True, True, True, True, True, True, True, True, True, Tru
e, True, True, True, True, True, True, True, True, True, True, True, True]

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

In [52]:
[sp.isprime(n**2+n+41) for n in [40,41]]
Out[52]:
[False, False]

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 [53]:
lista1000=[sp.isprime(n**2+n+41) for n in range(1,1001)] 
ispis(lista1000,80)

[True, True, True, True, True, True, True, True, True, True, True, True, True, T
rue, True, True, True, True, True, True, True, True, True, True, True, True, Tru
e, 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, Tru
e, True, True, False, True, True, True, True, True, True, True, True, False, Tru
e, 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, Fa
lse, 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, Tr
ue, True, False, True, False, False, True, True, True, True, False, True, True, 
True, True, True, False, False, False, False, True, True, False, True, True, Tru
e, True, True, True, True, True, True, True, False, True, True, False, False, Tr
ue, False, False, False, True, True, True, False, True, False, False, False, Fal
se, 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, Fal
se, True, False, False, True, True, True, True, True, True, False, False, True, 
True, True, False, False, True, False, False, True, False, True, False, True, Tr
ue, True, False, False, True, False, False, False, False, False, True, True, Tru
e, True, True, True, False, True, True, False, True, False, True, True, True, Tr
ue, True, True, False, True, True, True, False, False, False, False, False, Fals
e, 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, F
alse, False, False, True, True, False, False, True, True, True, False, True, Fal
se, False, True, False, True, False, True, True, False, False, True, True, True,
 True, True, False, True, True, True, False, True, False, False, True, True, Tru
e, 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, Fals
e, True, True, True, False, False, False, False, True, True, False, True, True, 
False, False, True, False, True, True, True, False, True, False, True, False, Fa
lse, True, False, True, False, True, True, True, False, True, False, True, False
, True, False, False, True, True, True, True, True, True, False, True, False, Fa
lse, True, False, True, True, True, True, False, True, False, False, True, True,
 False, False, False, False, True, True, True, True, True, True, True, True, Tru
e, True, False, False, False, False, True, True, True, True, True, False, True, 
True, False, False, True, True, False, False, False, False, True, True, False, T
rue, True, False, False, False, True, False, False, True, True, False, False, Fa
lse, True, True, False, False, True, False, False, False, True, False, True, Tru
e, True, False, True, True, True, True, True, True, False, True, True, False, Tr
ue, False, True, True, False, False, True, False, False, False, False, False, Fa
lse, True, True, True, False, True, False, True, False, True, True, True, False,
 True, False, True, False, False, True, True, False, True, True, False, True, Tr
ue, False, False, False, False, False, True, True, True, True, True, False, True
, True, False, False, False, True, True, False, False, False, False, False, Fals
e, False, True, True, False, False, False, True, True, True, False, False, True,
 True, False, False, True, False, True, True, False, False, True, True, False, T
rue, True, False, False, True, True, False, False, True, False, True, False, Fal
se, 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, Fal
se, False, True, False, False, False, True, True, False, False, True, False, Fal
se, True, False, False, True, True, False, False, False, True, False, True, Fals
e, True, False, False, True, True, True, False, False, False, False, False, Fals
e, False, True, False, True, True, True, False, True, True, True, True, True, Tr
ue, False, False, False, True, False, False, False, True, False, False, False, F
alse, 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, T
rue, True, True, False, False, False, True, True, False, False, False, False, Tr
ue, True, False, False, True, False, False, False, False, True, True, False, Tru
e, False, True, True, False, False, False, False, False, True, True, False, True
, False, False, False, True, False, True, True, True, True, True, True, True, Tr
ue, 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, Tru
e, 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 Python to prebroji.

In [54]:
lista1000.count(False)
Out[54]:
$$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 Python, ne bi napravio takvu pogrešku. No, lako je sada biti pametan. :-)

In [ ]: