Skip to search.

Breaking News Visit Yahoo! News for the latest.

×Close this window

primenumbers · Prime numbers and primality testing

The Yahoo! Groups Product Blog

Check it out!

Group Information

  • Members: 1089
  • Category: Number Theory
  • Founded: Dec 27, 2000
  • Language: English
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Hear how Yahoo! Groups has changed the lives of others. Take me there.

Messages

Advanced
Messages Help
Messages 24174 - 24203 of 25075   Oldest  |  < Older  |  Newer >  |  Newest
Messages: Show Message Summaries Sort by Date ^  
#24174 From: Peter Kosinar <goober@...>
Date: Wed Mar 21, 2012 4:29 pm
Subject: Re: [PrimeNumbers] Re: Fw: A new conjecture on primes
pkosinar
Send Email Send Email
 
> > CONJECTURE ON PRIMES (Z. W. Sun, March 17-18, 2012). For k=1,2,3,... let
> > P_k denote the product of the first k primes p_1,...,p_k.
> >
> >   (i) For n=1,2,3,... define w_1(n) as the least integer m>1 such that m
> > divides none of P_i-P_j with i,j distinct and not more than n. Then
> > w_1(n) is always a prime.
>
> Isn't it self evident that the first (least) integer which doesn't divide into
another integer, is a prime number? Or am I misunderstanding something here ...

Ignoring Sun's definition of P_i, if we set <P1, P2, P3> = <1, 3, 4>, the
corresponding value of w_1(3) would be equal to 4; not a prime. Thus,
there must be something special about his definition of P_i, which makes
the resulting ones primes [or his conjecture is false :-) ].

Peter

[Non-text portions of this message have been removed]

#24175 From: "jbrennen" <jfb@...>
Date: Wed Mar 21, 2012 4:49 pm
Subject: Re: Fw: A new conjecture on primes
jbrennen
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
>
> Isn't it self evident that the first (least) integer which doesn't divide into
another integer, is a prime number?  Or am I misunderstanding something here ...
>
>
> Mark
>

Hint: what is the least integer which does not divide 6?

It's evident that the least integer in question is a prime power, but it's not
necessarily a prime.

#24176 From: "Mark" <mark.underwood@...>
Date: Wed Mar 21, 2012 5:29 pm
Subject: Re: Fw: A new conjecture on primes
marku606
Send Email Send Email
 
True, true, a prime power, not simply a prime. Now I suppose the question is,
why hasn't there been a counterexample to Sun's conjectures. I'm guessing it is
just because prime powers are relatively scarce compared to the primes.

Mark



--- In primenumbers@yahoogroups.com, "jbrennen" <jfb@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@> wrote:
> >
> >
> > Isn't it self evident that the first (least) integer which doesn't divide
into another integer, is a prime number?  Or am I misunderstanding something
here ...
> >
> >
> > Mark
> >
>
> Hint: what is the least integer which does not divide 6?
>
> It's evident that the least integer in question is a prime power, but it's not
necessarily a prime.
>

#24177 From: "Mark" <mark.underwood@...>
Date: Wed Mar 21, 2012 5:54 pm
Subject: Re: Fw: A new conjecture on primes
marku606
Send Email Send Email
 
If I'm not mistaken Sun is saying that the least number to not divide, say, 11#
- 7#, is a prime. But the first number to not divide this is 8.

Mark




--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
>
>
>
> True, true, a prime power, not simply a prime. Now I suppose the question is,
why hasn't there been a counterexample to Sun's conjectures. I'm guessing it is
just because prime powers are relatively scarce compared to the primes.
>
> Mark
>
>
>
> --- In primenumbers@yahoogroups.com, "jbrennen" <jfb@> wrote:
> >
> > --- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@> wrote:
> > >
> > >
> > > Isn't it self evident that the first (least) integer which doesn't divide
into another integer, is a prime number?  Or am I misunderstanding something
here ...
> > >
> > >
> > > Mark
> > >
> >
> > Hint: what is the least integer which does not divide 6?
> >
> > It's evident that the least integer in question is a prime power, but it's
not necessarily a prime.
> >
>

#24178 From: Peter Kosinar <goober@...>
Date: Wed Mar 21, 2012 6:14 pm
Subject: Re: [PrimeNumbers] Re: Fw: A new conjecture on primes
pkosinar
Send Email Send Email
 
> If I'm not mistaken Sun is saying that the least number to not divide, say,
11# - 7#, is a prime. But the first number to not divide this is 8.
>
> Mark

Nope -- Sun claims that for any N, the first number which does not divide
ANY of the primorials A# - B# for A, B <= N, is a prime.

Peter

#24179 From: "Mark" <mark.underwood@...>
Date: Wed Mar 21, 2012 7:07 pm
Subject: Re: Fw: A new conjecture on primes
marku606
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Peter Kosinar <goober@...> wrote:
>
> > If I'm not mistaken Sun is saying that the least number to not divide, say,
11# - 7#, is a prime. But the first number to not divide this is 8.
> >
> > Mark
>
> Nope -- Sun claims that for any N, the first number which does not divide
> ANY of the primorials A# - B# for A, B <= N, is a prime.
>
> Peter
>

Ah, I see, thanks for the clarification. So as a counterexample we're looking
for a prime power (with exponent greater than one) which is the least number
that does not divide any combination of A# - B# for A,B up to a given n.  I
think I can see why that should be next to impossible.



> CONJECTURE ON PRIMES (Z. W. Sun, March 17-18, 2012). For k=1,2,3,... let
> P_k denote the product of the first k primes p_1,...,p_k.
>
>   (i) For n=1,2,3,... define w_1(n) as the least integer m>1 such that m
> divides none of P_i-P_j with i,j distinct and not more than n. Then
> w_1(n) is always a prime.

#24180 From: "Mark" <mark.underwood@...>
Date: Wed Mar 21, 2012 10:56 pm
Subject: Re: Fw: A new conjecture on primes
marku606
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
>
>
> --- In primenumbers@yahoogroups.com, Peter Kosinar <goober@> wrote:
> >
> > > If I'm not mistaken Sun is saying that the least number to not divide,
say, 11# - 7#, is a prime. But the first number to not divide this is 8.
> > >
> > > Mark
> >
> > Nope -- Sun claims that for any N, the first number which does not divide
> > ANY of the primorials A# - B# for A, B <= N, is a prime.
> >
> > Peter
> >
>
> Ah, I see, thanks for the clarification. So as a counterexample we're looking
for a prime power (with exponent greater than one) which is the least number
that does not divide any combination of A# - B# for A,B up to a given n.  I
think I can see why that should be next to impossible.
>

No, I'm wrong again.  The least number to not divide another number will indeed
be a prime power,  but I'm wrong to assume this would be true when applied to
more than one number.  The problem is more subtle and difficult than I supposed.


Mark



>
>
> > CONJECTURE ON PRIMES (Z. W. Sun, March 17-18, 2012). For k=1,2,3,... let
> > P_k denote the product of the first k primes p_1,...,p_k.
> >
> >   (i) For n=1,2,3,... define w_1(n) as the least integer m>1 such that m
> > divides none of P_i-P_j with i,j distinct and not more than n. Then
> > w_1(n) is always a prime.
>

#24181 From: Jack Brennen <jfb@...>
Date: Wed Mar 21, 2012 11:05 pm
Subject: Re: [PrimeNumbers] Re: Fw: A new conjecture on primes
jbrennen
Send Email Send Email
 
On 3/21/2012 3:56 PM, Mark wrote:
>
> No, I'm wrong again.  The least number to not divide another number
> will indeed be a prime power,  but I'm wrong to assume this would be
> true when applied to more than one number.  The problem is more
> subtle and difficult than I supposed.
>

As would be expected when coming from Zhi-Wei Sun:

    http://en.wikipedia.org/wiki/Sun_Zhiwei

If he presents it as a conjecture, you can be sure of two things...
It's very likely true, and will be very hard to prove.

#24182 From: "WarrenS" <warren.wds@...>
Date: Thu Mar 22, 2012 1:05 am
Subject: Re: Do the prime gaps have a limit distribution and what is it?
warren_d_smi...
Send Email Send Email
 
> Marek Wolf's Fig.1 in
> http://arxiv.org/pdf/1010.3945v1.pdf
> attempts to fit the data on maximal gaps
> from Thomas Nicely
> http://www.trnicely.net
> and Tomas Oliveira e Silva
> http://www.ieeta.pt/~tos/gaps.html
> and appears to do so quite nicely.

--Wolf's nonrigorous approximate formula is

(Max Prime Gap below x) = (x/pi(x)) * (2*ln(pi(x)) - ln(x) + c)

where c = ln(2) + sum(primes p>2) ln( 1 - 1/(p-1)^2 ) = 0.27787688...

It appears to work very well for the first 75 prime gap records.

But Wolf notes his formula conflicts with A.Granville who conjectures

(Max Prime Gap below x) >= 2*exp(-gamma) * ln(x)^2

for infinite set of cases, 2*exp(-gamma)=1.12292.

This Granville conjecture is unsupported by the evidence so far.

#24183 From: "djbroadhurst" <d.broadhurst@...>
Date: Thu Mar 22, 2012 1:59 am
Subject: Re: form of "Mills' constant"? [Puzzle 709]
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> As previously remarked, infinity is a long way away and we do well
> to avoid jumping to conclusions based on small numbers like my
> N = 647, or Warren's even smaller N = 274

Progress is, as expected, slowing down. Thus far, I have solved
Puzzle 709, where a 5045-digit probable prime, ending in
...2963978865589225213070090428982660368263, neatly stores
the 1,656,992 decimal digits of 709 smaller probable primes.
I think of such constructs as "portmanteau probable primes",
yet Warren might prefer his own name to be prefixed to them?

David

#24184 From: "WarrenS" <warren.wds@...>
Date: Thu Mar 22, 2012 5:23 am
Subject: Re: form of "Mills' constant"? [Puzzle 709]
warren_d_smi...
Send Email Send Email
 
> Progress is, as expected, slowing down. Thus far, I have solved
> Puzzle 709, where a 5045-digit probable prime, ending in
> ...2963978865589225213070090428982660368263, neatly stores
> the 1,656,992 decimal digits of 709 smaller probable primes.
> I think of such constructs as "portmanteau probable primes",
> yet Warren might prefer his own name to be prefixed to them?
> David

--
0. the amount of "data compression" is actually pretty good.  Roughly, we store
a set of primes whose summed total bitlength is N bits, in order sqrt(N) bits
of storage, via either stating the last prime in a finite sequence or stating
the "magic constant" to finite precision (either works and each
has about the same bit-size).
[Caveat: not proven to work forever unless certain conjectures assumed.]

Compare it with

1. Mills' original kind of prime generating formula.  This sucks in the sense
that
the total summed bitlength N for all the primes, is stored in order N bits.   In
my view, a "prime generating formula" ought to take much less space than just
listing the primes it generates! -- or it is pointless.

2. Storing all of the first N primes by encoding the gaps.
The total bit length of all those primes is order N*logN bits,
which by means of gap-based-compression is reduced to
order N*loglogN bits (or less perhaps as little as order N bits
is possible, but I doubt it).   This is a reduction, yes,  but a much tinier
reduction
than our prime-generating formula yields.

3. Storing all infinity primes by stating the "definition of the word 'prime'"
in a constant number of bits.  This is the ultimate in compression, but
the "decompression algorithm" i.e a prime-generator, is somewhat complicated.
Perhaps you consider it complicated enough that you are unwilling to regard this
as
a "formula" for generating primes?

Both (0) and (3) will decompress, i.e. generate primes, in near-linear time
(measured in terms of the output bitlength) and using optimal storage (of order
just that required
to store only the single largest among the output primes) albeit I think under
those
conditions (0) is somewhat faster than (3).   I.e. to generate primes using
optimal storage you could test successive integers using the AKS primality test
which I think would be asymptotically slower than the formula (0) method as
a function of the number of bits output, even though both are near-linear
runtime
so the comparison hinges on log factors in the runtimes...

#24185 From: "WarrenS" <warren.wds@...>
Date: Thu Mar 22, 2012 4:00 pm
Subject: Fast prime generators
warren_d_smi...
Send Email Send Email
 
To compute the first N primes...
Tomas Oliveira e Silva invented an excellent form of the Eratosthenes sieve
which he has
used to generate all primes below 10^(18.5).
This is one of the fastest, if not the fastest, prime generator in the world:
    http://www.ieeta.pt/~tos/software/prime_sieve.html

However, let us consider its deficiencies.  His algorithm to generate N primes
requires storage of order  sqrt(N/logN)*loglogN  bits.
The runtime is of order
N*logN*loglogN.   Many of the memory accesses are out-of-cache.

If we instead were to simply scan through integers testing them using a fast
primality
tester (there are various compromises between rigor and speed...) then the
memory
use would be negligible and we'd never leave the cache... but we'd need to work
harder for each prime.  I think the runtime in the same computational model
(where
an arithmetic op takes "1 step") would be
O(logN) arithmetic operations per prime tested [for a certain primality test
known to
be valid up to 2^64=1.84*10^19 combining one Lucas and one Fermat test]
for total runtime N*(logN)^2, or perhaps N*(logN)^2/loglogN  if we do a little
sieving to freduce the number of tests needed.   Note many ops now are division
and multiplication, whereas with OeS's code almost all ops were additive.

This runtime is a factor of order  (logN)/(loglogN)^K  times slower than
Oliveira e Silva's sieve for 1<=K<=2.   The question is whether this slowdown is
compensated for by the fact that we stay in cache and don't hog memory.

I claim my approach IS asymptotically much better reckoned in terms of "hardware
cost."
Analysis: with this approach we could go X times faster by using X processors
in parallel, whereas with Oliveira e Silva's approach we'd need to get X
processors
EACH WITH big memory, to get X-factor speedup.  The hardware cost
OeS's way would thus be of order   X*sqrt(N/logN)*loglogN
and my way would be (to get the same speed) of order
X*(logN)/(loglogN)^K.
My hardware cost for large N is tremendously cheaper than OeS's hardware cost.
Even if one felt forced to use a slower primality test to get rigor, then still
that only puts in some more log factors, so I still win huge.

[And the primality test I am suggesting would become rigorous even
for arbitrarily large numbers if
it were combined with a separate enumeration of pseudoprimes, which
could be done in a negligible amount of time compared to the prime enumeration
and also would have independent interest. Such an enumeration was already done
up to 2^64,
albeit it has not been independently confirmed,
which is why we know this primality test is valid up to 2^64.]

#24186 From: Luis Rodriguez <luiroto@...>
Date: Thu Mar 22, 2012 7:59 pm
Subject: Re: Do the prime gaps have a limit distribution and what is it?
luiroto
Send Email Send Email
 
By heuristic arguments I arrived to the simple  formula:
Mean Maximum Gap in the neighborhood of N , MMG(N) = [Ln (N) - Ln Ln(N)]^2
This formula represents very well  the mean superior boundary  of T.Oliveira's
cloud of points.
That is, the first occurence of a gap greater than its maximum predecessor is a
MMG.
Example:
N       =   2    4    6     8       14       20   .....   34 ....

MMG =  3    7    23   89     113     887 .....  1327....

Ludovicus


[Non-text portions of this message have been removed]

#24187 From: "WarrenS" <warren.wds@...>
Date: Thu Mar 22, 2012 11:54 pm
Subject: Re: Do the prime gaps have a limit distribution and what is it?
warren_d_smi...
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Luis Rodriguez <luiroto@...> wrote:
>
> By heuristic arguments I arrived to the simple  formula:
> Mean Maximum Gap in the neighborhood of N , MMG(N) = [Ln (N) - Ln Ln(N)]^2
> This formula represents very well  the mean superior boundary  of T.Oliveira's
cloud of points.

--your formula agrees with Marek Wolf's formula at both its dominant and
first subdominant term, as can be shown using claims in
    http://en.wikipedia.org/wiki/Prime-counting_function

#24188 From: Phil Carmody <thefatphil@...>
Date: Sun Mar 25, 2012 4:25 pm
Subject: Re: [PrimeNumbers] Fast prime generators
thefatphil
Send Email Send Email
 
--- On Thu, 3/22/12, WarrenS <warren.wds@...> wrote:
> To compute the first N primes...
> Tomas Oliveira e Silva invented an excellent form of the
> Eratosthenes sieve which he has
> used to generate all primes below 10^(18.5).
> This is one of the fastest, if not the fastest, prime
> generator in the world:
>    http://www.ieeta.pt/~tos/software/prime_sieve.html
>
> However, let us consider its deficiencies.  His
> algorithm to generate N primes
> requires storage of order  sqrt(N/logN)*loglogN 
> bits. The runtime is of order
> N*logN*loglogN.   Many of the memory accesses
> are out-of-cache.

To reduce the memory footprint to O(N^(1/3)), use Galway's brilliant
modification of the Sieve of Atkin.
  http://www.springerlink.com/content/jug31w3p60443l57/ et al.
Like Atkin's, this requires no table of primes. I'd love to see Bernstein
implement Galway's sieve...

Phil

#24189 From: Andrey Kulsha <Andrey_601@...>
Date: Sun Mar 25, 2012 4:43 pm
Subject: Re: [PrimeNumbers] Fast prime generators
andrey_601
Send Email Send Email
 
I doubt it will beat well-implemented Erato :-)

http://code.google.com/p/primesieve/
http://www.primefan.ru/stuff/pict/benchmark.gif

     Best regards,

     Andrey

#24190 From: Sebastian Martin Ruiz <s_m_ruiz@...>
Date: Sun Mar 25, 2012 5:27 pm
Subject: Twin primes equation
s_m_ruiz
Send Email Send Email
 
Hello all:

Let p and q INTEGERS 1<q<p.
 
Let:
 
F[p,q]=GCD[LCM[p+q,p-q],LCM[p-1,q+1]] -
(p+q)Mod[(p-1)!,p]Mod[(q-1)!,q]/(2(p-1)(q-1))
 
 F[p,q]=0 if and only if p and q are twin primes.   Except the case (p=11,
q=4)
 
 
Find other exception or prove that don’t exists.


Sincerely:

Sebastian Martin Ruiz

[Non-text portions of this message have been removed]

#24191 From: "WarrenS" <warren.wds@...>
Date: Sun Mar 25, 2012 6:37 pm
Subject: Re: Fast prime generators
warren_d_smi...
Send Email Send Email
 
--Galway document available for free:
http://www.math.uiuc.edu/~galway/SlidesETC/Draft-DissectedSieve-Slides.pdf

> To reduce the memory footprint to O(N^(1/3)), use Galway's brilliant
modification of the Sieve of Atkin.
>  http://www.springerlink.com/content/jug31w3p60443l57/ et al.
> Like Atkin's, this requires no table of primes. I'd love to see Bernstein
implement Galway's sieve...

--Thanks.
It looks to me like Galway's method is very promising.  It really seems to be
Voronoi's idea from early 1900s. But as Galway says it needs more development. 
However, my proposal still will beat it eventually according to my "hardware
cost" metric.
In the case of TOS's Eratosthenes sieve, the crossover point is plausibly
reachable -- but
only with a programmer willing to exploit appropriate hardware...
In the case of Galway's sieve, it plausibly is unfeasible to reach crossover
if we need all primes up to N; but if we only ask for the primes in the interval
[A,B] for large enough A and B, then it would be reachable.

#24192 From: "paulunderwooduk" <paulunderwood@...>
Date: Mon Mar 26, 2012 7:16 am
Subject: Re: Fast prime generators
paulunderwooduk
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Andrey Kulsha <Andrey_601@...> wrote:
>
>     I doubt it will beat well-implemented Erato :-)
>
> http://code.google.com/p/primesieve/
> http://www.primefan.ru/stuff/pict/benchmark.gif
>

Thanks for the link. I am now using it in a program of mine. This sieve is just
what I have been looking for -- being able to specify a range is very useful. I
hope Prof. Chris Caldwell will like this C++ code from:
http://primes.utm.edu/links/programs/sieves/Eratosthenes/
http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Paul

#24193 From: "Ben Buhrow" <bbuhrow@...>
Date: Mon Mar 26, 2012 2:11 pm
Subject: Re: Fast prime generators
nebworhub
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Andrey Kulsha <Andrey_601@...> wrote:
>
>     I doubt it will beat well-implemented Erato :-)
>
> http://code.google.com/p/primesieve/
> http://www.primefan.ru/stuff/pict/benchmark.gif
>
>     Best regards,
>
>     Andrey
>


And there are several such:

yafu-1.30 (http://sourceforge.net/projects/yafu/):

###### 101 % yafu "primes(0,10^10)" -threads 6
elapsed time = 1.0401

ans = 455052511

###### 104 % yafu "primes(0,10^11)" -threads 6
elapsed time = 5.8997

ans = 4118054813

###### 105 % yafu "primes(0,10^12)" -threads 6
elapsed time = 74.0429

ans = 37607912018

###### 106 yafu "primes(10^16,10^16+10^11)" -threads 6
elapsed time = 20.5100

ans = 2714336584


primesieve 3.0:

###### 98 % ../primesieve/primesieve-3.0/out/primesieve 1 10^10 -t6 -s32
START      = 1
STOP       = 10000000000
Sieve size = 32 Kilobytes
Threads    = 6
100%
Prime numbers : 455052511
Time elapsed  : 0.812076 sec

###### 99 % ../primesieve/primesieve-3.0/out/primesieve 1 10^11 -t6 -s32
START      = 1
STOP       = 100000000000
Sieve size = 32 Kilobytes
Threads    = 6
100%
Prime numbers : 4118054813
Time elapsed  : 7.26565 sec

###### 100 % ../primesieve/primesieve-3.0/out/primesieve 1 10^12 -t6 -s32
START      = 1
STOP       = 1000000000000
Sieve size = 32 Kilobytes
Threads    = 6
100%
Prime numbers : 37607912018
Time elapsed  : 92.8856 sec

###### 107 % ../primesieve/primesieve-3.0/out/primesieve 10^16 10^16+10^11 -t6
-s32
START      = 10000000000000000
STOP       = 10000100000000000
Sieve size = 32 Kilobytes
Threads    = 6
100%
Prime numbers : 2714336584
Time elapsed  : 21.6507 sec


Memory usage that goes as O(N^1/3) would be nice, tho.

- ben.

#24194 From: Flavio Mattos <flavio.mattos@...>
Date: Mon Mar 26, 2012 8:32 pm
Subject: Re: Fast prime generators
flavio_biker
Send Email Send Email
 
Hi!

Once more, I must apologize for my bad English.

I've published the first 2 billion prime number list at

http://www.primos.mat.br/indexen.html

page. I couldn't find a larger list available to download so I published
mine.

It was computed with a home-made not so fast prime generator.

As I said before, in order to learn Java language I've coded one prime
generator using only very basic Java language standard classes.

My version is not so fast because I don't want just to find prime numbers
inside computer memory, but also to print them down to a text file. The
Java io subsystem became the real bottleneck. The very standard segmented
Sieve of Eratosthenes implementation (with a little multi-thread help) has
enought power to suply primes for uninterrupted i/o.

Flavio Mattos


[Non-text portions of this message have been removed]

#24195 From: "paulunderwooduk" <paulunderwood@...>
Date: Mon Mar 26, 2012 9:34 pm
Subject: Re: Fast prime generators
paulunderwooduk
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Flavio Mattos <flavio.mattos@...> wrote:
>

>
> I've published the first 2 billion prime number list at
>
> http://www.primos.mat.br/indexen.html
>

Not to belittle your efforts too much, by the time I have navigated your site,
downloaded the zip files, unzipped them and read them from disk, I can use an
efficient program to calculate to 2*10^9 in about 1 second.
http://www.primefan.ru/stuff/pict/benchmark.gif

> I couldn't find a larger list available to download so I published
> mine.
>

PrimeGrid, when it was an embryo, calculated the first consecutive primes to a
huge level, filling up many DVDs. I can not find a link to them now.

Paul

#24196 From: "Ben Buhrow" <bbuhrow@...>
Date: Mon Mar 26, 2012 10:18 pm
Subject: Re: Fast prime generators
nebworhub
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...>
wrote:
>
>
>
> --- In primenumbers@yahoogroups.com, Flavio Mattos <flavio.mattos@> wrote:
> >
>
> >
> > I've published the first 2 billion prime number list at
> >
> > http://www.primos.mat.br/indexen.html
> >
>
> Not to belittle your efforts too much, by the time I have navigated your site,
downloaded the zip files, unzipped them and read them from disk, I can use an
efficient program to calculate to 2*10^9 in about 1 second.
> http://www.primefan.ru/stuff/pict/benchmark.gif
>

To be fair, it takes much longer to actually compute and print the primes in an
interval than just counting them (which is what primesieve does by default).

Computing and printing 2*10^9 primes took 6-threaded yafu 26 seconds.  Doing the
same with primesieve-3.0 took about 2 minutes.

If, for whatever reason, someone actually wanted a text file with ~98 million
primes listed in it :)

- ben.

#24197 From: Flavio Mattos <flavio.mattos@...>
Date: Mon Mar 26, 2012 10:27 pm
Subject: Re: Fast prime generators
flavio_biker
Send Email Send Email
 
It's ok Paul!

I'm doing just a free time programming exercise, and learning a lot in the
process. The classes I'm building will serve other purposes in the slow
world of Java.

I am not aiming at speed rigth now, and I down't believe any java program
can beat the fastest compiled C or C++ prime generators.

Thanks for the comments.

I wonder if posts like mine are inadequate to this list. If so, I will keep
reading and learning.

Thanks again

Flavio Mattos


[Non-text portions of this message have been removed]

#24198 From: Mark Rodenkirch <mgrogue@...>
Date: Mon Mar 26, 2012 10:47 pm
Subject: Re: [PrimeNumbers] Fast prime generators
mgrogue
Send Email Send Email
 
Since we're on the topic, has anyone tried to write a prime sieve that does most
of the work in the GPU?

-Mark

#24199 From: "djbroadhurst" <d.broadhurst@...>
Date: Tue Mar 27, 2012 12:11 am
Subject: Re: Fast prime generators
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"paulunderwooduk" <paulunderwood@...> wrote:

> PrimeGrid, when it was an embryo, calculated the first
> consecutive primes to a huge level, filling up many DVDs.
> I can not find a link to them now.

They try to keep quiet about that episode, these days. However
http://www.primegrid.com/forum_forum.php?id=19
still leaks some history on that "project" to print
24,480,641,557 primes on DVDs.

David

#24200 From: Jim White <mathimagics@...>
Date: Tue Mar 27, 2012 7:23 am
Subject: [PrimeNumbers] Fast prime generators
mathimagics
Send Email Send Email
 
I think Flavio's only to be encouraged in his learning process.
 
Perhaps one useful lesson is this - as CPU speeds keep doubling the same can not
be said of I/O operations. There probably was some time in the past when storing
precomputed primes in a file made sense - if the file could be randomly accessed
to fetch the k-th prime, this would be faster than computing the k-th prime on
the fly.
 
More importantly, the value of max(k) for which this would be efficient would be
relatively small.
 
But given the blistering speeds of CPU's today, coupled with smart E-sieve
algorithms, and the exceptionally high CPU/IO ratios we have now, I suspect that
the value of k for which a direct-access READ might make sense is so large that
the file would need to be simply enormous.
 
Speaking of ancient history, I see that "primos" apparently means primes in
Portuguese - I worked in R&D for a "super-mini" (remember them?) vendor back in
the 80's. The company was Prime Computer, and the operating system was PRIMOS.
 
Jim White

[Non-text portions of this message have been removed]

#24201 From: Flavio Mattos <flavio.mattos@...>
Date: Tue Mar 27, 2012 10:42 am
Subject: Re: [PrimeNumbers] Fast prime generators
flavio_biker
Send Email Send Email
 
Thanks for the nice words.

Yes, Primo, plural Primos is the portuguese version of Prime. :-)

This discussion was stimullating. I'll pursue betther performance from now
on.

Thanks.

2012/3/27 Jim White <mathimagics@...>

> I think Flavio's only to be encouraged in his learning process.
>
> Perhaps one useful lesson is this - as CPU speeds keep doubling the same
> can not be said of I/O operations. There probably was some time in the
> past when storing precomputed primes in a file made sense - if the file
> could be randomly accessed to fetch the k-th prime, this would be faster
> than computing the k-th prime on the fly.
>
> More importantly, the value of max(k) for which this would be efficient
> would be relatively small.
>
> But given the blistering speeds of CPU's today, coupled with smart E-sieve
> algorithms, and the exceptionally high CPU/IO ratios we have now, I suspect
> that the value of k for which a direct-access READ might make sense is so
> large that the file would need to be simply enormous.
>
> Speaking of ancient history, I see that "primos" apparently means primes
> in Portuguese - I worked in R&D for a "super-mini" (remember them?) vendor
> back in the 80's. The company was Prime Computer, and the operating system
> was PRIMOS.
>
> Jim White
>
>
>



--
"Toda boa dádiva e todo dom perfeito vêm do alto, descendo do Pai das
luzes, em quem não há mudança nem sombra de variação." (Tiago 1:17)"

http://flaviomattos.fotopages.com
http://maisumacurva.blogspot.com/


[Non-text portions of this message have been removed]

#24202 From: "bhelmes_1" <bhelmes@...>
Date: Tue Mar 27, 2012 8:00 pm
Subject: Re: Fast prime generators
bhelmes_1
Send Email Send Email
 
Hello Mark,

i wrote a prime sieve with Cuda on a Gpu Geforce 450 with 192 cores.
All work is done on the Gpu.

I get as result only the numbers of primes in arithmetic progressions.
The Programm needs approximately 1 month for counting all primes below 10^15

I am not sure if this is a good result, but i could give you the code,
if you want, it is quite nice and uses not the sieve of Eratosthenes,
but more a sieve of Ulam in some derivated form.

Does it make any sense to calculate the numbers of primes in arithmetic
progressions up to 10^15 ?

Nice greetings from the primes
Bernhard

#24203 From: "paulunderwooduk" <paulunderwood@...>
Date: Sun Apr 1, 2012 9:02 pm
Subject: Another variant - 3.X selfridge
paulunderwooduk
Send Email Send Email
 
Hi,

I have formulated another composite test variant:

Non-square N>5, with gcd(30,N)==1, is prime if and only if for any integer x:
gcd(x^3-x,N)==1 and
jacobiSymbol(D,N)==-1 and
jacobiSymbol(x+2,N)==-1
then
x^(N-1)==1 (mod N) (Fermat) and
(L^2-1)^(N+1)==-D (mod N, L^2-x*L+1)
where D=x^2-4.

I have a long list of such conjectures, all of which will be tested to some high
level, once my other projects are cleared,

Paul

Messages 24174 - 24203 of 25075   Oldest  |  < Older  |  Newer >  |  Newest
Add to My Yahoo!      XML What's This?

Copyright © 2010 Yahoo! Inc. All rights reserved.
Privacy Policy - Terms of Service - Guidelines NEW - Help