Inhaltsverzeichnis

Development of
Algorithmic Constructions

12:20:05
English
19.Sep 2021

Sieve of Ulam (vertical III)

mathematical description

Instead of sieving all odd numbers by the order of rising numbers,
the numbers are sorted in columns and each colomn is sieved:

Numbers % 7=0 are green:

1357911131517192123252729
313335373941434547495153555759
616365676971737577798183858789
9193959799101103105107109111113115117119
121123125127129131133135137139141143145147149
151153155157159161163165167169171173175177179
181183185187189191193195197199201203205207209
211213215217219221223225227229231233235237239
241243245247249251253255257259261263265267269
271273275277279281283285287289291293295297299
301303305307309311313315317319321323325327329
331333335337339341343345347349351353355357359
361363365367369371373375377379381383385387389
391393395397399401403405407409411413415417419
421423425427429431433435437439441443445447449
451453455457459461463465467469471473475477479
481483485487489491493495497499501503505507509
511513515517519521523525527529531533535537539
541543545547549551553555557559561563565567569
571573575577579581583585587589591593595597599
601603605607609611613615617619621623625627629
631633635637639641643645647649651653655657659
661663665667669671673675677679681683685687689
691693695697699701703705707709711713715717719
721723725727729731733735737739741743745747749
751753755757759761763765767769771773775777779
781783785787789791793795797799801803805807809
811813815817819821823825827829831833835837839
841843845847849851853855857859861863865867869
871873875877879881883885887889891893895897899

Numbers % 11=0 are green:

1357911131517192123252729
313335373941434547495153555759
616365676971737577798183858789
9193959799101103105107109111113115117119
121123125127129131133135137139141143145147149
151153155157159161163165167169171173175177179
181183185187189191193195197199201203205207209
211213215217219221223225227229231233235237239
241243245247249251253255257259261263265267269
271273275277279281283285287289291293295297299
301303305307309311313315317319321323325327329
331333335337339341343345347349351353355357359
361363365367369371373375377379381383385387389
391393395397399401403405407409411413415417419
421423425427429431433435437439441443445447449
451453455457459461463465467469471473475477479
481483485487489491493495497499501503505507509
511513515517519521523525527529531533535537539
541543545547549551553555557559561563565567569
571573575577579581583585587589591593595597599
601603605607609611613615617619621623625627629
631633635637639641643645647649651653655657659
661663665667669671673675677679681683685687689
691693695697699701703705707709711713715717719
721723725727729731733735737739741743745747749
751753755757759761763765767769771773775777779
781783785787789791793795797799801803805807809
811813815817819821823825827829831833835837839
841843845847849851853855857859861863865867869
871873875877879881883885887889891893895897899

Numbers % 13=0 are green:

1357911131517192123252729
313335373941434547495153555759
616365676971737577798183858789
9193959799101103105107109111113115117119
121123125127129131133135137139141143145147149
151153155157159161163165167169171173175177179
181183185187189191193195197199201203205207209
211213215217219221223225227229231233235237239
241243245247249251253255257259261263265267269
271273275277279281283285287289291293295297299
301303305307309311313315317319321323325327329
331333335337339341343345347349351353355357359
361363365367369371373375377379381383385387389
391393395397399401403405407409411413415417419
421423425427429431433435437439441443445447449
451453455457459461463465467469471473475477479
481483485487489491493495497499501503505507509
511513515517519521523525527529531533535537539
541543545547549551553555557559561563565567569
571573575577579581583585587589591593595597599
601603605607609611613615617619621623625627629
631633635637639641643645647649651653655657659
661663665667669671673675677679681683685687689
691693695697699701703705707709711713715717719
721723725727729731733735737739741743745747749
751753755757759761763765767769771773775777779
781783785787789791793795797799801803805807809
811813815817819821823825827829831833835837839
841843845847849851853855857859861863865867869
871873875877879881883885887889891893895897899

If you compare the sieved numbers of two neighboured coloumns,
you can see that the difference is always constant.

For example:
Regarding 7, in the first coloumn the 4.number is divisible by 7.
In the second coloumn the 3. / 10. number is divisible by 7.

Rule for 7 is +6 (mod 7)
next coloumn = preceding column + 6 mod 7

Rule for 11 is +8 (mod 11)
Rule for 13 is +6 (mod 13)

You can calculate the offset for every prime > 5 and < 30 and
make a sieving by the primes for the different coloumns.

The calculation of the starting points for the primes for the first two coloumns can be made
by technics of the sieve of Ulam vertical (II).

Only the primes less the square root of the field and the refered offsets are necessary for sieving the non primes.

Implementation in Mupad:



                                 1, FALSE

                                 31, TRUE

                                 61, TRUE

                                 151, TRUE

                                 181, TRUE

                                 211, TRUE

                                 241, TRUE

                                 271, TRUE

                                 331, TRUE

                                 421, TRUE

                                 541, TRUE

                                 571, TRUE

                                 601, TRUE

                                 631, TRUE

                                 661, TRUE

                                 691, TRUE

                                 751, TRUE

                                 811, TRUE

                                  7, TRUE

                                 37, TRUE

                                 67, TRUE

                                 97, TRUE

                                 127, TRUE

                                 157, TRUE

                                 277, TRUE

                                 307, TRUE

                                 337, TRUE

                                 367, TRUE

                                 397, TRUE

                                 457, TRUE

                                 487, TRUE

                                 547, TRUE

                                 577, TRUE

                                 607, TRUE

                                 727, TRUE

                                 757, TRUE

                                 787, TRUE

                                 877, TRUE

                                 11, TRUE

                                 41, TRUE

                                 71, TRUE

                                 101, TRUE

                                 131, TRUE

                                 191, TRUE

                                 251, TRUE

                                 281, TRUE

                                 311, TRUE

                                 401, TRUE

                                 431, TRUE

                                 461, TRUE

                                 491, TRUE

                                 521, TRUE

                                 641, TRUE

                                 701, TRUE

                                 761, TRUE

                                 821, TRUE

                                 881, TRUE

                                 13, TRUE

                                 43, TRUE

                                 73, TRUE

                                 103, TRUE

                                 163, TRUE

                                 193, TRUE

                                 223, TRUE

                                 283, TRUE

                                 313, TRUE

                                 373, TRUE

                                 433, TRUE

                                 463, TRUE

                                 523, TRUE

                                 613, TRUE

                                 643, TRUE

                                 673, TRUE

                                 733, TRUE

                                 823, TRUE

                                 853, TRUE

                                 883, TRUE

                                 17, TRUE

                                 47, TRUE

                                 107, TRUE

                                 137, TRUE

                                 167, TRUE

                                 197, TRUE

                                 227, TRUE

                                 257, TRUE

                                 317, TRUE

                                 347, TRUE

                                 467, TRUE

                                 557, TRUE

                                 587, TRUE

                                 617, TRUE

                                 647, TRUE

                                 677, TRUE

                                 797, TRUE

                                 827, TRUE

                                 857, TRUE

                                 887, TRUE

                                 19, TRUE

                                 79, TRUE

                                 109, TRUE

                                 139, TRUE

                                 199, TRUE

                                 229, TRUE

                                 349, TRUE

                                 379, TRUE

                                 409, TRUE

                                 439, TRUE

                                 499, TRUE

                                 619, TRUE

                                 709, TRUE

                                 739, TRUE

                                 769, TRUE

                                 829, TRUE

                                 859, TRUE

                                 23, TRUE

                                 53, TRUE

                                 83, TRUE

                                 113, TRUE

                                 173, TRUE

                                 233, TRUE

                                 263, TRUE

                                 293, TRUE

                                 353, TRUE

                                 383, TRUE

                                 443, TRUE

                                 503, TRUE

                                 563, TRUE

                                 593, TRUE

                                 653, TRUE

                                 683, TRUE

                                 743, TRUE

                                 773, TRUE

                                 863, TRUE

                                 29, TRUE

                                 59, TRUE

                                 89, TRUE

                                 149, TRUE

                                 179, TRUE

                                 239, TRUE

                                 269, TRUE

                                 359, TRUE

                                 389, TRUE

                                 419, TRUE

                                 449, TRUE

                                 479, TRUE

                                 509, TRUE

                                 569, TRUE

                                 599, TRUE

                                 659, TRUE

                                 719, TRUE

                                 809, TRUE

                                 839, TRUE