|
Development of Algorithmic Constructions |
15:59:03
| | | 29.Mar 2024
|
|
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:
| 1 | | 3 | | 5 | | 7 | | 9 | | 11 | | 13 | | 15 | | 17 | | 19 | | 21 | | 23 | | 25 | | 27 | | 29 |
| 31 | | 33 | | 35 | | 37 | | 39 | | 41 | | 43 | | 45 | | 47 | | 49 | | 51 | | 53 | | 55 | | 57 | | 59 |
| 61 | | 63 | | 65 | | 67 | | 69 | | 71 | | 73 | | 75 | | 77 | | 79 | | 81 | | 83 | | 85 | | 87 | | 89 |
| 91 | | 93 | | 95 | | 97 | | 99 | | 101 | | 103 | | 105 | | 107 | | 109 | | 111 | | 113 | | 115 | | 117 | | 119 |
| 121 | | 123 | | 125 | | 127 | | 129 | | 131 | | 133 | | 135 | | 137 | | 139 | | 141 | | 143 | | 145 | | 147 | | 149 |
| 151 | | 153 | | 155 | | 157 | | 159 | | 161 | | 163 | | 165 | | 167 | | 169 | | 171 | | 173 | | 175 | | 177 | | 179 |
| 181 | | 183 | | 185 | | 187 | | 189 | | 191 | | 193 | | 195 | | 197 | | 199 | | 201 | | 203 | | 205 | | 207 | | 209 |
| 211 | | 213 | | 215 | | 217 | | 219 | | 221 | | 223 | | 225 | | 227 | | 229 | | 231 | | 233 | | 235 | | 237 | | 239 |
| 241 | | 243 | | 245 | | 247 | | 249 | | 251 | | 253 | | 255 | | 257 | | 259 | | 261 | | 263 | | 265 | | 267 | | 269 |
| 271 | | 273 | | 275 | | 277 | | 279 | | 281 | | 283 | | 285 | | 287 | | 289 | | 291 | | 293 | | 295 | | 297 | | 299 |
| 301 | | 303 | | 305 | | 307 | | 309 | | 311 | | 313 | | 315 | | 317 | | 319 | | 321 | | 323 | | 325 | | 327 | | 329 |
| 331 | | 333 | | 335 | | 337 | | 339 | | 341 | | 343 | | 345 | | 347 | | 349 | | 351 | | 353 | | 355 | | 357 | | 359 |
| 361 | | 363 | | 365 | | 367 | | 369 | | 371 | | 373 | | 375 | | 377 | | 379 | | 381 | | 383 | | 385 | | 387 | | 389 |
| 391 | | 393 | | 395 | | 397 | | 399 | | 401 | | 403 | | 405 | | 407 | | 409 | | 411 | | 413 | | 415 | | 417 | | 419 |
| 421 | | 423 | | 425 | | 427 | | 429 | | 431 | | 433 | | 435 | | 437 | | 439 | | 441 | | 443 | | 445 | | 447 | | 449 |
| 451 | | 453 | | 455 | | 457 | | 459 | | 461 | | 463 | | 465 | | 467 | | 469 | | 471 | | 473 | | 475 | | 477 | | 479 |
| 481 | | 483 | | 485 | | 487 | | 489 | | 491 | | 493 | | 495 | | 497 | | 499 | | 501 | | 503 | | 505 | | 507 | | 509 |
| 511 | | 513 | | 515 | | 517 | | 519 | | 521 | | 523 | | 525 | | 527 | | 529 | | 531 | | 533 | | 535 | | 537 | | 539 |
| 541 | | 543 | | 545 | | 547 | | 549 | | 551 | | 553 | | 555 | | 557 | | 559 | | 561 | | 563 | | 565 | | 567 | | 569 |
| 571 | | 573 | | 575 | | 577 | | 579 | | 581 | | 583 | | 585 | | 587 | | 589 | | 591 | | 593 | | 595 | | 597 | | 599 |
| 601 | | 603 | | 605 | | 607 | | 609 | | 611 | | 613 | | 615 | | 617 | | 619 | | 621 | | 623 | | 625 | | 627 | | 629 |
| 631 | | 633 | | 635 | | 637 | | 639 | | 641 | | 643 | | 645 | | 647 | | 649 | | 651 | | 653 | | 655 | | 657 | | 659 |
| 661 | | 663 | | 665 | | 667 | | 669 | | 671 | | 673 | | 675 | | 677 | | 679 | | 681 | | 683 | | 685 | | 687 | | 689 |
| 691 | | 693 | | 695 | | 697 | | 699 | | 701 | | 703 | | 705 | | 707 | | 709 | | 711 | | 713 | | 715 | | 717 | | 719 |
| 721 | | 723 | | 725 | | 727 | | 729 | | 731 | | 733 | | 735 | | 737 | | 739 | | 741 | | 743 | | 745 | | 747 | | 749 |
| 751 | | 753 | | 755 | | 757 | | 759 | | 761 | | 763 | | 765 | | 767 | | 769 | | 771 | | 773 | | 775 | | 777 | | 779 |
| 781 | | 783 | | 785 | | 787 | | 789 | | 791 | | 793 | | 795 | | 797 | | 799 | | 801 | | 803 | | 805 | | 807 | | 809 |
| 811 | | 813 | | 815 | | 817 | | 819 | | 821 | | 823 | | 825 | | 827 | | 829 | | 831 | | 833 | | 835 | | 837 | | 839 |
| 841 | | 843 | | 845 | | 847 | | 849 | | 851 | | 853 | | 855 | | 857 | | 859 | | 861 | | 863 | | 865 | | 867 | | 869 |
| 871 | | 873 | | 875 | | 877 | | 879 | | 881 | | 883 | | 885 | | 887 | | 889 | | 891 | | 893 | | 895 | | 897 | | 899 |
Numbers % 11=0 are green:
| 1 | | 3 | | 5 | | 7 | | 9 | | 11 | | 13 | | 15 | | 17 | | 19 | | 21 | | 23 | | 25 | | 27 | | 29 |
| 31 | | 33 | | 35 | | 37 | | 39 | | 41 | | 43 | | 45 | | 47 | | 49 | | 51 | | 53 | | 55 | | 57 | | 59 |
| 61 | | 63 | | 65 | | 67 | | 69 | | 71 | | 73 | | 75 | | 77 | | 79 | | 81 | | 83 | | 85 | | 87 | | 89 |
| 91 | | 93 | | 95 | | 97 | | 99 | | 101 | | 103 | | 105 | | 107 | | 109 | | 111 | | 113 | | 115 | | 117 | | 119 |
| 121 | | 123 | | 125 | | 127 | | 129 | | 131 | | 133 | | 135 | | 137 | | 139 | | 141 | | 143 | | 145 | | 147 | | 149 |
| 151 | | 153 | | 155 | | 157 | | 159 | | 161 | | 163 | | 165 | | 167 | | 169 | | 171 | | 173 | | 175 | | 177 | | 179 |
| 181 | | 183 | | 185 | | 187 | | 189 | | 191 | | 193 | | 195 | | 197 | | 199 | | 201 | | 203 | | 205 | | 207 | | 209 |
| 211 | | 213 | | 215 | | 217 | | 219 | | 221 | | 223 | | 225 | | 227 | | 229 | | 231 | | 233 | | 235 | | 237 | | 239 |
| 241 | | 243 | | 245 | | 247 | | 249 | | 251 | | 253 | | 255 | | 257 | | 259 | | 261 | | 263 | | 265 | | 267 | | 269 |
| 271 | | 273 | | 275 | | 277 | | 279 | | 281 | | 283 | | 285 | | 287 | | 289 | | 291 | | 293 | | 295 | | 297 | | 299 |
| 301 | | 303 | | 305 | | 307 | | 309 | | 311 | | 313 | | 315 | | 317 | | 319 | | 321 | | 323 | | 325 | | 327 | | 329 |
| 331 | | 333 | | 335 | | 337 | | 339 | | 341 | | 343 | | 345 | | 347 | | 349 | | 351 | | 353 | | 355 | | 357 | | 359 |
| 361 | | 363 | | 365 | | 367 | | 369 | | 371 | | 373 | | 375 | | 377 | | 379 | | 381 | | 383 | | 385 | | 387 | | 389 |
| 391 | | 393 | | 395 | | 397 | | 399 | | 401 | | 403 | | 405 | | 407 | | 409 | | 411 | | 413 | | 415 | | 417 | | 419 |
| 421 | | 423 | | 425 | | 427 | | 429 | | 431 | | 433 | | 435 | | 437 | | 439 | | 441 | | 443 | | 445 | | 447 | | 449 |
| 451 | | 453 | | 455 | | 457 | | 459 | | 461 | | 463 | | 465 | | 467 | | 469 | | 471 | | 473 | | 475 | | 477 | | 479 |
| 481 | | 483 | | 485 | | 487 | | 489 | | 491 | | 493 | | 495 | | 497 | | 499 | | 501 | | 503 | | 505 | | 507 | | 509 |
| 511 | | 513 | | 515 | | 517 | | 519 | | 521 | | 523 | | 525 | | 527 | | 529 | | 531 | | 533 | | 535 | | 537 | | 539 |
| 541 | | 543 | | 545 | | 547 | | 549 | | 551 | | 553 | | 555 | | 557 | | 559 | | 561 | | 563 | | 565 | | 567 | | 569 |
| 571 | | 573 | | 575 | | 577 | | 579 | | 581 | | 583 | | 585 | | 587 | | 589 | | 591 | | 593 | | 595 | | 597 | | 599 |
| 601 | | 603 | | 605 | | 607 | | 609 | | 611 | | 613 | | 615 | | 617 | | 619 | | 621 | | 623 | | 625 | | 627 | | 629 |
| 631 | | 633 | | 635 | | 637 | | 639 | | 641 | | 643 | | 645 | | 647 | | 649 | | 651 | | 653 | | 655 | | 657 | | 659 |
| 661 | | 663 | | 665 | | 667 | | 669 | | 671 | | 673 | | 675 | | 677 | | 679 | | 681 | | 683 | | 685 | | 687 | | 689 |
| 691 | | 693 | | 695 | | 697 | | 699 | | 701 | | 703 | | 705 | | 707 | | 709 | | 711 | | 713 | | 715 | | 717 | | 719 |
| 721 | | 723 | | 725 | | 727 | | 729 | | 731 | | 733 | | 735 | | 737 | | 739 | | 741 | | 743 | | 745 | | 747 | | 749 |
| 751 | | 753 | | 755 | | 757 | | 759 | | 761 | | 763 | | 765 | | 767 | | 769 | | 771 | | 773 | | 775 | | 777 | | 779 |
| 781 | | 783 | | 785 | | 787 | | 789 | | 791 | | 793 | | 795 | | 797 | | 799 | | 801 | | 803 | | 805 | | 807 | | 809 |
| 811 | | 813 | | 815 | | 817 | | 819 | | 821 | | 823 | | 825 | | 827 | | 829 | | 831 | | 833 | | 835 | | 837 | | 839 |
| 841 | | 843 | | 845 | | 847 | | 849 | | 851 | | 853 | | 855 | | 857 | | 859 | | 861 | | 863 | | 865 | | 867 | | 869 |
| 871 | | 873 | | 875 | | 877 | | 879 | | 881 | | 883 | | 885 | | 887 | | 889 | | 891 | | 893 | | 895 | | 897 | | 899 |
Numbers % 13=0 are green:
| 1 | | 3 | | 5 | | 7 | | 9 | | 11 | | 13 | | 15 | | 17 | | 19 | | 21 | | 23 | | 25 | | 27 | | 29 |
| 31 | | 33 | | 35 | | 37 | | 39 | | 41 | | 43 | | 45 | | 47 | | 49 | | 51 | | 53 | | 55 | | 57 | | 59 |
| 61 | | 63 | | 65 | | 67 | | 69 | | 71 | | 73 | | 75 | | 77 | | 79 | | 81 | | 83 | | 85 | | 87 | | 89 |
| 91 | | 93 | | 95 | | 97 | | 99 | | 101 | | 103 | | 105 | | 107 | | 109 | | 111 | | 113 | | 115 | | 117 | | 119 |
| 121 | | 123 | | 125 | | 127 | | 129 | | 131 | | 133 | | 135 | | 137 | | 139 | | 141 | | 143 | | 145 | | 147 | | 149 |
| 151 | | 153 | | 155 | | 157 | | 159 | | 161 | | 163 | | 165 | | 167 | | 169 | | 171 | | 173 | | 175 | | 177 | | 179 |
| 181 | | 183 | | 185 | | 187 | | 189 | | 191 | | 193 | | 195 | | 197 | | 199 | | 201 | | 203 | | 205 | | 207 | | 209 |
| 211 | | 213 | | 215 | | 217 | | 219 | | 221 | | 223 | | 225 | | 227 | | 229 | | 231 | | 233 | | 235 | | 237 | | 239 |
| 241 | | 243 | | 245 | | 247 | | 249 | | 251 | | 253 | | 255 | | 257 | | 259 | | 261 | | 263 | | 265 | | 267 | | 269 |
| 271 | | 273 | | 275 | | 277 | | 279 | | 281 | | 283 | | 285 | | 287 | | 289 | | 291 | | 293 | | 295 | | 297 | | 299 |
| 301 | | 303 | | 305 | | 307 | | 309 | | 311 | | 313 | | 315 | | 317 | | 319 | | 321 | | 323 | | 325 | | 327 | | 329 |
| 331 | | 333 | | 335 | | 337 | | 339 | | 341 | | 343 | | 345 | | 347 | | 349 | | 351 | | 353 | | 355 | | 357 | | 359 |
| 361 | | 363 | | 365 | | 367 | | 369 | | 371 | | 373 | | 375 | | 377 | | 379 | | 381 | | 383 | | 385 | | 387 | | 389 |
| 391 | | 393 | | 395 | | 397 | | 399 | | 401 | | 403 | | 405 | | 407 | | 409 | | 411 | | 413 | | 415 | | 417 | | 419 |
| 421 | | 423 | | 425 | | 427 | | 429 | | 431 | | 433 | | 435 | | 437 | | 439 | | 441 | | 443 | | 445 | | 447 | | 449 |
| 451 | | 453 | | 455 | | 457 | | 459 | | 461 | | 463 | | 465 | | 467 | | 469 | | 471 | | 473 | | 475 | | 477 | | 479 |
| 481 | | 483 | | 485 | | 487 | | 489 | | 491 | | 493 | | 495 | | 497 | | 499 | | 501 | | 503 | | 505 | | 507 | | 509 |
| 511 | | 513 | | 515 | | 517 | | 519 | | 521 | | 523 | | 525 | | 527 | | 529 | | 531 | | 533 | | 535 | | 537 | | 539 |
| 541 | | 543 | | 545 | | 547 | | 549 | | 551 | | 553 | | 555 | | 557 | | 559 | | 561 | | 563 | | 565 | | 567 | | 569 |
| 571 | | 573 | | 575 | | 577 | | 579 | | 581 | | 583 | | 585 | | 587 | | 589 | | 591 | | 593 | | 595 | | 597 | | 599 |
| 601 | | 603 | | 605 | | 607 | | 609 | | 611 | | 613 | | 615 | | 617 | | 619 | | 621 | | 623 | | 625 | | 627 | | 629 |
| 631 | | 633 | | 635 | | 637 | | 639 | | 641 | | 643 | | 645 | | 647 | | 649 | | 651 | | 653 | | 655 | | 657 | | 659 |
| 661 | | 663 | | 665 | | 667 | | 669 | | 671 | | 673 | | 675 | | 677 | | 679 | | 681 | | 683 | | 685 | | 687 | | 689 |
| 691 | | 693 | | 695 | | 697 | | 699 | | 701 | | 703 | | 705 | | 707 | | 709 | | 711 | | 713 | | 715 | | 717 | | 719 |
| 721 | | 723 | | 725 | | 727 | | 729 | | 731 | | 733 | | 735 | | 737 | | 739 | | 741 | | 743 | | 745 | | 747 | | 749 |
| 751 | | 753 | | 755 | | 757 | | 759 | | 761 | | 763 | | 765 | | 767 | | 769 | | 771 | | 773 | | 775 | | 777 | | 779 |
| 781 | | 783 | | 785 | | 787 | | 789 | | 791 | | 793 | | 795 | | 797 | | 799 | | 801 | | 803 | | 805 | | 807 | | 809 |
| 811 | | 813 | | 815 | | 817 | | 819 | | 821 | | 823 | | 825 | | 827 | | 829 | | 831 | | 833 | | 835 | | 837 | | 839 |
| 841 | | 843 | | 845 | | 847 | | 849 | | 851 | | 853 | | 855 | | 857 | | 859 | | 861 | | 863 | | 865 | | 867 | | 869 |
| 871 | | 873 | | 875 | | 877 | | 879 | | 881 | | 883 | | 885 | | 887 | | 889 | | 891 | | 893 | | 895 | | 897 | | 899 |
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:
- m:=30;
p:={7,11,13,17,19,23,29};
for i from 1 to nops (p) do
p_inv:=p[i]^(-1) mod m;
p_start[i]:=(p[i]*p_inv-1)/m;
// p_offset[i]:=(p_start[i]*3)-p_start[i] mod p[i];
p_offset[i]:=2*p_start[i] mod p[i];
end_for;
for j from 1 to m step 2 do
if gcd (j, m)=1 then
// Preset coloum with 0
for i from 0 to m-1 do
liste[i]:=0;
end_for;
// Sieving
for i from 1 to nops (p) do
start:=p_start[i];
while start<m do
liste[start]:=1;
start:=start+p[i]
end_while;
end_for;
// Result
for i from 0 to m-1 do
if liste [i]=0 then
print (i*m+j, isprime (i*m+j));
end_if;
end_for;
end_if;
// Calculation of p_start for the next coloumn
for i from 1 to nops (p) do
p_start[i]:=p_start[i]+p_offset[i];
if p_start[i]>p[i] then
p_start[i]:=p_start[i]-p[i];
end_if;
end_for;
end_for;
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