mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-03-14, 13:22   #1
Krzysztof
 
Mar 2021

616 Posts
Default Sito liczb Mersenne'a (Mersenne Number Sieve?)

Chciałem zaprezentować ciekawą tabelę znalezioną w internacie (będącą sitem liczb Mersenne'a). Zdefiniujmy tabelę Y mającą k kolumn i w wierszy. Wartości k, w należą do liczb naturalnych oraz k > 0 i w > 0. Wybrany element tabeli będziemy oznaczać Y[w,k]. Dodatkowo zdefiniujmy liczbę LW taką, że: LW =3*w+1,5 - 0,5*(-1)^w tj. dla w parzystych LW= 3*w+1, a dla w nieparzystych LW=3*w+2.
Dla wartości k=1 elementy Y[w,1] przyjmują wartości: dla w parzyste Y[w,1] = w+1, a dla w nieparzyste Y[w,1] = (w+1)*2.
Natomiast dla wartości k>1 elementy Y[w,k] przyjmują wartości:
a) dla Y[w,k-1] parzyste i k parzyste Y[w,k] = (Y[w,k-1] + 1 + LW)/2;
b) dla Y[w,k-1] nieparzyste i k parzyste Y[w,k] = (Y[w,k-1] + 1)/2;
c) dla Y[w,k-1] parzyste i k nieparzyste Y[w,k] = Y[w,k-1]/2;
d) dla Y[w,k-1] nieparzyste i k nieparzyste Y[w,k] = (Y[w,k-1] + LW)/2.

Przy tak zdefiniowanej tabeli Y, wprowadźmy jeszcze jedną liczbę: M = 2^k - 1, gdzie k > 2 dodatkowo jeżeli k będzie liczbą pierwszą oraz Y[w,k] różne od 1 dla w <= (M-1)/6, to ze 100% pewnością można powiedzieć, że liczba M dla danego k jest liczbą pierwszą.
Okazuje się też, że wartości Y[w,k] dla danego w powtarzają się okresowo w odstępach mniejszych lub równych LW-1.

Powyżej przedstawione sito liczb można przedstawić za pomocą ciągu bitów odpowiadający liczbie k np. jeżeli Y(w,k) = 1 bit k ustawiamy na 1 (oczywiście uwzględnieniem powyżej opisanych warunków dla Y(W,k)).

Podsumowując - szukam więcej informacji na ile takie sito liczb jest efektywne.
Krzysztof is offline   Reply With Quote
Old 2021-03-14, 14:05   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

1095610 Posts
Default

Quote:
Originally Posted by Krzysztof View Post
Chciałem zaprezentować ciekawą tabelę znalezioną w internacie (będącą sitem liczb Mersenne'a). Zdefiniujmy tabelę Y mającą k kolumn i w wierszy. Wartości k, w należą do liczb naturalnych oraz k > 0 i w > 0. Wybrany element tabeli będziemy oznaczać Y[w,k]. Dodatkowo zdefiniujmy liczbę LW taką, że: LW =3*w+1,5 - 0,5*(-1)^w tj. dla w parzystych LW= 3*w+1, a dla w nieparzystych LW=3*w+2.
Dla wartości k=1 elementy Y[w,1] przyjmują wartości: dla w parzyste Y[w,1] = w+1, a dla w nieparzyste Y[w,1] = (w+1)*2.
Natomiast dla wartości k>1 elementy Y[w,k] przyjmują wartości:
a) dla Y[w,k-1] parzyste i k parzyste Y[w,k] = (Y[w,k-1] + 1 + LW)/2;
b) dla Y[w,k-1] nieparzyste i k parzyste Y[w,k] = (Y[w,k-1] + 1)/2;
c) dla Y[w,k-1] parzyste i k nieparzyste Y[w,k] = Y[w,k-1]/2;
d) dla Y[w,k-1] nieparzyste i k nieparzyste Y[w,k] = (Y[w,k-1] + LW)/2.

Przy tak zdefiniowanej tabeli Y, wprowadźmy jeszcze jedną liczbę: M = 2^k - 1, gdzie k > 2 dodatkowo jeżeli k będzie liczbą pierwszą oraz Y[w,k] różne od 1 dla w <= (M-1)/6, to ze 100% pewnością można powiedzieć, że liczba M dla danego k jest liczbą pierwszą.
Okazuje się też, że wartości Y[w,k] dla danego w powtarzają się okresowo w odstępach mniejszych lub równych LW-1.

Powyżej przedstawione sito liczb można przedstawić za pomocą ciągu bitów odpowiadający liczbie k np. jeżeli Y(w,k) = 1 bit k ustawiamy na 1 (oczywiście uwzględnieniem powyżej opisanych warunków dla Y(W,k)).

Podsumowując - szukam więcej informacji na ile takie sito liczb jest efektywne.
For the benefit of people who read English but not Polish, I append what translate.google.com has to say on this post.
Quote:

Mersenne's Sieve of Numbers
I wanted to present an interesting table found in the boarding school (which is a sieve of Mersenne numbers). Let's define a table Y that has k columns and rows. The values ​​of k, w belong to natural numbers and k> 0 and w> 0. We will denote the selected element of the table as Y [w, k]. Additionally, let's define the number LW such that: LW = 3 * w + 1.5 - 0.5 * (- 1) ^ w i.e. for even LW = 3 * w + 1, and for w odd LW = 3 * w +2.
For the value of k = 1, the elements of Y [w, 1] take the following values: for w even Y [w, 1] = w + 1, and for w odd Y [w, 1] = (w + 1) * 2.
However, for the value of k> 1, the elements of Y [w, k] take the following values:
a) for Y [w, k-1] even and k even Y [w, k] = (Y [w, k-1] + 1 + LW) / 2;
b) for Y [w, k-1] odd and k even Y [w, k] = (Y [w, k-1] + 1) / 2;
c) for Y [w, k-1] even and k odd Y [w, k] = Y [w, k-1] / 2;
d) for Y [w, k-1] odd and k odd Y [w, k] = (Y [w, k-1] + LW) / 2.

With the table Y defined in this way, let's introduce one more number: M = 2 ^ k - 1, where k> 2 additionally if k is a prime number and Y [w, k] different from 1 for w <= (M-1) / 6 then it can be said with 100% certainty that the number M for a given k is prime.
It also turns out that the values ​​of Y [w, k] for a given w repeat periodically at intervals smaller than or equal to LW-1.

The sieve of numbers presented above can be represented by a sequence of bits corresponding to the number k, e.g. if Y (w, k) = 1, bit k is set to 1 (of course taking into account the above-described conditions for Y (W, k)).

To sum up - I am looking for more information on how effective such a sieve of numbers is.
xilman is offline   Reply With Quote
Old 2021-03-14, 16:04   #3
ZFR
 
ZFR's Avatar
 
Feb 2008
Bray, Ireland

2×79 Posts
Default

Quote:
Originally Posted by xilman View Post
For the benefit of people who read English but not Polish, I append what translate.google.com has to say on this post.
Pretty accurate translation, except


Quote:
I wanted to present an interesting table found in the boarding school .
I think the orginal poster meant to write "internecie" (internet) instead of "internacie" (boarding school). Though who can tell...

Quote:
Let's define a table Y that has k columns and rows.
Should be: "Let's define a table Y that has k columns and w rows."
ZFR is offline   Reply With Quote
Old 2021-03-16, 18:52   #4
Krzysztof
 
Mar 2021

2·3 Posts
Default Przykład Excel.

Click image for larger version

Name:	20210316_194908.jpg
Views:	58
Size:	410.3 KB
ID:	24506
Krzysztof is offline   Reply With Quote
Old 2021-03-16, 20:41   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

234408 Posts
Default

Label your columns. I don't see 2 or 3 in your prime list.
Uncwilly is offline   Reply With Quote
Old 2021-03-16, 21:47   #6
Krzysztof
 
Mar 2021

610 Posts
Default Tabela Excel

Górny zielony wiersz to wartości k.
Kolumna "c" zielona to wartości w.
Kolumna "B" to wartości LW.

Jeżeli do wartości k= 5, 7, 11, 13 ....zastosujemy jeszcz sito Małgorzaty, to można jednoznacznie określić czy k z tego ciągu jest liczbą pierwszą. Liczby k nie brane pod uwagę zawsze będą liczbami złożonymi.
Krzysztof is offline   Reply With Quote
Old 2021-03-16, 21:51   #7
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

2×11×31 Posts
Default

Quote:
Originally Posted by Krzysztof View Post
Górny zielony wiersz to wartości k.
Kolumna "c" zielona to wartości w.
Kolumna "B" to wartości LW.

Jeżeli do wartości k= 5, 7, 11, 13 ....zastosujemy jeszcz sito Małgorzaty, to można jednoznacznie określić czy k z tego ciągu jest liczbą pierwszą. Liczby k nie brane pod uwagę zawsze będą liczbami złożonymi.
The top green row is k values.
The green "c" column is the values of w.
Column "B" is LW values.

If we apply Margaret's sieve to the value of k = 5, 7, 11, 13 .... it can be clearly determined whether k of this sequence is a prime number. The numbers k that are not taken into account will always be composite numbers.
Viliam Furik is offline   Reply With Quote
Old 2021-03-17, 07:41   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110001110112 Posts
Default

Quote:
Originally Posted by Viliam Furik View Post
The numbers k that are not taken into account will always be composite numbers.
Prove it.

(Not you. I mean the OP )
The argument is that almost any "random" sieve will work (or, doh, will appear to work), because there are only very few mersenne primes. I can "invent" a new sieve: pick prime numbers randomly, in increasing order, starting with some value, like over 100 or so (trying to get around the law of small numbers, haha). Any number you picked will be the exponent of a composite mersenne.

Last fiddled with by LaurV on 2021-03-17 at 07:43
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Sieve Godzilla Miscellaneous Math 1 2019-02-19 13:00
Double-mersenne sieve programming axn Programming 32 2014-05-08 12:43

All times are UTC. The time now is 20:39.


Mon Oct 25 20:39:19 UTC 2021 up 94 days, 15:08, 0 users, load averages: 1.80, 2.11, 2.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.