Zielony Smok - logo witryny

Naszyjniki i bransoletki

Liczby względnie pierwsze

Jak wiemy z rozdziału poświęconego liczbom pierwszym każda liczba większa od 1 jest iloczynem liczb pierwszych lub sama jest liczbą pierwszą (czyli iloczynem siebie i 1):

7 jest liczbą pierwszą
14 = 2 * 7
15 = 3 * 5
21 = 3 * 7

Liczby względnie pierwsze to takie liczby całkowite, które po rozłożeniu na czynniki pierwsze nie mają wspólnych czynników (dzielników) poza 1.

4 i 15 są liczbami względnie pierwszymi
14 i 21 nie są względnie pierwsze gdyż obie dzielą się przez 7
15 i 21 nie są względnie pierwsze gdyż obie dzielą się przez 3

Aby sprawdzić, czy liczby są względnie pierwsze, najlepiej użyć funkcji obliczającej największy wspólny dzielnik (NWD). Jeżeli NWD = 1 to liczby są względnie pierwsze

Funkcja φ Eulera

Nazywana jest również funkcją φ Gaussa lub tocjentem.

Funkcja φ(n) oblicza liczbę liczb względnie pierwszych z n, które są większe lub równe 1 i mniejsze od n, czyli spełniają warunek naszyjniki i bransoletki

n 1 2 3 4 5 6 7 8 9 10 11 12
φ(n) 1 1 2 2 4 2 6 4 6 4 10 4
liczby
względnie
pierwsze
z n
1 1 1,2 1,3 1,2,3,4 1,5 1,2,3,4,5,6 1,3,5,7 1,2,4,5,7,8 1,3,7,9 1,2,3,4,5,6,7,8,9,10 1,5,7,11
czynniki
pierwsze n
2 3 2×2=22 5 2×3 7 2x2x2=23 3×3=32 2×5 11 2x2x3=22x3

Wzór:

naszyjniki i bransoletki

gdzie:

Π oznacza 'iloczyn’

p oznacza dzielnik pierwszy liczby n.

p|n oznacza, że składnikami iloczynu są wszystkie dzielniki pierwsze liczby n (bez powtórzeń, czyli składnik jest uwzględniany tylko raz)

Przykład 1

Liczba naszyjniki i bransoletki

naszyjniki i bransoletki

Istnieją 4 liczby względnie pierwsze z n (1,5,7,11);

Przykład 2

naszyjniki i bransoletki

Właściwości

Właściwość 1

naszyjniki i bransoletki gdy n jest liczbą pierwszą.

naszyjniki i bransoletki

Właściwość 2

naszyjniki i bransoletki, jeżeli m i n są względnie pierwsze.

naszyjniki i bransoletki

Liczby 14 i 15 są względnie pierwsze.

naszyjniki i bransoletki

Właściwość 3

naszyjniki i bransoletki jeżeli naszyjniki i bransoletki

Ponieważ 8 = 23 to naszyjniki i bransoletki

Właściwość 4

Dla dowolnej liczby całkowitej n zachodzi:

naszyjniki i bransoletki

Sumowanie przebiega po wszystkich dzielnikach m liczby n.

naszyjniki i bransoletki

Właściwość 5

Jeżeli

naszyjniki i bransoletki

jest rozkładem liczby n na czynniki pierwsze to:

naszyjniki i bransoletki

naszyjniki i bransoletki

więc

naszyjniki i bransoletki

Tabela wartości funkcji tocjent i wykaz liczb względnie pierwszych

Naszyjniki i bransoletki

Naszyjnik składa się z n koralików, z których każdy może być w jednym z k kolorów.

Naszyjnik jest też (rozpiętym) łańcuchem zawierającym n znaków wziętych z alfabetu mającego k znaków.

Wszelkie naszyjniki powstałe przez obrót (rotację) są uważane za równoważne.

Naszyjnik kombinatoryczny podobnie jak jubilerski ma tylko jedną stronę, czyli jeden układ 'koralików’.

Bransoletka kombinatoryczna podobnie jak jubilerska, jest podobna do naszyjnika, ale ma dwie strony. Drugą stronę uzyskujemy dokonując refleksji (odbicia).

Poniżej przedstawiamy naszyjniki i bransoletki dla n = 6 i k = 2.

naszyjniki i bransoletki

Liczba naszyjników N2(6) = 14

Liczba bransoletek B2(6) = 13

Układ oznaczony jako x to dwa układy w sensie naszyjników, a jeden układ w sensie bransoletek.

Układ ten wykazuje symetrię chiralną, która występuje wtedy, gdy dwie figury nie dadzą się na siebie nałożyć jedynie przez translację (przesunięcie) i rotację (obrót), ale można je nałożyć przez refleksję (odbicie).

naszyjniki i bransoletki

Po odwróceniu jednego z zaznaczonych układów otrzymujemy drugi, więc ponieważ naszyjników nie można odwracać, liczymy je jako dwa układy. Ponieważ bransoletki możemy odwracać liczmy je jako jedną bransoletkę.

Naszyjniki

Liczbę naszyjników można obliczyć ze wzoru:

naszyjniki i bransoletki

gdzie:

n – to liczba elementów

k – to liczba stanów (kolorów), które może przyjąć każdy z koralików

di są dzielnikami n od d1 = 1 do dv = n. v(n) jest liczbą dzielników n.

φ(di) – oznacza funkcję φ Eulera, nazywaną czasem funkcją Gaussa.

Przykład 1

Obliczmy N dla n = 10 i k = 2

Dzielniki liczby 10 to {1, 2, 5, 10}

φ(1) = 1

φ(2) = 1

φ(5) = 4

φ(10) = 4

naszyjniki i bransoletki

Tablice naszyjników

Bransoletki

Liczbę bransoletek możemy obliczyć ze wzoru:

naszyjniki i bransoletki

Wzoru umieszczonego wyżej używamy gdy n jest liczbą nieparzystą.

Wzoru umieszczonego niżej używamy, gdy n – jest liczbą parzystą.

Nk(n) – oznacza liczbę naszyjników

Powyższy wzór można uprościć:

naszyjniki i bransoletki

Wzoru umieszczonego wyżej używamy gdy n jest liczbą nieparzystą.

Wzoru umieszczonego niżej używamy, gdy n – jest liczbą parzystą.

Gdy k = 2, a n jest nieparzystą liczbą pierwszą (czyli większą od 2), wzór upraszcza się do:

naszyjniki i bransoletki

Przykład 2

Obliczamy liczbę bransoletek dla n = 10 i k = 2

Skorzystamy ze wzoru uproszczonego.

naszyjniki i bransoletki

Ponieważ n jest liczbą parzystą:

naszyjniki i bransoletki

Tablice bransoletek

Kody

Kody do obliczeń w języku JavaScript możesz znaleźć w książce Matematyka dla programistów JavaScript.

Kody do obliczeń w języku Java możesz znaleźć w książce Matematyka dla programistów Java.