Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie
        STUDIA        

Liczby pierwsze a systemy zapisu liczb.

Teoria liczb

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
3 odpowiedzi w tym temacie

#1 piastlis

piastlis

    Nowicjusz

  • Użytkownik
  • 3 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 22.10.2016 - 00:28

Więc tak od początku...Nie jestem matematykiem ani zawodowo ani hobbystycznie.Naukę zakończyłem jako mgr.(automatyk-elektryk). Programuję w C++ w wolnym czasie.Podczas pisania kalkulatora "bignum" zauważyłem coś ciekawego.Potrafię to zapisać jako twierdzenie:

 

Dla każdego systemu numerycznego jeżeli odwrotność (1/n) liczby naturalnej n ma okresowość n-1 cyfr to n jest liczbą pierwszą.

 

Nie potrafię tego potwierdzić ani zaprzeczyć więc potrzebowałbym konsultacji matematyka.

Przykłady:(pierwsza liczba to system liczbowy,następne to liczby pierwsze dla których zasada ma zastosowanie)

2-1,3,5,11,13,19,29,37,53,59,61,67,83,101,107,131,139,149,163,
3-1,5,7,17,19,29,31,43,53,79,89,101,113,127,137,139,149,163,
4-1,
5-1,3,7,17,23,37,43,47,53,73,83,97,103,107,113,137,157,167,
6-1,11,13,17,41,59,61,79,83,89,103,107,109,113,127,131,137,151,157,
7-1,5,11,13,17,23,41,61,67,71,79,89,97,101,107,127,151,163,
8-1,3,5,11,29,53,59,83,101,107,131,149,
9-1,
10-1,7,17,19,23,29,47,59,61,97,109,113,131,149,167,
11-1,3,13,17,23,29,31,41,47,59,67,71,73,101,103,109,149,163,
12-1,5,7,17,31,41,43,53,67,101,103,113,127,137,139,149,151,163,
13-1,5,11,19,31,37,41,47,59,67,71,73,83,89,97,109,137,149,151,167,
14-1,3,17,19,23,29,53,59,73,83,89,97,109,127,131,149,151,
15-1,13,19,23,29,37,41,47,73,83,89,97,101,107,139,149,151,157,167,
16-1,
17-1,3,5,7,11,23,31,37,41,61,97,107,113,131,139,167,
18-1,5,11,29,37,43,53,59,61,67,83,101,107,109,139,149,157,163,
19-1,7,11,13,23,29,37,41,43,47,53,83,89,113,139,163,
20-1,3,13,17,23,37,43,47,53,67,73,83,103,107,113,137,157,163,167,
21-1,19,23,29,31,53,71,97,103,107,113,137,139,149,157,
22-1,5,17,19,31,37,41,47,53,71,83,107,131,139,
23-1,3,5,17,47,59,89,97,113,127,131,137,149,167,
24-1,7,11,13,17,31,37,41,59,83,89,107,109,113,137,157,
25-1,
26-1,3,7,29,41,43,47,53,61,73,89,97,101,107,131,137,139,157,167,
27-1,5,17,29,53,89,101,113,137,149,
28-1,5,11,13,17,23,41,43,67,71,73,79,89,101,107,
29-1,3,11,17,19,41,43,47,73,79,89,97,101,113,127,131,137,163,
30-1,11,23,41,43,47,59,61,79,89,109,131,151,167,
31-1,7,17,29,47,53,59,61,67,71,73,89,107,131,137,
32-1,3,5,13,19,29,37,53,59,67,83,107,139,149,163,
33-1,5,7,13,19,23,43,47,53,59,71,73,89,113,137,
34-1,19,23,31,41,43,53,59,67,73,79,83,101,113,149,157,167,
35-1,3,11,37,41,47,53,61,71,79,83,89,101,103,137,151,167,
36-1,
37-1,5,13,17,23,29,59,79,97,109,113,131,167,
38-1,3,5,7,23,47,59,89,97,101,107,113,149,157,
39-1,11,17,29,37,47,53,59,73,79,83,97,109,113,127,167,
40-1,7,11,17,19,23,29,47,59,73,97,101,103,109,131,137,139,149,167,
41-1,3,11,13,17,19,47,53,67,89,97,149,167,
42-1,5,23,31,37,59,71,73,83,101,109,137,163,
43-1,5,23,29,31,47,59,61,79,83,89,103,107,113,127,137,149,157,167,
44-1,3,17,23,29,31,47,59,61,67,71,73,103,109,163,
45-1,7,13,17,47,53,73,83,103,107,113,127,137,163,167,
46-1,11,13,17,43,67,83,89,101,107,113,127,137,167,
47-1,3,5,7,29,41,59,71,73,79,83,109,113,137,
48-1,5,17,19,29,31,41,43,53,67,79,89,101,103,127,137,149,151,
49-1,
50-1,3,11,13,29,37,53,59,67,83,101,107,109,131,139,149,163,
51-1,11,19,23,53,61,67,89,101,103,107,109,137,149,151,167,
52-1,5,7,11,19,31,37,41,47,59,71,83,109,137,149,151,163,167,
53-1,3,5,19,23,31,41,71,73,79,83,101,103,109,127,137,139,157,167,
54-1,7,13,17,37,41,59,61,79,83,89,103,107,113,131,137,151,
55-1,29,31,37,43,53,59,61,71,83,101,107,113,127,137,149,157,167,
56-1,3,17,23,29,37,41,53,59,71,83,89,97,109,127,131,139,149,151,
57-1,5,11,17,23,37,47,67,83,97,109,127,131,137,149,
58-1,5,13,17,41,47,53,73,83,89,97,107,109,113,127,137,139,149,
59-1,3,7,13,19,37,61,71,73,79,89,97,101,107,109,113,149,167,
60-1,19,23,29,41,47,73,79,83,89,97,107,149,157,167,
61-1,7,11,17,23,29,37,43,53,59,67,71,89,101,139,151,157,
62-1,3,5,11,17,43,47,71,73,83,89,103,109,137,149,157,
63-1,5,11,13,17,23,41,43,61,67,71,79,89,101,107,151,157,163,
64-1,
65-1,3,17,23,31,41,53,59,71,89,103,107,109,127,149,
66-1,7,23,29,47,79,83,89,101,107,113,131,137,149,157,163,
67-1,5,13,19,23,41,47,53,59,61,71,83,101,103,107,109,113,127,131,137,163,167,
68-1,3,5,7,11,29,61,71,73,79,97,107,113,139,163,167,
69-1,29,37,41,43,47,59,67,71,109,157,167,
70-1,19,41,47,59,79,89,103,107,109,113,137,139,149,157,163,167,
71-1,3,13,17,19,41,43,53,61,83,97,103,107,137,149,151,167,
72-1,5,11,13,19,29,37,43,53,59,83,101,107,109,131,139,149,157,163,
73-1,5,7,11,17,29,31,43,47,53,59,83,101,107,139,157,163,167,
74-1,3,11,17,23,31,53,67,79,83,89,97,101,103,107,113,149,157,167,
75-1,7,17,31,41,53,79,89,101,103,113,137,149,163,
76-1,13,23,29,37,41,43,47,83,89,97,113,131,163,
77-1,3,5,29,43,47,59,79,103,107,149,151,157,
78-1,5,17,19,47,61,67,71,73,103,107,127,149,167,
79-1,11,17,19,23,29,31,37,53,61,67,83,109,113,137,149,163,167,
80-1,3,7,13,17,23,47,53,67,83,97,107,113,137,157,163,167,
81-1,
82-1,5,7,17,47,59,71,79,89,97,107,131,137,151,163,167,
83-1,3,5,11,23,31,59,89,97,101,127,131,137,149,157,167,
84-1,11,13,23,29,31,53,71,73,97,103,107,113,137,149,157,
85-1,11,13,29,47,53,67,79,83,103,109,127,131,137,139,157,
86-1,3,19,23,31,47,53,73,79,89,101,103,113,127,137,167,
87-1,5,7,37,47,53,61,67,73,97,103,131,149,157,
88-1,5,17,23,41,47,53,73,83,103,107,131,139,157,
89-1,3,7,13,19,23,29,37,41,43,59,83,101,113,137,149,151,163,
90-1,11,17,19,23,29,47,59,97,101,113,131,137,139,149,167,
91-1,17,19,37,43,47,59,61,83,107,109,127,137,149,157,167,
92-1,3,5,17,37,47,53,59,61,71,89,97,113,127,137,139,149,163,167,
93-1,5,13,37,41,59,71,73,101,107,113,127,131,139,149,151,
94-1,7,11,37,41,53,101,107,113,137,149,157,163,
95-1,3,11,17,29,41,67,89,107,109,131,137,157,167,
96-1,7,11,17,31,37,59,61,83,89,103,107,109,113,127,131,151,157,
97-1,5,13,17,19,23,29,41,59,83,107,127,131,137,149,157,
98-1,3,5,13,19,29,37,43,53,59,67,83,101,107,109,131,139,149,
99-1,17,23,41,47,59,67,71,73,101,103,109,149,
100-1,
101-1,3,7,11,29,41,53,59,67,73,83,103,113,127,139,149,163,167,
102-1,5,13,23,29,59,71,73,83,89,97,137,139,151,157,167,
103-1,5,7,23,53,59,83,89,101,107,109,113,131,163,167,
104-1,3,31,41,43,47,53,61,71,73,89,97,101,107,131,137,139,151,157,167,
105-1,11,17,19,29,31,43,47,61,83,167,
106-1,11,13,23,29,31,37,41,43,59,71,73,127,131,137,149,151,163,167,
107-1,3,5,11,17,23,47,73,79,83,97,113,163,
108-1,5,7,17,19,29,41,53,67,79,89,101,103,113,137,139,149,151,163,
109-1,17,19,23,37,47,53,59,79,101,103,107,127,139,149,151,163,167,
110-1,3,7,13,19,31,41,97,113,127,131,137,139,167,
111-1,13,23,41,53,59,67,97,131,137,139,149,151,167,
112-1,5,11,17,23,41,43,61,73,89,97,101,107,127,151,163,
113-1,3,5,17,23,29,37,47,59,67,71,73,79,89,101,107,137,167,
114-1,17,29,31,43,47,53,59,79,97,103,107,127,137,139,151,157,163,
115-1,7,13,31,43,59,61,67,71,73,83,89,103,107,109,131,139,149,151,
116-1,3,11,17,19,37,41,43,47,61,79,89,101,113,127,131,137,163,
117-1,5,7,11,19,31,41,47,67,73,83,89,137,149,151,163,167,
118-1,5,11,29,53,67,71,73,79,83,89,97,113,127,131,167,
119-1,3,13,29,43,89,101,109,113,131,139,157,167,
120-1,23,43,47,53,59,61,73,89,97,109,131,151,163,167,
121-1,
122-1,3,5,7,17,23,79,83,89,107,109,131,149,163,
123-1,5,11,13,47,71,97,103,109,113,139,157,167,
124-1,7,13,17,19,29,37,47,53,59,61,67,71,89,103,107,131,137,163,
125-1,3,17,23,47,53,83,107,113,137,167,
126-1,17,23,29,37,53,59,71,73,79,83,97,131,139,149,151,
127-1,5,11,19,29,31,47,53,71,79,89,101,107,109,131,
128-1,3,5,11,13,19,37,53,59,61,67,83,101,107,131,139,149,163,
129-1,7,11,17,19,23,37,41,47,59,61,83,101,107,151,163,167,
130-1,17,23,29,37,41,67,71,83,89,101,113,127,139,151,163,
131-1,3,7,17,29,37,59,73,107,137,149,157,167,
132-1,5,13,23,43,47,53,59,61,71,73,79,89,113,137,139,
133-1,5,17,37,47,53,71,73,79,83,107,109,113,127,131,151,157,
134-1,3,11,23,29,41,43,47,71,97,113,127,137,139,149,151,167,
135-1,19,23,29,31,37,41,47,73,83,89,97,101,107,139,149,167,
136-1,7,13,19,23,31,41,59,67,71,83,97,101,113,149,157,167,
137-1,3,5,13,29,31,47,53,83,89,97,113,131,149,157,163,
138-1,5,7,11,41,47,53,71,79,83,97,103,107,149,167,
139-1,11,17,47,53,61,71,79,83,101,107,109,127,131,149,157,163,167,
140-1,3,11,41,53,61,71,83,89,113,137,151,167,
141-1,13,17,31,43,53,59,67,73,83,101,127,131,139,149,151,
142-1,5,17,29,41,59,79,113,137,139,157,167,
143-1,3,5,7,17,19,23,29,37,83,89,101,103,137,167,
144-1,
145-1,7,11,13,23,31,41,53,67,79,83,89,107,131,167,
146-1,3,17,19,31,37,47,67,103,109,113,149,151,167,
147-1,5,17,19,29,41,43,53,67,79,89,101,103,113,149,163,
148-1,5,17,19,23,29,31,43,59,61,89,103,109,131,163,167,
149-1,3,11,13,23,41,43,59,71,79,83,89,101,109,137,163,167,
150-1,7,11,13,17,37,59,83,89,107,113,127,137,
151-1,11,41,47,53,59,73,89,101,103,109,113,139,149,157,167,
152-1,3,5,7,23,41,47,59,61,67,89,101,107,113,149,157,
153-1,5,23,29,37,41,61,71,79,97,107,109,131,163,167,
154-1,13,19,47,53,67,79,83,89,97,101,103,131,139,163,
155-1,3,19,23,29,43,59,71,83,89,97,167,
156-1,11,17,29,47,53,59,79,83,97,101,103,109,113,127,139,167,
157-1,5,7,23,41,43,53,59,61,73,83,97,103,107,131,137,139,149,151,
158-1,3,5,13,17,23,31,41,43,59,107,113,137,139,151,167,
159-1,7,17,23,29,43,73,83,89,109,113,149,163,167,
160-1,11,17,29,47,59,73,101,109,113,131,137,139,149,167,
161-1,3,11,37,47,53,59,73,79,107,109,131,137,139,149,167,
162-1,5,11,13,19,43,53,59,67,83,101,107,109,131,149,157,
163-1,5,13,17,29,37,43,47,71,83,89,137,149,151,157,167,
164-1,3,7,17,29,47,53,71,79,89,101,137,149,151,167,
165-1,17,19,37,59,61,67,79,89,97,103,107,109,139,151,163,167,
166-1,7,19,23,29,31,37,61,67,73,107,109,127,137,151,163,
167-1,3,5,11,13,17,19,31,37,47,53,101,107,109,113,149,
168-1,5,23,31,37,59,67,83,97,101,103,109,113,131,137,
169-1,
170-1,3,37,41,47,59,71,103,107,127,137,149,163,
171-1,7,11,13,23,29,41,47,53,83,89,97,109,113,131,139,
172-1,5,11,23,29,31,37,47,59,73,83,89,107,113,127,137,149,157,167,
173-1,3,5,7,11,17,19,53,59,61,71,97,101,103,107,127,
174-1,19,47,59,73,83,101,103,107,109,163,
175-1,13,17,23,41,43,67,71,73,89,101,107,127,157,163,
176-1,3,13,17,23,29,31,41,47,61,101,109,149,
177-1,5,17,29,31,41,43,53,61,71,73,97,103,107,137,157,167,
178-1,5,7,11,23,53,67,103,107,109,157,
179-1,3,31,41,47,53,59,73,83,97,107,109,113,137,139,
180-1,7,13,17,23,37,47,53,67,73,83,97,103,107,113,127,137,167,
181-1,17,19,23,41,47,53,61,83,89,97,103,107,109,113,131,149,151,157,163,
182-1,3,5,11,17,23,29,47,67,127,137,163,167,
183-1,5,11,37,41,59,113,127,137,149,157,163,
184-1,11,13,17,19,29,43,47,67,71,83,89,97,101,107,127,137,167,
185-1,3,7,19,29,47,53,59,61,67,73,83,89,107,127,131,137,
186-1,19,41,47,53,71,73,79,83,151,
187-1,5,7,37,59,79,97,101,103,107,113,131,149,167,
188-1,3,5,13,29,41,59,73,79,83,103,109,113,131,137,
189-1,11,13,23,29,31,61,71,97,103,107,113,137,139,149,
190-1,17,37,41,43,53,59,61,73,83,101,103,137,149,167,
191-1,3,23,43,53,59,67,73,89,101,103,107,137,157,
192-1,5,7,17,19,29,41,43,53,79,89,113,127,137,139,149,163,
193-1,5,11,13,17,19,29,41,47,53,61,73,79,89,113,167,
194-1,3,7,11,17,23,41,53,71,101,109,127,137,
195-1,11,23,29,59,67,71,79,101,107,137,139,157,163,
196-1,
197-1,3,5,13,17,31,67,71,79,89,113,131,139,149,167,
198-1,5,17,23,31,37,41,43,47,53,71,83,107,131,
199-1,7,17,23,31,41,47,73,97,101,103,113,137,149,151,
200-1,3,11,19,29,37,43,53,59,61,83,101,107,109,139,149,157,


Użytkownik piastlis edytował ten post 22.10.2016 - 09:32

  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Mariusz M

Mariusz M

    Wielki Analityk

  • Użytkownik
  • Redaktor
  • 901 postów
414
Instruktor II
  • Płeć:Mężczyzna

Napisano 25.10.2016 - 23:36

To może być konsekwencją małego twierdzenia Fermata , poszukaj czegoś o tym

ps jak bardzo jest zaawansowana twoja wiedza z programowania w C


  • 0

#3 piastlis

piastlis

    Nowicjusz

  • Użytkownik
  • 3 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 24.11.2016 - 01:27

Tematem się zainteresowałem gdyż szukałem metody oszacowania ilości bitów niezbędnych do obliczenia wyniku dzielenia.Sprawa okazała się nie tak prosta jak mi się wydawało.....Zauważyłem potencjał tego twierdzenia do obliczania bardzo dużych liczb pierwszych. Metoda działa dla liczb w postaci 2^(2^n-1)-1 ale jest nieefektywna.Wymaga wykonania sqrt{2^n-1}  testów na liczbach o długości 10^6-10^9 bitów. Co do umiejętności programowania.... Pascal - poziom profesjonalny a C++ - nadrabiam zaległości :shifty:


Użytkownik piastlis edytował ten post 24.11.2016 - 01:45

  • 0

#4 piastlis

piastlis

    Nowicjusz

  • Użytkownik
  • 3 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 27.11.2016 - 09:34

Zapoznałem się z małym twierdzeniem Fermata i rozwiązuje ono tylko część problemu.Oczywiście bezpośrednio odnosi się do liczb które są na powyższej liście ale dotyczy też reszty liczb.

 

Np dla systemu 2 liczba 23:

 

małe twierdzenie Fermata   ----  2^22 mod 23 =1

ale okresowość odwrotności  ----  11

 

Jest to na tyle ciekawe że udało mi się skorelować podzielność liczby w postaci 2^n-1 z okresowością odwrotności wykładnika n:

(1--n,  2--2^n-1  3-- czy pierwsza  4-- reszta z dzielenia przez 23):

      

1--                                    1-1 1
2 --                                   3-1 3
3 --                                   7-1 7
4  --                               15-0 15
5  --                               31-1 8
6  --                               63-0 17
7  --                             127-1 12
8  --                             255-0 2
9  --                             511-0 5
10--                           1023-0 11
11--                           2047-0 0   !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
12--                           4095-0 1
13--                           8191-1 3
14--                         16383-0 7
15--                         32767-0 15
16--                         65535-0 8
17--                       131071-1 17
18--                       262143-0 12
19--                       524287-1 2
20--                     1048575-0 5
21--                     2097151-0 11
22--                     4194303-0 0
23--                     8388607-0 1   <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
24--                   16777215-0 3
25--                   33554431-0 7
26--                   67108863-0 15
27--                 134217727-0 8
28--                 268435455-0 17
29--                 536870911-0 12
30--                1073741823-0 2
31--                2147483647-1 5
32--                4294967295-0 11
33--                8589934591-0 0
34--              17179869183-0 1
35--              34359738367-0 3
36--              68719476735-0 7
37--            137438953471-0 15
38--            274877906943-0 8
39--            549755813887-0 17
40--          1099511627775-0 12
41--          2199023255551-0 2
42--           4398046511103-0 5
43--           8796093022207-0 11
44--         17592186044415-0 0
45--         35184372088831-0 1
46--         70368744177663-0 3
47--       140737488355327-0 7
48--       281474976710655-0 15
49--       562949953421311-0 8
50--     1125899906842623-0 17
51--     2251799813685247-0 12
52--     4503599627370495-0 2
53--     9007199254740991-0 5
54--   18014398509481983-0 11
55--   36028797018963967-0 0
56--   72057594037927935-0 1
57--  144115188075855871-0 3
58--  288230376151711743-0 7
59--  576460752303423487-0 15
60--1152921504606846975-0 8
61--2305843009213693951-1 17
62--4611686018427387903-0 12
63--9223372036854775807-0 2
 

Okresowość odwrotności liczby 23 -11 sugeruje że 2^11-1=2047 jest podzielna przez 23 i nie jest liczbą pierwszą.

 

Gdybym miał przetłumaczyć małe twierdzenie Fermata na pojęcie okresowości brzmiałoby:

 

Dla każdego systemu numerycznego jeżeli odwrotność (1/n) liczby naturalnej n  jej okresowość lub  całkowita wielokrotność okresowości ma  n-1 cyfr to n jest liczbą pierwszą.


Użytkownik piastlis edytował ten post 27.11.2016 - 10:27

  • 0