Test Lucasa-Lehmera jest testem pierwszości dla liczb Mersenne'a. Został on stworzony przez Edwarda Lucasa w 1856, a następnie ulepszony przez niego w 1878. Test działa następująco. Liczba 2^p - 1 jest liczbą pierwszą gdy jest ona dzielnikiem wyrazu L_p-1 określonego w poniższy sposób.

• L₁ = 4

• L_n= L_n-1² - 2

Powyższy test jest wykorzystywany przez serwis GIMPS do znajdowania dużych liczb pierwszych Mersenne’a. Zaletą test jest bardzo szybkie działanie. Natomiast główną wadą jest fakt, że używać można go tylko dla liczb Mersenne’a.

Zróbmy przykład :

• Ćzy liczba 7 jest liczbą pierwszą?

• 7 = 2³-1 . Więc p = 3

• Więc musimy sprawdzić czy liczba 7 jest dzielnikiem L₂ . Więc n = 2

• L₁ = 4
  L₂ = L₁² - 2
  L₂ = 4² - 2
  L₂ = 16 - 2
  L₂ = 14

• Liczba 7 jest dzielnikiem liczby 14 zatem 7 to liczba pierwsza.

Dzisiaj utworzyłem nowe logo w moim serwisie o liczbach pierwszych


Przepraszam za ta długą przerwę. Od teraz postaram się regualarnie uaktualniać serwis.

• W XVII wieku francuski mnich Marin Mersenne rozpatrzył możliwość istnienia liczb pierwszych w postaci 2ⁿ-1, gdzie n jest liczbą naturalną.

• Uczony stwierdził, że liczba 2ⁿ-1 jest liczbą pierwszą dla wartości n = 2,3,5,7,13,17,19,31,67,127,257 i nie jest nią dla żadnej innej wartości n mniejszej od 257.

• Dziś wiemy, że francuz pominął n = 61,89,107 i błędnie określił jako liczby pierwsze liczby dla n = 67,257. Jednak trzeba przyznać, że liczby te zostały wyznaczone bez użycia komputerów.

• Aktualnie poszukiwaniem liczb pierwszych Mersenne'a zajmuje się organizacja GIMPS (Great Internet Mersenne Prime Search). Poszykiwanie tych liczb wykonywane jest w sposób rozrposzony. dzięki czemu każdy użytkownik może udostępnić moc obliczeniową swojego komputera, aby pomóc przy poszukiwaniu tych liczb.

• Dzisiaj nie wiadomo czy liczb pierwszych Mersenne'a jest nieskończenie wiele. Na dziś znamy 51 tych liczb. Ale okazuje się, że dzisiaj ośmioma największymi znanymi liczbami pierwszymi są właśnie Liczby Mersenne’a.

Witam serdecznie. Zmieniłem trochę moją konfigurację sprzętową dodając mikrofon. W związku z tym chciałbym Was poinformować, że zamierzam od stycznia dodawać do mojego serwisu podcasty o liczbach pierwszych. Napiszcie proszę w komentarzu co o tym myślicie? Dziękuję.

Dzisiaj chciałbym opisać cechy podzielności liczb naturalnych przez 2,3,4,5,6,7,8,9 i 10.

• Liczba naturalna dzieli się przez 2 gdy jej ostatnią cyfrą jest 0, 2, 4, 6 albo 8

• Liczba naturalna dzieli się przez 3 gdy suma jej cyfr dzieli się przez 3

• Liczba naturalna dzieli się przez 4 gdy liczba wyrażona dwiema ostatnimi jej cyframi, dzieli się przez 4

• Liczba naturalna dzieli się przez 5 gdy jej ostatnią cyfrą jest 0 albo 5

• Liczba naturalna dzieli się przez 6 gdy dzieli się przez 2 i przez 3

• Liczba naturalna dzieli się przez 7 gdy różnica między liczbą wyrażoną kolejnymi trzema ostatnimi cyframi danej liczby a liczbą wyrażoną pozostałymi cyframi tej liczby dzieli się przez 7

• Liczba naturalna dzieli się przez 8 gdy liczba wyrażona trzema ostatnimi jej cyframi dzieli się przez 8

• Liczba naturalna dzieli się przez 9 gdy suma jej cyfr dzieli się przez 9

• Liczba naturalna dzieli się przez 10 gdy ostatnią jej cyfrą jest 0

Wpis powstał przy pomocy serwisu matematycznego https://math.edu.pl.

Dzisiaj chciałbym wprowadzić pojęcie rekurencji, ponieważ będę ją również wykorzystywał w kolejnych wpisach. Skupmy się na algorytmie wyznaczania największego wspólnego dzielnika - NWD Jakiś czas temu podawałem klasyczny algorytm wyznaczania NWD napisany w języku PHP:

function nwd($a,$b)
{
while($a*$b!=0)
{
if ($a>$b)
{
$a=$a%$b;
}
else
{
$b=$b%$a;
}
}
$wynik=$a+$b;
return($wynik);
}

Teraz pzedstawię wersję rekurencyjną. Rekurencja do zdolność programu komputerowego do wywoływania samego siebie. Oto algorytm - napisany w pseudopascalu.

if (a*b=0) then NWD(a,b):=a+b
else if (a>=b) then NWD(a,b)=NWD(a mod b,b)
else NWD(a,b)=NWD(a,b mod a)
              

Zauważmy, że funkcja NWD wywołuje samą siebe.

Test pierwszości Fermata jest probabilistycznym algorytmem sprawdzającym czy dana liczba jest liczbą pierwszą. Z nazwy widać, że opiera się ona na twierdzeniu Fermata.

Oto algorytm ( czy n jest liczbą pierwszą? ) :

• Wylosuj liczbę mniejszą od n i oblicz NWD(a,n)

• Jeżeli NWD(a,n)=d>1 to, d jest dzielnikiem liczby n i n jest liczbą złożoną.

• Jeżeli NWD(a,n)=1 to oblicz a^n-1 mod n

  • jeżeli wartość powyższego wyrażenia jest większe od 1 to n jest liczbą złożoną.

  • jeżeli wartość w=powyższego wyrażenia równa się 1 to n jest liczbą pierwszą.

Jeżeli wartość wyrażenia a^n-1 mod n jest większa od 1 to mamy pewność, że n jest liczbą złożoną. Wynika to z twierdzenia Fermata. Natomiast jeżeli wartość tego wyrażenia równa się 1 to możemy popełnić błąd. Liczba n może być złożona mimo, że wyrażenie a^n-1 mod n wynosi 1.

Dzisiaj trochę Wam opowiem o relacjach kongruencji. Jest to ważny temat, ponieważ będę go stosował w dalszych wpisach na blogu.

• Niech m będzie dowolną liczbą naturalną więszą od zera. Mówimy, że dwie liczby całkowite a i b są równoważne ( lub przystają modulo m ) jeżeli : m | (a-b)

• Jeżeli liczby a i b są dodatnie to a ≡ b (mod m) wtedy i tylko wtedy gdy a ib mają takie same reszty z dzielenia przez m

• Relacja przystawania modulo m jest relacją równoważności czyli spełnia warunki : zwrotność, symetrię i przechodniość.

  • zwrotność : dla każdeg a zachodzi a ≡ a (mod m)

  • symetria : dla każdego a,b jeżeli a ≡ b (mod m), to b ≡ a (mod m)

  • przechodniość : dla każdego a,b,c jeżeli a ≡ b (mod m) i b ≡ c (mod m), to a ≡ c (mod m)

Dzisiaj przygotowałem statystykę odwiedzin mojego serwisu o liczbach pierwszych za rok 2021.



Wykres został stworzony za pomocą aplikacji calc pochodzącej z pakietu Libre Office.

Dzisiaj przygotowałem listę serwisów, które w ciekawy sposób prezentują wiedzę na temat liczb pierwszych.

Liczby pierwsze w internecie:

• Wikipedia
  zobacz

• Serwis "Matemaks".
  zobacz

• Serwis "Math.edu.pl"
  zobacz

• Serwis "Matematyka Szkolna"
  zobacz

• Serwis "Młody Technik"
  zobacz

• Serwis "Matematyka innego wymiaru"
  zobacz

• Ciekawy serwis o liczbach pierwszych
  zobacz

Dzisiaj trochę inny post. Polecam przesłuchanie muzyki elektronicznej o pięknie liczb wykonanej przez zespół muzyczny Klangwelt. Nazwa płyty to - The age of numbers.



Lista utworów:

• Zero

• Enigma

• Self Similar

• Meander

• Wheel of Fortune

• Topologique

• Lucky Numbers

• Long Distance

• Infinity +1

• The Beauty Of Numbers

Tutaj możecie kupić tę płytę

Dzisiaj chciałbym zaprezentować algortym, który wypisuje n kolejnych liczb pierwszych.

function pt($liczba)
{
	$wynik=0;
	$g=floor($liczba/2);
	$i=2;
	if ($liczba<2) return(0);
	else
	  {
	  while(($wynik==0) & ($i<=$g))
	  {
	  if ($liczba%$i==0) ++$wynik;
	  ++$i;
	  }
	}
	if ($wynik==0) return(1);
	else return(0);    
}

function gen($l)
{
$ile=0;
$i=0;
while ($ile<$l)
{
	if (pt($i)==1)
	{		
		print("$i");
		++$ile;
	}
	++$i;
}
}

Funkcja pt jest funkcją sprawdzającą czy dana liczba jest liczbą pierwszą. Jeżeli funkcja zwróci wartość 1 to dana liczba jest liczbą pierwszą.Natomiast funkcja gen wypisuje l kolejnych liczb pierwszych.

Chciałbym wprowadzić pojęcie gęstości liczb pierwszych. Niech A_n oznacza ilość liczb pierwszych wśród liczb naturalnych 1,2,3,...,n. Zatem :

• A₁ = 0

• A_{2 = 1}

• A_{3 = 2}

• A_{4 = 2}

• A_{5 = 3}

• ...

Gęstość liczb pierwszych wśród n pierwszych liczb całkowitych jest dana przez stosunek : An / n. Oto algorytm wyznaczania gęstości liczb pierwszych zakodowany w języku PHP

         
function pt($liczba)
  {
  $wynik=0;
  $g=floor($liczba/2);
  $i=2;
  if ($liczba<2) return(0);
else
  { 
  while(($wynik==0) & ($i<=$g))
    {
    if ($liczba%$i==0) ++$wynik;
    ++$i;
    } 
  }
  if ($wynik==0) return(1);
  else return(0);                 
  }
              

    
function glp($zakres)
  {
  $prc=0;
  $wynik=0; 
  for ($i=2;$i<=$zakres;++$i)
    { 
    if (pt($i)==1) ++$prc;
    }
  else {}
  }
  $wynik=($prc/($zakres-1))*100;
  print("W danym przedziale występuje $wynik % liczb pierwszych.");
  }
             

Pierwsza funkcja pt sprawdza czy dana liczb jest liczbą pierwszą. Jest to funkcja pomocnicza. Funkcja zwraca wartość 1 jeżeli dana liczba jest liczbą pierwszą. Natomiast druga funkcja glp oblicza gęstość liczb pierwszych w danym przedziale [2 ,.. , $zakres] .

Bardzo ciekawą grupą w teorii liczb są liczby Fermata. Są to liczby w postaci:

F(n) = 2²ⁿ + 1

Fermat zauważył, że liczby Fermata F₀, F₁, F₂, F₃, F₄ są liczbami pierwszymi.

• F₀ = 3

• F₁ = 5

• F₂ = 17

• F₃ = 257

• F₄ = 65537

Fermat był przekonany, że wszystkie liczby Fermata są pierwsze. Nie mógł sprawdzić wartości liczby F₅, ponieważ zawiera ona 10 cyfr. Musiałby mieć tablicę wszystkich liczb pierwszych z przedziału od 2 do 100000. A takiej nie posiadał. Dopiero Euler odkrył, że liczba F₅ jest złożona, ponieważ jest podzielna przez liczbę 641.

• F₅ = 641 x 6700417

Dzisiaj opowiem trochę o bardo starym twierdzeniu, które było znane Chińczykom już w starożytności.

Chińskie twierdzenie o resztach
Jeżeli liczby całkowite dodatnie n₁, n₂,...,n_k są parami względnie pierwsze, zaś liczby a₁, a₂,...,a_k są dowolnymi liczbami całkowitymi, to istnieje taka liczba a, że:

• a ≡ a₁ ( mod n₁ )

• a ≡ a₂ ( mod n₂ )

.........................

• a ≡ a_k ( mod n_k )

Chińskie twierdzenie o resztach ma wiele zastosowań. W rzeczywistości chińscy generałowie stosowali je do sprawdzania liczby swoich żołnierzy. Wydawali kolejno rozkazy:

• w dwuszeregu zbiórka

• w 3-szeregu zbiórka

• w 5-szeregu zbiórka

• w 7-szeregu zbiórka

• w 11-szeregu zbióka

i kontynuowali w ten sposób, obliczając za każdym razem tylko resztę (tzn. liczbę żołnierzy w ostatniej niepełnej kolumnie). Zatem mamy do rozwiązania poniższy układ równań :

• a ≡ a₁ ( mod 2 )

• a ≡ a₂ ( mod 3 )

• a ≡ a₃ ( mod 5 )

• a ≡ a₄ ( mod 7 )

• a ≡ a₅ ( mod 11 )

gdzie a₁, a₂, a₃, a₄, a₅ to liczba żołnierzy w ostatnich niepełnych kolumnach. Rozwiązaniem tego zadania jest liczba a, która wyznacza ilość żołnierzy w armii.

Dzisiaj opowiem trochę o liczbach pseudopierwszych.

• Liczby pseudopierwsze to takie liczby naturalne, które spełniają niektóre własności charakteryzujące liczby pierwsze – jednak same nie są liczbami pierwszymi.

• Najbardziej znaną kategorią liczb pseudopierwszych są liczby pseudopierwsze Fermata, To takie liczby, które spełniają warunki małego twierdzenia Fermata.

Twierdzenie Fermata
Jeżeli p jest liczbą pierwszą to dla dowolnej liczby całkowitej a liczba ap-a jest podzielna przez p.

• Zatem liczba p spełnia warunek Fermata jeżeli a^p-1 -1 jest podzielne przez p dla pewnego a. Jeżeli p nie jest liczbą pierwszą to nazywamy ją liczbą pseudopierwszą przy podstawie a.

Dzisiaj opowiem trochę o liczbach pierwszych bliźniaczych.

• Liczbami pierwszymi bliźniaczymi nazywamy dwie liczby pierwsze, których różnica wynosi 2. Zatem przykładowe liczby pierwsze bliźniacze to (3,5), (5,7), (11,13) itp.

• Do dziś nie wiadomo, czy liczb pierwszych bliźniaczych jest skończenie czy nieskończenie wiele. Wiadomo, że są one rozmieszczone bardzo rzadko.

• Największą obecnie znaną parą liczb pierwszych bliźniaczych jest para liczb 260 497 545*2^{6 625}-1, 260 497 545*2^{6 625}+1)

• W 1919 roku pewien matematyk wykazał, że szereg odwrotności bliźniaczych liczb pierwszych
  
  
  
  jest zbieżny.

Dzisiaj poruszę trochę inny temat, mianowicie będę pisał o liczbach doskonałych.

• Liczbę nazywamy doskonałą jeżeli jest sumą wszystkich swoich dzielników właściwych.

• Zatem najmniejszą liczbą doskonałą jest liczba 6. Dlaczego? Liczba 6 ma trzy dzielniki właściwe : 1,2 oraz 3 więc suma tych dzielników wynosi 6.

• Do tej pory matematycy znaleźli tylko 39 liczb doskonałych.

• Inne liczby doskonałe to 28, 496 oraz 8128.

• Największą obecnie znaną liczbą doskonałą jest liczba 2^82589932 * ( 2^82589933 − 1 ) i liczy ona 49 724 095 cyfr w rozwinięciu dziesiętnym.

• Ciekawe jest również to, że wszystkie do tej pory odnalezione liczby doskonałe są parzyste.

Sito Eratostenesa jest algorytmem, który dla danej liczby N wyznacza wszystkie liczby pierwsze mniejsze od N. Jak to działa?. Poniżej zamieszczam algorytm:

• Tworzymy tablicę liczb naturalnych o rozmiarze N-1 ( tak jakby wszystkie liczby naturalne od 2 do N.)

• Następnie wybieramy pierwszą liczbę z tablicy, Jest nią liczba 2. Teraz wykreślamy wszystkie liczby od 2 do N, które są wielokrotnością liczby 2.

• Bierzemy kolejną liczbę. Jest nią liczba 3. Postępujemy tak samo wykreślając wszystkie jej wielokrotności.

• Proces ten powtarzamy aż dojdziemy do liczby mniejszej niż pierwiastek z N.

W tej chwili wszystkie niewykreślone liczby z tablicy są liczbami pierwszymi.

• Zastanówmy się co by było gdyby liczb pierwszych była skończona ilość. Moglibyśmy je wszystkie pomnożyć. Pojawiła by się jakaś wielka liczba - nazwijmy ją N.

• Spróbujmy teraz dodać do tej liczby jeden. Nasza nowa liczba N+1 nie dzieli się przez żadną z liczb pierwszych, ponieważ zawsze zostaje reszta z dzielenia 1.

• Zatem nasza nowa liczba N+1 jest kolejną liczbą pierwszą. Wniosek z tego jest taki, że mamy nieskończenie wiele liczb pierwszych.

• Dzień dobbry. Trafiłeś na pierwszy wpis na moim blogu o liczbach pierwszych. W tym blogu będę się dzielił z Tobą różnymi nowinkami na temat liczb pierwszych. Artykuy będą krótkie jednak będzie ich sporo - przynajmniej dwa artykuły w tygodniu. Zatem zapraszam do czytania mojego bloga i wpisywania komentarzy :)