Mathematica-dolgozat

Feladat

Lássuk be, hogy tetszőleges egész számot elő lehet állítani az első néhány négyzetszám valamilyen előjeles összegeként.  (Pl.: 0=0 , 1=1 , 2=-1-4-9+16 , 3=-1+4 , ...)
Milyen más sorozatokra teljesül még az állítás?

Négyzetszámok

Írjunk függvényt, mely elkészíti az első n db négyzetszámból előállítható egész számokat. Ehhez szükségünk lesz egy kétváltozós segédfüggvényre, melynek első változója legyen egy lista, második pedig egy tetszőleges szám, és a függvény készítsen el egy listát a bemenő lista elemeinek a szám négyzetével vett összegeiből illetve különbségeiből.

{#1 - #2^2, #1 + #2^2} &[{1, 2, 3}, 2]

A Fold paranccsal a {0} listából kiindulva az első n számon végigfuttatva a függvényt éppen az első n db négyzetszámból képezhető számokat kapjuk.

Fold[Union[#1 - #2^2, #1 + #2^2] &, {0}, Range[2]]

A FoldList utasítással megkaphatjuk az első n vagy annál kevesebb négyzetszámból előálló számokat.

FoldList[Union[#1 - #2^2, #1 + #2^2] &, {0}, Range[2]]

Elegendő a pozitív számokat tekintenünk, ugyanis ha egy  "a" szám előáll a feltételnek megfelelően, akkor az összegben az előjelek ellentétesre változtatásával a szám ellentettjét kapjuk meg, tehát  "a" és "-a" egyszerre állhatnak elő. 
 Így a függvényt kompakt alakra hozva megkapjuk az első n db négyzetszám segítségével képezhető pozitív számokat.

f[n_] := 
      Select[Union[
          Flatten[FoldList[Union[#1 - #2^2, #1 + #2^2] &, {0}, Range[n]]]], 
        Positive]

f[3]

f[10]

Length[Intersection[f[10], Range[100]]]

Az első tíz négyzetszámból képezhető listában a  számok sűrűn helyezkednek el, a lista két szám kivételével tartalmazza az első száz pozitív egészt.

A sorozat első n eleméből generált számok száma (2^n) (egy elemet + vagy -  előjellel vehetünk), egy szám azonban többféleképpen is előállhat ( pl.: 5=1+4=1+4+9+16-25 ), azaz a generált számok nem különbözőek. Ahogyan a példa is mutatja jóval kevesebb szám áll ténylegesen elő.

{Length[f[33]], 2^33}

Írjunk függvényt,amely megadja azt a számot, ahány elemére a sorozatnak  szükség van 1-től  n-ig a pozitív számok maradéktalanul való előállításához.

g[n_] := 
      Module[{i}, 
        For[i = 1, 
          Length[Intersection[f[i], Range[n]]] ≠  n, i++]; 
        i]

Map[g, {100, 500, 1000, 10000}]

ListPlot[Map[g, Range[100]], PlotJoined -> True]

f[33][[10000]]

Láthatjuk, hogy a sorozatnak kevés eleme is igen sok számot előállít, 33 elem már 10000-ig generálja az egész számokat.

SEJTÉS:  A kísérletek alapján sejthető, hogy minden egész számot előállít az első néhány négyzetszám előjeles összege.

SEJTÉS IGAZOLÁSA:  Az igazoláshoz vizsgáljuk meg a négyzetszámok különbségsorozatát. A szomszédos négyzetszámok különbségei a páratlan számok sorozatát adják. Négy egymás utáni négyzetszámot tekintve az első kettő különbsége egy 2k+1 alakú szám, a második kettőé   2k+5 , a különbségek különbsége pedig 4 lesz.
      Pl.: (16-9)-(4-1)=7-3=4

Expand[((n + 4)^2 - (n + 3)^2) - ((n + 2)^2 - (n + 
                  1)^2)]

((n+4)^2-(n+3)^2)-((n+2)^2-(n+1)^2)  =  (n+1)^2-(n+2)^2-(n+3)^2+(n+4)^2

Négy egymás utáni elemből megfelelő előjelezéssel kikeverhető a 4 konstans. Mivel minden egész felírható 4k+r alakban, ahol r  a  0, 1, 2 , 3  értékeket veheti fel, amelyeknek felírása már ismert, ezért bármely egész szám felírható az első néhány négyzetszám valamilyen előjeles összegeként.
                        Pl.:      7 = 3 + 
            4 = (-1 + 4) + (9 - 16 - 25 + 36)
\(\(\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \)\(8 = \(4 + 4 = \((1 - 4 - 9 + 16)\) + \((25 - 36 - 49 + 64)\)\)\)\)\)

 A négyzetszámokra beláttuk az állítást, vizsgáljuk meg következőként a köbszámok sorozatát.

Köbszámok

Írjunk hasonló függvényt, mely elkészíti az első n db köbszámból előállítható pozitív számokat.

k[n_] := 
      Select[Union[
          Flatten[FoldList[Union[#1 - #2^3, #1 + #2^3] &, {0}, Range[n]]]], 
        Positive]

k[6]

Konstans kikeverése, maradékok vizsgálata

Az egymást követő nyolc köbszámot hasonló módszerrel előjelezve a 48 konstans keverhető ki.

Expand[(((n + 8)^3  -  (n + 
                      7)^3)  -  ((n + 6)^3   -  (n + 
                      5)^3 )) -  (((n + 4)^3  -  (n + 
                      3)^3)  -   ((n + 2)^3   -  (n + 
                      1)^3))]

Egy ciklussal ellenőrizhetjük, hogy az első 47 szám előállítható-e, és ehhez hány elemre van szükség.

For[i = 1, 
      Length[Intersection[k[i], Range[47]]] ≠ 
        47, i++]

i

k[16][[47]]

Bármely egész szám felírható  48k+r  (r=0,1,... ,47) alakban, ahol r  biztosan előáll az első legfeljebb 16 köbszámból, a 48k pedig az azt követő 8k db számból, melyet nyolcasával úgy előjelezünk, hogy 48-at adjon ki.

Az (n^k) sorozat vizsgálata (általánosítás)

Konstans meghatározása

A konstans kikeveréséhez írjunk egy különbségfüggvényt, mely a beadott lista elemeit párba állítja, és veszi a páros sorszámú elemek különbségét az azt megelőző páratlan sorszámú elemmel.

ff[n_] := 
      Table[n[[2 i]] - n[[2  i - 1]], {i, 1, 
          Length[n]/2}]

ff[{a, b, c, d, e, f, g, h}]

A NestList utasítással a függvény többszöri alkalmazásakor nyomonkövethetjük a sorozat elemein vett különbségszámítást.

NestList[ff, {a, b, c, d, e, f, g, h}, 3]

Nézzük meg a különbséglistákat a négyzet-és köbszámok esetében.

NestList[Expand[ff[#]] &, Table[(n + i)^2, {i, 1, 4}], 
      2]

NestList[Expand[ff[#]] &, Table[(n + i)^3, {i, 1, 8}], 
      3]

A különbségfüggvény segítségével az  (n^k) esetre is meghatározhatjuk a szomszédos elemekből kikeverhető konstansokat.

NestList[Expand[ff[#]] &, Table[(n + i)^4, {i, 1, 16}], 
      4]

Az (n^k)sorozatnak sejtésünk szerint (2^k) szomszédos elemére van szükség az  (n^k), (n^(k - 1)), ... , n  hatványok kiejtéséhez, azaz a konstans előállításához. Ezt majd az együtthatók vizsgálatánál fogjuk pontosan látni.

konst[x_] := 
      Nest[Expand[ff[#]] &, Table[(n + i)^x, {i, 1, 2^x}], x]

Nézzük meg a konstansok listáját az  (n^10) polinomig.

Map[konst, Range[10]]

A polinomok együtthatói

Vizsgáljuk meg, hogyan változik a négyzet-és köbszámoknál a különbségfüggvény alkalmazásakor az  (n^2)-es  illetve az n-es tag együtthatója.

l2 = 
      NestList[Expand[ff[#]] &, Expand[Table[(n + i)^2, {i, 1, 4}]], 
        2]

Coefficient[l2, n^2]

Coefficient[l2, n]

Az n-es tag  együtthatói négy egymást követő négyzetszámnál számtani sorozatot alkotnak, azaz differenciájuk állandó, így kiejthetők.

l3 = 
      NestList[Expand[ff[#]] &, Expand[Table[(n + i)^3, {i, 1, 8}]], 
        3]

Coefficient[l3, n^3]

Coefficient[l3, n^2]

Coefficient[l3, n]

%/3

l4 = 
        NestList[Expand[ff[#]] &, Expand[Table[(n + i)^4, {i, 1, 16}]], 
          4];

Coefficient[l4[[1]], n]/4

(n^3) együtthatója 1, ezért az elempárok különbségeiben kiesik.
(n^2)együtthatói számtani sorozatot alkotnak, így az elempárok különbségeiben az együttható a differencia lesz, a következő lépésben pedig az (n^2)-ek is kiesnek. Az n-es tagokat hárommal  (3 alatt a 2) leosztva az első nyolc négyzetszámhoz jutunk, melyekből négyesével kikeverhető a 4 konstans, s a két négyes különbségét véve kiejthető n.

Általánosan megfogalmazva   (n^k) sorozat esetén sorban ki kell ejtenünk az  (n^k), (n^(k - 1)), (n^(k - 2)), ...,  n-es tagokat. Az elemszám minden lépésben feleződik, ezért (2^k) elemre van szükségünk. 
Az  (((n + c))^k)=(∑_(i = 0)^k)(({{k}, {i}}))  (n^(i ))(c^(k - i))  összefüggésből látható, hogy (n^(k - 3))-os tagok együtthatója: (({{k}, {3}})) (c^3) , azaz  (({{k}, {3}})) (1^3), (({{k}, {3}})) (2^3), ... , (({{k}, {3}})) ((((2^k)))^3). Ezen tagok száma legalább 16 (vagy 16 2-hatványszorosa), amit kétszer 8-as csoportra osztva kiejthető lesz a változó.   (n^2)-re,   (n^3)-re,   (n^4)-re  már látjuk, hogy működik az eljárás, (n^5)-nél pedig az együtthatók listája rendre az (n^0), n , (n^2), (n^3), (n^4) sorozat első (2^5) eleme lesz, azaz visszavezethető a korábbi esetekre. Ezt tetszőleges (n^k)-ra (k pozitív egész) megtehetjük, beláthatjuk tehát, hogy a konstans kikeverhető az (n^k) alakú sorozatokból.

Összegzés

Be lehet látni, hogy bármely egész szám előáll az (n^k) sorozat első m elemének vagy azok ellentettjeinek összegeként, ahol k, m pozitív egészek.
További polinomokat vizsgálva megállapíthatjuk, hogy a  c (n^k) sorozatra ez nem teljesül, hiszen az előállított számok között csak c konstanssal oszthatók szerepelnek, az (n^k) + c sorozatra viszont teljesül az állítás, hiszen ugyanaz a konstans keverhető ki elemeiből, mint az (n^k)-nál.