This site is supported by donations to The OEIS Foundation.

User:Karsten Meyer/Fingerprint

From OeisWiki
Jump to: navigation, search

"Fingerprints" of the numbers

Introduction

The Content of this subpage may Origin research, but it is important for me. Some readers may find it interesting. If you understand german, you find a similar content here: de.wikibooks.org/wiki/Pseudoprimzahlen:_Potenzen_und_Modulo.

Exponantiation

We want to create a table of numbers. In the first column, we write the sequence of natural numbers:

1
2
3
4
5
6
...

In every row, we write the exponatiation of each number:

n 1 2 3 4 5 6 7 8 9 ...
a
1 1 1 1 1 1 1 1 1 1 ...
2 2 4 8 16 32 64 128 256 512 ...
3 3 9 27 81 243 729 2187 6561 19683 ...
4 4 16 64 256 1024 4096 16384 65536 262144 ...
5 5 25 125 625 3125 15625 78125 390625 1953125 ...
6 6 36 216 1296 7776 46656 279936 1679616 10077696 ...
7 7 49 343 2401 16807 117649 823543 5764801 40353607 ...
8 8 64 512 4096 32768 262144 2097152 16777216 134217728 ...
9 9 81 729 6561 59049 531441 4782969 43046721 387420489 ...
10 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 ...
11 11 121 1331 14641 161051 1771561 19487171 214358881 2357947691 ...
12 12 144 1728 20736 248832 2985984 35831808 429981696 5159780352 ...
.. .. ... ... ... ... ... ... ... ... ...

This is the base!

Modulo operation

If i use the Modulo operation, i will get a pattern. I will take two examples for this:

  • Modul0 15
n 1 2 3 4 5 6 7 8 9 10 11 12 ...
a
1 1 1 1 1 1 1 1 1 1 1 1 1 ...
2 2 4 8 1 2 4 8 1 2 4 8 1 ...
3 3 9 12 3 9 12 3 9 12 3 9 12 ...
4 4 1 4 1 4 1 4 1 4 1 4 1 ...
5 5 10 5 10 5 10 5 10 5 10 5 10 ...
6 6 6 6 6 6 6 6 6 6 6 6 6 ...
7 7 4 13 7 4 13 7 4 13 7 4 13 ...
8 8 4 2 1 8 4 2 1 8 4 2 1 ...
9 9 6 9 6 9 6 9 6 9 6 9 6 ...
10 10 10 10 10 10 10 10 10 10 10 10 10 ...
11 11 1 11 1 11 1 11 1 11 1 11 1 ...
12 12 9 3 6 12 9 3 6 12 9 3 6 ...
13 13 4 7 1 13 4 7 1 13 4 7 1 ...
14 14 1 14 1 14 1 14 1 14 1 14 1 ...
15 0 0 0 0 0 0 0 0 0 0 0 0 ...
16 1 1 1 1 1 1 1 1 1 1 1 1 ...
17 2 4 8 1 2 4 8 1 2 4 8 1 ...
18 3 9 12 3 9 12 3 9 12 3 9 12 ...
19 4 1 4 1 4 1 4 1 4 1 4 1 ...
20 5 10 5 10 5 10 5 10 5 10 5 10 ...
21 6 6 6 6 6 6 6 6 6 6 6 6 ...
22 7 4 13 7 4 13 7 4 13 7 4 13 ...
23 8 4 2 1 8 4 2 1 8 4 2 1 ...
24 9 6 9 6 9 6 9 6 9 6 9 6 ...
25 10 10 10 10 10 10 10 10 10 10 10 10 ...
26 11 1 11 1 11 1 11 1 11 1 11 1 ...
27 12 9 3 6 12 9 3 6 12 9 3 6 ...
28 13 4 7 1 13 4 7 1 13 4 7 1 ...
29 14 1 14 1 14 1 14 1 14 1 14 1 ...
30 0 0 0 0 0 0 0 0 0 0 0 0 ...
31 1 1 1 1 1 1 1 1 1 1 1 1 ...
32 2 4 8 1 2 4 8 1 2 4 8 1 ...
33 3 9 12 3 9 12 3 9 12 3 9 12 ...
34 4 1 4 1 4 1 4 1 4 1 4 1 ...
35 5 10 5 10 5 10 5 10 5 10 5 10 ...
36 6 6 6 6 6 6 6 6 6 6 6 6 ...
37 7 4 13 7 4 13 7 4 13 7 4 13 ...
38 8 4 2 1 8 4 2 1 8 4 2 1 ...
39 9 6 9 6 9 6 9 6 9 6 9 6 ...
40 10 10 10 10 10 10 10 10 10 10 10 10 ...
41 11 1 11 1 11 1 11 1 11 1 11 1 ...
42 12 9 3 6 12 9 3 6 12 9 3 6 ...
43 13 4 7 1 13 4 7 1 13 4 7 1 ...
44 14 1 14 1 14 1 14 1 14 1 14 1 ...
45 0 0 0 0 0 0 0 0 0 0 0 0 ...
... ... ... ... ... ... ... ... ... ... ... ... ... ...

The single Pattern of Modulo 15 is:

n 1 2 3 4
a
1 1 1 1 1
2 2 4 8 1
3 3 9 12 3
4 4 1 4 1
5 5 10 5 10
6 6 6 6 6
7 7 4 13 7
8 8 4 2 1
9 9 6 9 6
10 10 10 10 10
11 11 1 11 1
12 12 9 3 6
13 13 4 7 1
14 14 1 14 1
15 0 0 0 0

This pattern will repeat vertical every steps, and it will repeat horizontal every steps. means here the Carmichael function.

  • Modulo 7
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ...
a
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
2 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
3 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
4 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
5 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
6 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
8 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
9 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
10 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
11 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
12 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
13 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
16 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
17 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
18 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
19 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
20 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
21 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
22 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
23 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 1 ...
24 3 2 6 4 5 1 3 2 6 4 5 1 3 2 6 4 5 1 ...
25 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 4 2 1 ...
26 5 4 6 2 3 1 5 4 6 2 3 1 5 4 6 2 3 1 ...
27 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 6 1 ...
28 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....

The single Pattern of Modulo 7 is:

n 1 2 3 4 5 6
a
1 1 1 1 1 1 1
2 2 4 1 2 4 1
3 3 2 6 4 5 1
4 4 2 1 4 2 1
5 5 4 6 2 3 1
6 6 1 6 1 6 1
7 0 0 0 0 0 0

This pattern will repeat vertical every steps, and it will repeat horizontal every steps. means here the Carmichael function. You will find, that the numbers of the 6th column, exept of the row 7, is 1. You will find also, that the numbers of the 3th column, exept of the row 7, inherit the numbers 1 or 6 (-1 mod 7).

Pattern

Every natural number has it's indiviually pattern, but some sort of natural numbers like prime numbers have a similarities in their pattern.

natural numbers

Natural numbers have a common pattern:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X X X X X
X: X X X X X X
X: X X X X X X
X: X X X X X X
A: A 1 A 1 A 1

The top row is filled with while in the bottom row and alternate. means . Every natural number has this pattern.

prime numbers

Color Formular

A prime number has a typical pattern:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X 1 X X 1
X: X X A X X 1
X: X X 1 X X 1
X: X X A X X 1
A: A 1 A 1 A 1

Zu der für jede natürliche Zahl typischen Zeilen kommen zwei Charaktaristika bei Primzahlen hinzu:

Erstens die geschlossene Einserspalte
1 1 1 ...

in blau gefärbt. Die Einser sind die Werte, welche die Carmichael-Funktion zurückliefert.

Zweitens die, ebenfalls geschlossene, Zeile aus Einsern und Zahlen A die die Zahl (n-1) repräsentieren.

1 A ...

Hier sind es die Werte, die die nach der nach Euler modifizierten Funktion zurückgeliefert werden.

Differenting prime numbers in (4k-1)-form and (4k+1)-form

The structure of the fingerprint of prime numbers of the (4k-1)-form and the4(k+1)-form differ sich in one column:

1 2 3 4 5 6 7 8 9 10
1: 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 5 10 9 7 3 6 1
3: 3 9 5 4 1 3 9 5 4 1
4: 4 5 9 3 1 4 5 9 3 1
5: 5 3 4 9 1 5 3 4 9 1
6: 6 3 7 9 10 5 8 4 2 1
7: 7 5 2 3 10 4 6 9 8 1
8: 8 9 6 4 10 3 2 5 7 1
9: 9 4 3 5 1 9 4 3 5 1
10: 10 1 10 1 10 1 10 1 10 1
1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1
Prime number of the (4k+3)-form Prime number of the (4k+1)-form
Example 11 Example 13

The magenta column of (4k+1) prime numbers is symetric, the magenta column of (4k-1) prime numbers is complementary.

Wie ja schon bekannt ist, gilt für eine Primzahl , das für jede zu teilerfremde Basis gilt (Siehe blaue Spalte in der unteren Tabelle).

1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1

Nun ist aber keine Primzahl, sondern läßt sich in Faktoren zerlegen. So gilt für die unten stehende Tabelle für die Primzahl das ist, sich also z.B. in und zerlegen läßt. Das bedeutet, wenn sich ein Exponent in zwei Faktoren uns zerlegen läßt, das gilt.

Beispiele:

1 2 3 4 5 6 7 8 9 10 11 12
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 3 6 12 11 9 5 10 7 1
3: 3 9 1 3 9 1 3 9 1 3 9 1
4: 4 3 12 9 10 1 4 3 12 9 10 1
5: 5 12 8 1 5 12 8 1 5 12 8 1
6: 6 10 8 9 2 12 7 3 5 4 11 1
7: 7 10 5 9 11 12 6 3 8 4 2 1
8: 8 12 5 1 8 12 5 1 8 12 5 1
9: 9 3 1 9 3 1 9 3 1 9 3 1
10: 10 9 12 3 4 1 10 9 12 3 4 1
11: 11 4 5 3 7 12 2 9 8 10 6 1
12: 12 1 12 1 12 1 12 1 12 1 12 1

Pseudoprimes

What differs Prime numbers from all other natural numbers

In the pattern of Prime numbers , the .th and the .th columns are closed. That means, that every value of the .th column is and every value of the .th is or .

For every non prime number the .th and the .th columns are not closed, and in some cases the .th column is not existence, which means, that no value of the .th column is or .


1 2 3 4 5 6
1: 1 1 1 1 1 1
2: 2 4 8 7 5 1
3: 3 0 0 0 0 0
4: 4 7 1 4 7 1
5: 5 7 8 4 2 1
6: 6 0 0 0 0 0
7: 7 4 1 7 4 1
8: 8 1 8 1 8 1
1 2 3 4
1: 1 1 1 1
2: 2 4 8 1
3: 3 9 2 6
4: 4 1 4 1
5: 5 10 5 10
6: 6 6 6 6
7: 7 4 13 1
8: 8 4 2 1
9: 9 6 9 6
10: 10 10 10 10
11: 11 1 11 1
12: 12 9 3 6
13: 13 4 7 1
14: 14 1 14 1
Neun Fünfzehn

Wie man bei der Neun sehen kann, ist der Mittelbalken noch, wenn auch unterbrochen, vorhanden. Bei der 15 fehlt er vollständig.

Carmichael-Zahlen

Nachdem was bisher geschrieben worden ist, müßte die Neun, und damit alle Quadrate einer Primzahl, eine perfekte Fast-Primzahl sein. Dem ist aber nicht so. Damit eine Nichtprimzahl eine gute Fast-Primzahl sein kann, muß eines zutreffen: muß durch teilbar sein. Nichtprimzahlen mit dieser Eigenschaft nennt man Carmichael-Zahlen.

Was stimmt nun also an der Neun nicht? Die Einser liegen auf der blauen und, mit den Achten, auf der violetten Spalte.

Sie müßten allerdings auf der grünen Spalte liegen, und zusammen mit Achten auf der cyanen Spalte. Da ist aber weder eine Eins, noch eine Acht vorhanden. Einsen auf der grünen Spalte sind typisch für fermatsche Pseudoprimzahlen, und Einsen, bzw. (n-1) auf der cyanen Spalte sind typisch für eulersche Pseudoprimzahlen.

1 2 3 4 5 6
1: 1 1 1 1 1 1
2: 2 4 8 7 5 1
3: 3 0 0 0 0 0
4: 4 7 1 4 7 1
5: 5 7 8 4 2 1
6: 6 0 0 0 0 0
7: 7 4 1 7 4 1
8: 8 1 8 1 8 1

Die weiter oben abgebildete 15 ist eine fermatsche Pseudoprimzahl zu den Basen 4 und 11.

Folgerichtig muß man die Struktur für eine typische Primzahl ergänzen:

1 2 3 4 5 6
1: 1 1 1 1 1 1
X: X X 1 X X 1
X: X X A X X 1
X: X X 1 X X 1
X: X X A X X 1
A: A 1 A 1 A 1

pure eulersche Pseudoprimzahl

Mit der puren eulerschen Pseudoprimzahl ist eine fermatsche Pseudoprimzahl gemeint, bei der jede Basis, zu der die Zahl eine fermatsche Pseuodoprimzahl ist, auch gilt, das die Zahl zu der gleichen Basis auch eine eulersche Pseudoprimzahl ist.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 16 7 14 3 6 12 24 23 21 17 9 18 11 22 19 13 1
3: 3 9 2 6 18 4 12 11 8 24 22 16 23 19 7 21 13 14 17 1
4: 4 16 14 6 24 21 9 11 19 1 4 16 14 6 24 21 9 11 19 1
5: 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6: 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1 6 11 16 21 1
7: 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1 7 24 18 1
8: 8 14 12 21 18 19 2 16 3 24 17 11 13 4 7 6 23 9 22 1
9: 9 6 4 11 24 16 19 21 14 1 9 6 4 11 24 16 19 21 14 1
10: 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
11: 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1 11 21 6 16 1
12: 12 19 3 11 7 9 8 21 2 24 13 6 22 14 18 16 17 4 23 1
13: 13 19 22 11 18 9 17 21 23 24 12 6 3 14 7 16 8 4 2 1
14: 14 21 19 16 24 11 4 6 9 1 14 21 19 16 24 11 4 6 9 1
15: 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16: 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1 16 6 21 11 1
17: 17 14 13 21 7 19 23 16 22 24 8 11 12 4 18 6 2 9 3 1
18: 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1 18 24 7 1
19: 19 11 9 21 24 6 14 16 4 1 19 11 9 21 24 6 14 16 4 1
20: 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
21: 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1 21 16 11 6 1
22: 22 9 23 6 7 4 13 11 17 24 3 16 2 19 18 21 12 14 8 1
23: 23 4 17 16 18 14 22 6 13 24 2 21 8 9 7 11 3 19 12 1
24: 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1 24 1
1 2 3 4 5 6 7 8 9 10
1: 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 16 32 31 29 25 17 1
3: 3 9 27 15 12 3 9 27 15 12
4: 4 16 31 25 1 4 16 31 25 1
5: 5 25 26 31 23 16 14 4 20 1
6: 6 3 18 9 21 27 30 15 24 12
7: 7 16 13 25 10 4 28 31 19 1
8: 8 31 17 4 32 25 2 16 29 1
9: 9 15 3 27 12 9 15 3 27 12
10: 10 1 10 1 10 1 10 1 10 1
11: 11 22 11 22 11 22 11 22 11 22
12: 12 12 12 12 12 12 12 12 12 12
13: 13 4 19 16 10 31 7 25 28 1
14: 14 31 5 4 23 25 20 16 26 1
15: 15 27 9 3 12 15 27 9 3 12
16: 16 25 4 31 1 16 25 4 31 1
17: 17 25 29 31 32 16 8 4 2 1
18: 18 27 24 3 21 15 6 9 30 12
19: 19 31 28 4 10 25 13 16 7 1
20: 20 4 14 16 23 31 26 25 5 1
21: 21 12 21 12 21 12 21 12 21 12
22: 22 22 22 22 22 22 22 22 22 22
23: 23 1 23 1 23 1 23 1 23 1
24: 24 15 30 27 21 9 18 3 6 12
25: 25 31 16 4 1 25 31 16 4 1
26: 26 16 20 25 23 4 5 31 14 1
27: 27 3 15 9 12 27 3 15 9 12
28: 28 25 7 31 10 16 19 4 13 1
29: 29 16 2 25 32 4 17 31 8 1
30: 30 9 6 15 21 3 24 27 18 12
31: 31 4 25 16 1 31 4 25 16 1
32: 32 1 32 1 32 1 32 1 32 1

Es gibt auch fermatsche Pseudoprimzahlen, bei denen die Pseudoprimzahl keine eulersche Pseudoprimzahl ist. Zu diesen fermatschen Pseudoprimzahlen zählen u.a. die 45, 91 und 153.


Selbstreferenzierende Spalte