Temat: Własności liczb.                                                  wl-liczb.doc – 71 kB

 

Celem lekcji jest zapoznanie ze sposobem sprawdzania, czy dana liczba jest pierwsza, sposobem wyznaczania liczb pierwszych w danym przedziale, sposobem wyznaczania nwd i nww oraz z zwłasnością liczby 153.

 

Przebieg lekcji:

 

1.Omówienie sposobu sprawdzania, czy dana liczba całkowita jest pierwsza.

program Liczba_pierwsza;          {Turbo Pascal}

uses crt; 

var liczba,n:longint;

begin

     clrScr;

     liczba:=1997;

     for n:=2 to round(sqrt(liczba)) do

        if liczba mod n=0 then exit;

     writeLn(liczba,'-liczba pierwsza');

     readLn;

end.

program Liczba_pierwsza;          {Think Pascal}

var

     liczba, n: longint;

begin

     liczba := 1997;

     for n := 2 to round(sqrt(liczba)) do

        if liczba mod n = 0 then

           halt;

     writeLn(liczba, '-liczba pierwsza');

end.

 

2.Wyznaczenie wszystkich liczb pierwszych w danym przedziale - sito Eratostenesa.

{Turbo Pascal}

program Liczby_pierwsze;

uses crt;

const max=500;

var liczba,n:longInt;

    t:array[2..max] of longInt;

begin

   clrScr;

   for liczba:=2 to round(sqrt(max)) do

      if t[liczba]=0 then

        for n:=2 to max div liczba do t[liczba*n]:=1;

   for n:=2 to max do if t[n]=0 then write(n:5);

   readLn;

end.

{Think Pascal}

program Liczby_pierwsze;

const max=500;

var liczba,n:longInt;

    t:array[2..max] of longInt;

begin

   for liczba:=2 to round(sqrt(max)) do

     if t[liczba]=0 then

      for n:=2 to max div liczba do t[liczba*n]:=1;

   for n:=2 to max do if t[n]=0 then

     if n mod 100=0 then writeLn

     else write(n:5);

end.

 

 

Liczby pierwsze z przedziału (1, 500):

 

                2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,

211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,

307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,

401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499

 

3. Gra w sito Eratostenesa.

 

4. Omówienie zastosowań liczb pierwszych do szyfrowanie.

 

5. Omówienie sposobu znajdowania największego wspólnego dzielnika liczb a i b - algorytm Euklidesa.

Należy przedstawić liczbę a jako kombinację liniową liczby b: a=k*b+r, gdzie r<b. Jeżli r=0 to nwd(a,b)=b, jeżeli r¹0 to podstawiamy za a liczbę b, za b liczbę r i powtarzamy całą operację ponownie dopóki r nie będzie równe 0.

 

6.Ułożenie programu na algorytm Euklidesa.

Program Nwd;                      {Turbo Pascal}

uses crt;

var a,b,r:integer;

begin

  clrScr;

  a:=1995;

  b:=1957;

  repeat

    writeLn(a,' = ',a div b,'*',b,' + ',a mod b);

    r:=a mod b;

    a:=b;

    b:=r;

  until r=0;

  writeLn('Nwd = ',a);

  readLn;

end.

program Nwd;                      {Think Pascal}

   var

      a, b, r: integer;

begin

   a := 1995;

   b := 1957;

   repeat

    writeLn(a,' =',a div b:2,'*',b:2,'+',a mod b:2);

    r := a mod b;

    a := b;

    b := r;

   until r = 0;

   writeLn('Nwd = ', a : 2);

end.

 

7. Omówienie sposobu znajdowania najmniejszej wspólnej wielokrotności liczb a i b.

 

I sposób: bierzemy kolejne wielokrotności liczby a: 1a, 2a, 3a, i.t.d., aż do momentu, gdy któraś z nich podzieli się przez b. Wtedy ta wielokrotność jest to najmniejszą wspólną wielokrotnością liczb a i b.

II sposób: rozkładamy obie liczby a i b na czynniki pierwsze i za najmniejszą wspólną wielokrotność uznajemy iloczyn czynników, z tym, że jeśli jakiś czynnik występuje w obu rozkładach to do iloczynu bierzemy go tylko raz.

III sposób: obliczamy iloczyn liczb a i b i dzielimy go przez ich największy wspólny dzielnik tych liczb.

 

8. Ułożenie programów komputerowych do wyznaczania najmniejszej wspolnej wielokrotności.

program Najmniejsza_wspolna_wielokrotnosc;

uses crt;

var a,b,dz:longInt;

begin

  clrScr;

  a:=30;

  b:=105;

  dz:=1;

  while dz*a mod b<>0 do dz:=dz+1;

  writeLn('N. w. w.(',a,',',b,') = ',dz*a);

  readLn;

end.

program Najmniejsza_wspolna_wielokrotnosc;

var a, b, dz: longInt;

begin

     a := 30;

     b := 105;

     dz := 1;

     while dz * a mod b <> 0 do  dz := dz + 1;

     writeLn('N. w. w.(',a:1,',',b:1,')=',dz*a:1);

end.

 

 

9. Omówienie własności kolejnych sum cyfr dowolnej liczby naturalnej:

a)      sumy cyfr, np. 12345 -> 15 ->6-> 6-> ...

3 -> 3 -> 3 -> ...

b)      sumy kwadratów cyfr, np. 12345 ->55 ->50 ->25 ->29 ->85->89->145->42 ->20->4 ->16 ->37 ->58->89->...

3 -> 9 -> 81 -> 65 -> 61 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> ...

c)      sumy sześcianów cyfr (własność liczby 153), np. 12345 ->225 ->141-> 66 ->432-> 99 ->1458 ->702-> 351 ->153 ->153->...

3 -> 27 -> 351 -> 153 -> 153 -> 153 -> ...

program Suma_szescianow_cyfr    {Turbo Pascal}

uses crt;

var liczba,cyfra,suma,i:longInt;

    key:char;

begin

  clrScr;

  liczba:=123;

  write(liczba,' ');

  repeat

    suma:=0;

    repeat

        cyfra:=liczba mod 10;

        suma:=suma+cyfra*cyfra*cyfra;

        liczba:=liczba div 10;

    until liczba=0;

    write(suma,' ');

    liczba:=suma;

    key:=readKey;

  until (key=#27);

end.

program Suma_szescianow_cyfr     ;{Think Pascal}

   var

      liczba, cyfra, suma, i: longInt;

      key: char;

begin

   liczba := 123;

   writeLn(liczba);

   repeat

      suma := 0;

      repeat

         cyfra := liczba mod 10;

         suma := suma + cyfra * cyfra * cyfra;

         liczba := liczba div 10;

      until liczba = 0;

      write(suma, ' ');

      liczba := suma;

      read(key);

   until key = '^';

end.

 

We wszystkich przypadkach kolejne iteracje sum cyfr, lub sum kwadratów cyfr lub suma sześcianów cyfr tworzą cykle.Szczególnie ciekawy jest przypadek c) dla liczb podzielnych przez 3. Otrzymujemy zawsze liczbę 153.

Dowód tej własności polega na pokazaniu, że suma sześcianów cyfr liczby większej niż 9999 jest od niej mniejsza a dla pozostałych można sprawdzić badaną własność na komputerze.

 

10. Omówienie własności ciągu liczb Collatza.

 

Liczby te powstają według następującego przepisu:

Bierzemy dowolną liczbę naturalną. Jeśli jest ona parzysta to dzielimy ją przez 2, w przeciwnym przypadku mnożymy ją przez 3 i dodajemy 1. Z otrzymaną liczbą postępujemy w ten sam sposób. Collatz wysunął hipotezę, że w skończonej ilości takich iteracji zawsze otrzymamy liczbę 1.  Hipoteza ta nie została to tej pory udowodniona.

 

Przykłady:

5®16®8®4®2®1,

3®10®5®16®8®4®2®1,

12®6®3®10®5®16®8®4®2®1,

23®70®35®106®53®160®80®40®20®10®5®16®8®4®2®1,

 

 

11. Zastosowanie programu komputerowego do otrzymywania liczb ciągu Collatza.

Program Ciag_Collatza;

uses crt;

var n:longInt;

begin

  clrscr;

  n:=23;

  repeat

    write(n,'  ');

    if n mod 2=0 then n:=n div 2

    else

    n:=3*n+1;

  until n=1;

  writeln('1');

  readln;

end.

 

11. Omówienie rozkładu liczb parzystych, podzielnych przez 3, podzielnych przez 4, itd. w trójkącie Pascala. Rozkład ten ma związek z trójkątem Sierpińskiego i z liczbami Newtona.

program trojkat_Pascala;

uses graph;

var karta,tryb,n,k:integer;

    x,y:longInt;ilS:string;t:array[1..33] of longInt;

begin

  karta:=detect; initGraph(karta, tryb, '');

  setTextStyle(2,0,1);

  for n:=1 to 33 do t[n]:=0;

  y:=1;

  for n:=1 to 33 do

      for k:=1 to n-1 do

          begin

            x:=y;

            y:=t[k];

            t[k]:=x+y;

            setColor(t[k] mod 2+3);

            str(t[k],ilS);

            setUserCharSize(1,length(ilS) div 2,5,4);

           outTextXY(320-10*n+k*20,12*n,ilS);

         end;

  readLn; closeGraph;

end.