mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Need an assessment and help regarding prime numbers. (https://www.mersenneforum.org/showthread.php?t=27466)

 TimoKinnunen 2022-01-05 13:24

Need an assessment and help regarding prime numbers.

I made an algorithm (2000 primes per minute) that without dividing (see example below) produces all primes of 2,3,5,7,... I think it is revolutionary.

But I don't know and need your expertise here. If you say that technique already exists, I have already been remedied.

Have you heard of an algorithm that produces prime numbers without the usual test with "a % b == 0"?
Thank you if you answered that question. Of course, I haven't found anything on the net.

Is it possible to become a Doctor in the subject? It's fast because the answer already exists!

// //calculate primenumbers the old way
// {
// {
// {
// break;
// }
// }
// }

 retina 2022-01-05 13:30

[QUOTE=TimoKinnunen;597190]... without dividing (see example below) ...
...[/QUOTE][b]%[/b] is just a division in disguise. So your code does use division.

Your code does what is known as trial factoring, TF for short. It isn't revolutionary.

 Uncwilly 2022-01-05 14:31

2000 primes per minute in the lower realms does not sound fast.

 axn 2022-01-05 14:39

Well... post your algorithm. Don't post "old way". We know old way. We know more "old ways" than you have heard of. Just post your algorithm and we'll tell you if its already known / good / bad.

 kruoli 2022-01-05 14:45

[CODE]private static int Gcd(int a, int b)
{
while (a != b)
{
if (a > b)
{
a -= b;
}
else
{
b -= a;
}
}
return a;
}

var primes = new List<int>();
for (int i = 3; i < limit; i += 2)
{
foreach (int prime in primes)
{
if (Gcd(prime, i) > 1)
{
goto not_prime;
}
}
not_prime: ;
}[/CODE]

This is without division, multiplication and modulo. I bet it is faster than 2000 primes per minute [SPOILER]up to a limit[/SPOILER].

 kriesel 2022-01-05 18:44

Welcome to GIMPS (assuming you're here in good faith).[QUOTE=TimoKinnunen;597190]I made an algorithm (2000 primes per minute) that without dividing (see example below) produces all primes of 2,3,5,7,... I think it is revolutionary.[/QUOTE]What's revolutionary? Post your source. Document your hardware, software, and operands range for which 2000 primes/minute was achieved.
Show us in detail how what you have done is superior in what respect to any or all of the code examples at
[URL="http://rosettacode.org/wiki/Primality_by_Wilson%27s_theorem"]http://rosettacode.org/wiki/Primality_by_Wilson%27s_theorem[/URL] and [URL]http://rosettacode.org/wiki/Primality_by_trial_division[/URL]
[spoiler]If I recall correctly, 2000 very small primes/minute was unremarkable for personal computers of 40 years ago doing simple sieving.[/spoiler]

 kriesel 2022-01-06 01:23

The old way seems deliberately constructed to be inefficient. It's perhaps asking a lot of an optimizing compiler to undo that.

//calculate prime numbers the old way
{
break;
}
}
} [/CODE]int.Parse is string to int conversion. Repeatedly on the same operand. Inside a for loop. That's properly done once outside the loop.
i increments by one, testing for factors of 2,3,4,5,6,7, ..., number being tested.
Not odds only with the special case of 2 handled separately, not using previously sieved primes only, not using upper limit of sqrt(number under test), not using wheel, etc etc etc.

Let's see, 2000 primes/minute ~33.3/second from the OP.

I forgot to include Sieve of Eratosthenes earlier.
[URL]http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Chapel[/URL]
The Chapel output corresponds to ~383,080,366.65 primes/minute.
[CODE]The first 25 primes are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Count of primes to a million is: 78498.
Found 50847534 primes up to 1,000,000,000 in 7964.05 milliseconds.[/CODE]The alternate odds-only bit-packed version corresponds to 12,686. primes per MILLISECOND.
Multithreaded Chapel 128.279 msec, ~396. primes/ MICROsecond.

The Fortran result 219 msec for up to a billion on Intel Skylake i5-6500 CPU at 3.2 GHz multithreaded with four cores, corresponds to ~232,180,520 primes/sec.
Plus there's an estimated near-fourfold and a near-double optimization untested.
[URL]http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Fortran[/URL]
where it's noted to then get adequate timing, a range to 10 billion is more appropriate than 1 billion. That would put multithreaded Fortran in the gigaprimes/sec range.

Faster way with Haskell: 1.085 seconds, corresponding to 46,864,087./second on Sky Lake i5-2500 CPU @ 3.6 GHz (turbo boost for single threaded)

Single threaded NIM up to a billion in 0.793 sec, with untested further near-four-fold and two-fold optimizations, & multithreading unused.

And all the preceding is without getting into the superior TF parallelism performance available on GPUs.

 TimoKinnunen 2022-01-17 16:41

Hunting prime numbers with TimoEratosthenes algorithm

Inventor of algorithm and author: Timo Kinnunen born 06/30/1956.
Subject: Programming, mathematics, prime number.
Date: 01/15/2022.
Algorithm was born at 12/28/2021 in Finland.
Introduction
What I know this is first time this kind of algorithm is presented by anybody to public. Traversing x-axis will give prime number candidates and decision is made whether it is a prime number or not using Erathostenes sieve (“knock out” those prime number candidates that can’t be prime numbers). No division is needed. Biggest known Mersenne prime number has 24 million digits. With a database table having three columns (Id, PrimeNumber, ForwardX) where PrimeNumber column and ForwardX column have capacity of 24 million characters, it is possible to bypass biggest known prime number in acceptable time with a powerful super-computer. One known prime number took 14 years to compute. TimoEratosthenes algorithm needs to know as starting point that 3 is prime number. This is enough to reveal all of prime numbers! The numbers have it. The numbers have it. Look at x-axis! Traverse the x-axis!
Meaningful cryptography needs prime numbers with 400 digits. Eratosthenes sieve the old way can produce prime numbers up to 8 digits length on home computer. The technique is wrong, and computer’s resources are limited. I recommend TimoEratosthenes algorithm instead when computer’s resources are not limited.
Method
Showing Eratosthenes sieve as a program.
Explaining TimoEratosthes algorithm with guidelines to understanding.
Showing TimoEratosthenes algorithm as program.
Conclusion.
Programming environment
All programs are written in C# using Microsoft Visual Studio 2022 and can therefore be reproduced and studied.

Eratosthenes sieve the old way
Greek Eratosthenes lived around 240 B.C. And hunting primes has gone on for about 2460 years among mathematicians.
An example of division with modulus (%) when hunting prime numbers is below.
This is the old way. When size of primeNumberCandidate number grows it takes more divisions to decide if primeNumberCandidate is prime number.
[CODE]using System;

namespace OldEratosthenes
{
internal class Program
{
static void Main(string[] args)
{

int counter = 0;

while (true)
{
for (int divisor = 2; divisor <= primeNumberCandidate / 2; divisor++)
{
if (primeNumberCandidate % divisor == 0)
{
break;
}
}

{
continue;
}

counter++;
if (counter % 1000 == 0)
{
Console.Clear();
}
}
}
}
}
Hunting prime numbers with TimoEratosthenes algorithm
There has not been a clear understanding of where prime numbers appear on the line y=2*x+1. Focus has been to find prime numbers among prime numbers. And I think that forest is not visible because of all trees. Another approach is shown here.
Think of x-axis of natural, positive numbers greater than zero and corresponding y=2*x+1 value as prime number candidate. Use Eratosthenes sieve to decide if prime number candidate is prime number.
Knowing two first prime numbers 2 and 3 is enough. The numbers have it! Or knowing 3 as prime number is enough to calculate rest of prime numbers! The numbers have it!
Considering natural, positive numbers greater than zero and a line y=2*x+1 then all prime numbers reside on the line except for two (2). Two is a special case and don’t fit on line y=2*x+1.
Traversing x-axis from 1 to 2 to 3 and so on will reveal the magic prime numbers by “knocking out” prime number candidates and leaving prime numbers!
We have database table (or collection) with columns Id, PrimeNumber and ForwardX at hand.
2 is prime number.
Let x=1.
Prime number candidate that corresponds to x=1 is 2*1+1=3. And forwardx is (3*3 -1)/2=4 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=4 it is “knocked out”.
Is prime number candidate 3 prime number? Let us find out. Look through all previous records in database table for 1==ForwardX. Database table contains 1 record and no records match query 1==ForwardX.
3 is therefore prime number.
We know that when x=4 prime number candidate is 2*4+1=9 and cannot be prime number.
Let x=2.
Prime number candidate that corresponds to x=2 is 2*2+1=5. And forwardx is (5*5 -1)/2=12 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=12 it is “knocked out”.
Is prime number candidate 5 prime number? Let us find out. Look through all previous records in database table for 2==ForwardX. Database table contains 2 records and no records match query 2==ForwardX.
5 is therefore prime number.
We know that when x=12 prime number candidate is 2*12+1=25 and cannot be prime number.
Let x=3.
Prime number candidate that corresponds to x=3 is 2*3+1=7. And forwardx is (7*7 -1)/2=24 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=24 it is “knocked out”.
Is prime number candidate 7 prime number? Let us find out. Look through all previous records in database table for 3==ForwardX. Database table contains 3 records and no records match query 3==ForwardX.
7 is therefore prime number.
We know that when x=24 prime number candidate is 2*24+1=49 and cannot be prime number.
Let x=4.
Prime number candidate that corresponds to x=4 is 2*4+1=9. And forwardx is (9*9 -1)/2=40 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=40 it is “knocked out”.
Is prime number candidate 9 prime number? Let us find out. Look through all previous records in database table for 4==ForwardX. Database table contains 4 records and one record match query 4==ForwardX.
9 is therefore not prime number. It is “knocked out”.
For future queries edit record so that ForwardX=PrimeNumber+ForwardX. And save to database.
Let x=5.
Prime number candidate that corresponds to x=5 is 2*5+1=11. And forwardx is (11*11 -1)/2=60 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=60 it is “knocked out”.
Is prime number candidate 11 prime number? Let us find out. Look through all previous records in database table for 5==ForwardX. Database table contains 4 records and no records match query 5==ForwardX.
11 is therefore prime number.
We know that when x=60 prime number candidate is 2*60+1=121 and cannot be prime number.
Let x=6.
Prime number candidate that corresponds to x=6 is 2*6+1=13. And forwardx is (13*13 -1)/2=84 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=84 it is “knocked out”.
Is prime number candidate 13 prime number? Let us find out. Look through all previous records in database table for 6==ForwardX. Database table contains 5 records and no records match query 6==ForwardX.
13 is therefore prime number.
We know that when x=84 prime number candidate is 2*84+1=169 and cannot be prime number.
Let x=7.
Prime number candidate that corresponds to x=7 is 2*7+1=15. And forwardx is (15*15 -1)/2=224 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=224 it is “knocked out”.
Is prime number candidate 15 prime number? Let us find out. Look through all previous records in database table for 7==ForwardX. Database table contains 6 records and one record match query 7==ForwardX.
15 is therefore not prime number. It is “knocked out”.
For future queries edit record so that ForwardX=PrimeNumber+ForwardX. And save to database.

Let x=8.
Prime number candidate that corresponds to x=8 is 2*8+1=17. And forwardx is (17*17 -1)/2=144 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=144 it is “knocked out”.
Is prime number candidate 17 prime number? Let us find out. Look through all previous records in database table for 8==ForwardX. Database table contains 6 records and no records match query 8==ForwardX.
17 is therefore prime number.
We know that when x=144 prime number candidate is 2*144+1=289 and cannot be prime number.
Let x=9.
Prime number candidate that corresponds to x=9 is 2*9+1=19. And forwardx is (19*19 -1)/2=180 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=180 it is “knocked out”.
Is prime number candidate 19 prime number? Let us find out. Look through all previous records in database table for 9==ForwardX. Database table contains 7 records and no records match query 9==ForwardX.
19 is therefore prime number.
We know that when x=180 prime number candidate is 2*180+1=361 and cannot be prime number.
Let x=10.
Prime number candidate that corresponds to x=10 is 2*10+1=21. And forwardx is (21*21 -1)/2=220 meaning that according to Eratosthenes sieve that when we traverse on x-axis to value x=220 it is “knocked out”.
Is prime number candidate 21 prime number? Let us find out. Look through all previous records in database table for 10==ForwardX. Database table contains 8 records and one record match query 10==ForwardX.
21 is therefore not prime number. It is “knocked out”.
For future queries edit record so that ForwardX=PrimeNumber+ForwardX. And save to database.
And so on...

TimoEratosthenes algorithm is the new way

using System;
using System.Collections.Generic;
using System.Linq;

namespace TimoEratosthenesConsoleApp
{
internal class Program
{
static void Main(string[] args)
{
int id = 1;

int x = 0;

List<Prime> primesList = new List<Prime> { new Prime { Id = id++, PrimeNumber = primeNumberCandidate, ForwardX = x } }; //special case

int counter = 0;

while (true)
{
x++;

List<Prime> forwardXPrimesList = primesList.Where(p => p.ForwardX == x).ToList<Prime>();
foreach (Prime prime in forwardXPrimesList)
{
Prime existingPrime = primesList.FirstOrDefault(p => p.Id == prime.Id);
if (existingPrime != null)
{
}
}

{
continue;
}

primeNumberCandidate = 2 * x + 1;

#region show
Console.Clear();
foreach (var prime in primesList)
{
Console.WriteLine( prime );
}
#endregion show

counter++;
if (counter % 1000 == 0)
{
Console.Clear();
}
}
}
}

public class Prime
{
public int Id { get; set; }

public int PrimeNumber { get; set; }

public int ForwardX { get; set; }

public override string ToString()
{
}
}
}

[/CODE]

Conclusion
A new algorithm was introduced by Timo Kinnunen in this paper and explained to a degree so that reader can themselves reproduce and use it.
The numbers have it! Starting with prime number 3 and all prime numbers are revealed!
Eratosthenes sieve uses division and TimoEratosthenes algorithm not.
Saving data as strings in database table or collection makes it possible to produce big prime numbers. The limitation lies often in the chosen datatype i.e. int, uint, long, BigInteger and so on. These limitations are overridden using strings.
My hope is that next biggest prime number uses TimoEratosthenes algorithm and that mathematicians can find this algorithm useful to explain prime numbers. Today it is a jungle.
Is there hyper-computer somewhere with free time window to implement this algorithm?
That’s all folks! Thank you for reading.

 VBCurtis 2022-01-17 18:27

[QUOTE=TimoKinnunen;598184]
Eratosthenes sieve uses division [......] Thank you for reading.[/QUOTE]

It does? Where? When I teach it to children, I don't do any division.

Also, next time you post code use [code] tags[/code]

 Batalov 2022-01-17 23:11

[QUOTE=TimoKinnunen;598184]Hunting prime numbers with [B]Timo[/B]Eratosthenes algorithm

Inventor of algorithm and author: Timo Kinnunen born 06/30/1956.
...[/QUOTE]
I am aware of a lot of smart people that would stop reading after the first line here, above.

Reason: vanity self-naming usually correlates with lack of substance.

In fact, this old golden rule has not failed us here, today.

 jwaltos 2022-01-18 15:20

[QUOTE=Batalov;598243]I am aware of a lot of smart people that would stop reading after the first line here, above.

Reason: vanity self-naming usually correlates with lack of substance.

In fact, this old golden rule has not failed us here, today.[/QUOTE]

William Gosset..circumstances were different though.

If the original poster reads and appreciates "EWD1036.PDF" on this site: [url]https://www.cs.utexas.edu/users/EWD/index10xx.html[/url]
(as a start) then perhaps some better questions may occur to this person.

All times are UTC. The time now is 19:40.