----- Original Message -----
From: "Bill Bouris" <leavemsg1@...>

[a^ (p-2)] is equiv. to [p - (p-1)/a] (mod p)

Interesting? or not?

------------------------------------------

It's trivial:

a^(p-1) = = 1
a^(p-2)*a = = 1
a^(p-2)*a = = p-p+1
a^(p-2)*a = = p-(p-1)
a^(p-2) = = [p-(p-1)]/a
a^(p-2) = = p/a-(p-1)/a

And we have that GCD(a,p)=1
p/a = = x (mod p)
a*x = = p = = 0 (mod p)
x = = 0 (mod p)
p/a = = 0 = = p (mod p).

So:
a^(p-2) = = p-(p-1)/a.

QED

Jose Brox

I've been running Prime95 with a smaller B1/B2 and a huge exponent
(M33554432).

I realized this morning that the box has been stuck on the same curve
for the last 18 hours, when it normally finishes a curve in 2 hours.
So I checked the Prime95 folder and found a results.txt file with the
following entry.

- - -
[Sat Jul 02 16:05:36 2005]
ECM found a factor in curve #11, stage #1
Sigma=4573583067221178, B1=2000, B2=200000.
- - -

The screen display shows that Prime95 has finished stage-1 and
appears to be initializing for stage-2. No mention of a factor on the
screen display and no mention in results.txt as to what the factor
supposably is. And Prime95 is still chewing up 100% of the CPU.

So thinking it may have been a glitch, I switched to another box with
more memory. I attempted to run the same identical curve with the
same B1/B2 and same sigma. Darned if it didn't go through the curve
without finding any factors.

Both boxes have the same lowm.txt and both boxes appear to have run
the same identical curve. Box-1 is still stuck (using 100% of the
CPU) and box-2 claims there was no factor.

Do I assume a glitch on box-1 and box-2 is correct? Or is there a
chance that box-2 didn't run an identical curve? Or is it time to
stick to smaller exponents since Prime95 sometimes seems to have
problems with very large factors when running ECM?

From: "j_m_berg" <j_m_berg@...>
>
> I've been running Prime95 with a smaller B1/B2 and a huge exponent
> (M33554432).
>
> I realized this morning that the box has been stuck on the same curve
> for the last 18 hours, when it normally finishes a curve in 2 hours.
> So I checked the Prime95 folder and found a results.txt file with the
> following entry.
>
> - - -
> [Sat Jul 02 16:05:36 2005]
> ECM found a factor in curve #11, stage #1
> Sigma=4573583067221178, B1=2000, B2=200000.

With a B1 that low, it's quite likely that the factor, if it really exists,
could be found with only trial division.

For each prime p of the form k*33554432+1, find 2^33554432 (mod p). If it's
one, that's a factor. That calculation is only 20 modular squarings (of 2^32),
and it should be trivial to hammer out 10^10 of those in no time at all.

Paul/David/Jim - you're the fast x86 guys - can you be of any help?

Phil


()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]



____________________________________________________
Yahoo! Sports
Rekindle the Rivalries. Sign up for Fantasy Football
http://football.fantasysports.yahoo.com

All,

I am a novice with the Zeta Function.  Could someone help me understand
something...

If I set S = 1, and calculate up to 1/7 and 1/7 only,

Z(s) = 1 + 1/2^s + 1/3^s + 1/4^s + 1/5^s + 1/6^s + 1/7^s

Is this what is meant "that no zeros could lie on the line Re(z) =
1" ?  Does S need to be greater than 1 here?

Thanks,

Jeff

On Mon, 4 Jul 2005, Jeffrey N. Cook wrote:
> I am a novice with the Zeta Function.  Could someone help me understand
> something...
>
> If I set S = 1, and calculate up to 1/7 and 1/7 only,
>
> Z(s) = 1 + 1/2^s + 1/3^s + 1/4^s + 1/5^s + 1/6^s + 1/7^s

This expression for the zeta function only converges when the real
part of s is greater than one.  In Calculus this was called the
"p-test" (at least in the books I use).

> Is this what is meant "that no zeros could lie on the line Re(z) =
> 1" ?  Does S need to be greater than 1 here?

Nope.  That refers to the analytic continuation of the sum above--that
means there is a function that converges on most of the complex plane
that agrees with the sum above (where it converges).  This continuation is
called the Riemann zeta function and its the one that all the talk is
about

CC

In my search for "triple double" values, I am looking for a k, such
that the two power series k.2^n+&-1 provide more than 10 Cunningham
Chains (1st kind), 10 Cunningham Chains (2nd kind) and 10 twins.
during the search, I have noticed that the number of k's producing
more than 10 Cunningham Chains length 2 (1st or 2nd kind) tends to
be consistently higher than the number of k providing 10 twins, and
the maxima of CCs found also looks to be higher than the maxima for
twins.

In this arrangement I count a Cunningham Chain of length 3 as two
CC's length 2, a CC4 as 3 CC2's etc.

Is there a fundamental reason for this? I would have thought that
for a given prime of the form k.2^n+1, that there were slightly
higher chances of k.2^n-1 being prime than k.2^(n+1)+1, given that
the twin partner is smaller than the CC partner. It would follow, to
my untutored, peanut sized brain that there would be more twins as a
result than CC's for a given power series.

The k's I am checking are chosen as follows:- they are multiples of
29#/17, and the n values 1 to 10 do not have any factors smaller
than 256, + or -.

I only take forward for checking the values of k which provide at
least 7 "triple double" points in the first 10 n, and 13 points by
n=100.

I will be happy to provide anyone who wants it with further
statistics to support the observations, made over the values from
k=1 up to k= 30trillion*29#/17

Regards

Robert Smith

Do the CCs occur in roughly equal numbers or is a particular sort of CC more
common?!?
Gary

Robert <rw.smith@...> wrote:
In my search for "triple double" values, I am looking for a k, such
that the two power series k.2^n+&-1 provide more than 10 Cunningham
Chains (1st kind), 10 Cunningham Chains (2nd kind) and 10 twins.
during the search, I have noticed that the number of k's producing
more than 10 Cunningham Chains length 2 (1st or 2nd kind) tends to
be consistently higher than the number of k providing 10 twins, and
the maxima of CCs found also looks to be higher than the maxima for
twins.

In this arrangement I count a Cunningham Chain of length 3 as two
CC's length 2, a CC4 as 3 CC2's etc.

Is there a fundamental reason for this? I would have thought that
for a given prime of the form k.2^n+1, that there were slightly
higher chances of k.2^n-1 being prime than k.2^(n+1)+1, given that
the twin partner is smaller than the CC partner. It would follow, to
my untutored, peanut sized brain that there would be more twins as a
result than CC's for a given power series.

The k's I am checking are chosen as follows:- they are multiples of
29#/17, and the n values 1 to 10 do not have any factors smaller
than 256, + or -.

I only take forward for checking the values of k which provide at
least 7 "triple double" points in the first 10 n, and 13 points by
n=100.

I will be happy to provide anyone who wants it with further
statistics to support the observations, made over the values from
k=1 up to k= 30trillion*29#/17

Regards

Robert Smith





Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/





---------------------------------
YAHOO! GROUPS LINKS


     Visit your group "primenumbers" on the web.

     To unsubscribe from this group, send an email to:
  primenumbers-unsubscribe@yahoogroups.com

     Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


---------------------------------





---------------------------------
How much free photo storage do you get? Store your holiday snaps for FREE with
Yahoo! Photos. Get Yahoo! Photos

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

From: "Robert" <rw.smith@...>
> In my search for "triple double" values, I am looking for a k, such
> that the two power series k.2^n+&-1 provide more than 10 Cunningham
> Chains (1st kind), 10 Cunningham Chains (2nd kind) and 10 twins.
> during the search, I have noticed that the number of k's producing
> more than 10 Cunningham Chains length 2 (1st or 2nd kind) tends to
> be consistently higher than the number of k providing 10 twins, and
> the maxima of CCs found also looks to be higher than the maxima for
> twins.

My immediate gut feel reaction tells me this would be expected.
I suspect that my gut feel is wrong though!
As always, everything should be predicted by sieving with small primes so
look at residues of k*2^n+/-1 mod p for small p, fixed k, variable n.

Phil

()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

--- In primenumbers@yahoogroups.com, Gary Chaffey <garychaffey2@y...>
wrote:
> Do the CCs occur in roughly equal numbers or is a particular sort of
CC more common?!?
> Gary


Gary: No simple answer to that. I would have to rerun the candidates
to find out how many CC3, CC4 etc. My program only counts points.

The statistics for the range of k 1 to 1531174737133 multiplied by
29#/34 (approx 1/20th of the overall numbers checked):

25250 values of k have 7 or more triple double points at n=10
of these:
2814 had 13 or more points at n=100 and of these:
81 had 20 or more points at n=500, the best of which were 4 23's and 5
22's

49 of those taken to 500 (2814 candidates)had 10 or more CC's of the
1st kind (including a 13 and 3 12's)
41 of those taken to 500 had 10 or more CCs of the 2nd kind (including
7 12's)
4 of those taken to 500 had 10 or more twins (1 with 11)
1 candidate fell into two categories

As I might have expected, twins are slightly more prevalent - if I
average the scores of the 2814 candidates with 13 or more points, they
have 5.09 CC1s, 5.09 CC2s and 5.25 twins.

So it appears that the distribution curves for CC's amd twins are not
the same, which defies simple analysis.

Regards

Robert Smith

I'm many miles from home, and without my C&P, and floundering with my google
searches. I don't suppose someone could provide some links, or a few quick
hints for the following.

Is it possible to evaluate a polynomial (in Z_p[x]) of degree n at many, say m,
points efficiently? i.e. o(m*n) operations mod p.
How about evaluating the product of all of the above evaluations directly,
without  needing to generate their individual values?

My memory is telling me that there is such an FFT-based technique, but for the
life of me I can't re-invent it.

Phil


()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]



____________________________________________________
Sell on Yahoo! Auctions – no fees. Bid on great items.
http://auctions.yahoo.com/

Its been a thrill to me to use the pari to factorize large numbers. A
very small observation which i made is what follows:-

A mobius function M(n) is defined as follows:

M(n) = 0 if p^2|n for some prime number p.
M(n)= -1 if n has odd number of prime divisors
M(n)=+1 if n has even number of prime divisors.

A number n is said to be a mobius number if M(n)=+1 or -1
meaning there is no p such that p^2|n

The question:-
The probability that a given big number n is a mobius number is very
high. What is the mathematical reasoning behind this.

[pushing back on list]

--- Chris Caldwell <caldwell@...> wrote:
> At 09:23 AM 7/7/2005, you wrote:
> >I'm many miles from home, and without my C&P, and floundering with my google
> >searches. I don't suppose someone could provide some links, or a few quick
> >hints for the following.
>
> I don't recall this.  I've got the book.  Where/how do you suggest I look?
> Found it--three algorithms: are the points in artih. prog, geo prog or
> arbitrary?

Anna is coming to Turku with my copy of the book today.

I have had a wacky idea for a possible modification to pollard rho.
I was wondering if one could iterate different starting points (using the same
function), and then the birthday paradox could kick in as you take gcds using
differences between each possible pair of final values.

t_i_0 = a_i, iterate t_i_m = t_i_{m-1}^2+a up to t_i_n
Then look at (t_i_n - t_j_n) for all pairs {i,j},
this, as in t_i_m-t_i_{m-1}, is a (recursive) difference of squares.
To do this look at P(x) = Prod(x-t_i_n) at x=t_j_n

Unfortunately there's the nasty factor of (t_i_n-t_i_n) in that product, which
I need to remove. (Any ideas how to do this massive product of differences?)

I don't believe it will be an improvement over the current Pollard Rho (as I
don't believe in the 'random cycles'/'birthday paradox' nature of Rho in the
first place), but believe it might shift how/where the birthday paradox kicks
in. (Which is useless if my prejudice is correct :-| .)
It however lets Rho be distributed very easily. It may be an old idea anyway.

A second Rho idea, while I'm here:
It's common knowledge that apart from x->x^2 and x->x^2-2 all x->x^2+a
iterations are as good as each other. However I might be tempted to claim that
x->x^2-6 is a (ever so fractionally) better iteration function than x->x^2+a
for any n for finding small factors. What kind of test would I have to perform
in order to verify if the improvement is measurable? I tested ten thousand
numbers in GP, and 'visually' it looks like -6 finds factors faster than +a,
but that could just be personal bias in only paying attention to the positive
results.

Unfortunately the improvement decreases to zero as the size of factors you're
looking for increases. So even if my claim is true, you'd be most likely to be
running simple Euclid-GCD-based (i.e. tree) trial division at that stage
anyway, and not see its benefits.

Phil

()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

Phil Carmody wrote:
> Anna is coming to Turku with my copy of the book today.
>
> I have had a wacky idea for a possible modification to pollard rho.
> I was wondering if one could iterate different starting points (using the same
> function), and then the birthday paradox could kick in as you take gcds using
> differences between each possible pair of final values.
>
> t_i_0 = a_i, iterate t_i_m = t_i_{m-1}^2+a up to t_i_n
> Then look at (t_i_n - t_j_n) for all pairs {i,j},
> this, as in t_i_m-t_i_{m-1}, is a (recursive) difference of squares.
> To do this look at P(x) = Prod(x-t_i_n) at x=t_j_n
>
> Unfortunately there's the nasty factor of (t_i_n-t_i_n) in that product, which
> I need to remove. (Any ideas how to do this massive product of differences?)

This sounds like one of the research problems in C&P.  I've worked alot on
it and can see some similarities to your problem.  In chapter 6, research
problem 6.16 starts out by saying:

"Observe first the amusing algebraic identity:
F(x) = ((x^2 - 85)^2 - 4176)^2 - 2880^2 =
(x - 13)(x - 11)(x - 7)(x - 1)(x + 1)(x + 7)(x + 11)(x + 13)"

which, as we can all see is also =
(x^2 - 1^2)(x^2 - 7^2)(x^2 - 11^2)(x^2 - 13^2)
[ie, your difference of squares]
So, you can test 8 algebraic factors with only 3 squarings.  This can also
be extended up to 4 squarings to test 16 algebraic factors at once.  I've
written a program to generate these pretty quickly.  However, I've also
used this program to search for a 5 squaring/32 a.f. solution but haven't
found any to date.

I know that this won't completely cover your difference of squares
multiplication, but you can use several different polynomials (similar to
F(x) above) to try and obtain a covering set.  I'm not sure how much this
will help with your current problem, but I thought I'd throw it out there
to see what you (and anyone else) thought.  If you'd like the program, or
would like the results for the 4 squaring/16 a.f. polynomials, just let me
know and I can send it on over.

-David C.


> I don't believe it will be an improvement over the current Pollard Rho (as I
> don't believe in the 'random cycles'/'birthday paradox' nature of Rho in the
> first place), but believe it might shift how/where the birthday paradox kicks
> in. (Which is useless if my prejudice is correct :-| .)
> It however lets Rho be distributed very easily. It may be an old idea anyway.
>
> A second Rho idea, while I'm here:
> It's common knowledge that apart from x->x^2 and x->x^2-2 all x->x^2+a
> iterations are as good as each other. However I might be tempted to claim that
> x->x^2-6 is a (ever so fractionally) better iteration function than x->x^2+a
> for any n for finding small factors. What kind of test would I have to perform
> in order to verify if the improvement is measurable? I tested ten thousand
> numbers in GP, and 'visually' it looks like -6 finds factors faster than +a,
> but that could just be personal bias in only paying attention to the positive
> results.
>
> Unfortunately the improvement decreases to zero as the size of factors you're
> looking for increases. So even if my claim is true, you'd be most likely to be
> running simple Euclid-GCD-based (i.e. tree) trial division at that stage
> anyway, and not see its benefits.
>
> Phil
>
> ()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
> /\    against HTML mail        /\  against gratuitous bloodshed
>
> [stolen with permission from Daniel B. Cristofani]

hi Sudarshan,

> Its been a thrill to me to use the pari to factorize
> large numbers.

You might also like to try out MIRACL's factoring
package below.

http://indigo.ie/~mscott/#other

> The question:-
> The probability that a given big number n is a
> mobius number is very
> high. What is the mathematical reasoning behind
> this.

According to mathworld (URL below) the asymptotic
density of square free numbers is 6/(pi^2) which is
approximately 60%. So you should hit a squareful
number nearly 40% of the time. With what probability
did you find that the number under test to be
squarefree and for how many integers did you test?

http://mathworld.wolfram.com/Squarefree.html


Sarad.




____________________________________________________
Sell on Yahoo! Auctions – no fees. Bid on great items.
http://auctions.yahoo.com/

David, quoting me:
> > I have had a wacky idea for a possible modification to pollard rho.
> > I was wondering if one could iterate different starting points (using the
> same
> > function), and then the birthday paradox could kick in as you take gcds
> using
> > differences between each possible pair of final values.
> >
> > t_i_0 = a_i, iterate t_i_m = t_i_{m-1}^2+a up to t_i_n
> > Then look at (t_i_n - t_j_n) for all pairs {i,j},
> > this, as in t_i_m-t_i_{m-1}, is a (recursive) difference of squares.
> > To do this look at P(x) = Prod(x-t_i_n) at x=t_j_n
> >
> > Unfortunately there's the nasty factor of (t_i_n-t_i_n) in that product,
> which
> > I need to remove. (Any ideas how to do this massive product of
> differences?)
>
> This sounds like one of the research problems in C&P.  I've worked alot on
> it and can see some similarities to your problem.  In chapter 6, research
> problem 6.16 starts out by saying:

That's related, but the poly evaluation I'm after is at arbitrary points.
The closest thing in C&P is in the research problems for exponential-time
factoring algorithms section - the 'g^K' part-2 for P-1.

> If you'd like the program, or
> would like the results for the 4 squaring/16 a.f. polynomials, just let me
> know and I can send it on over.

I certainly do. I submitted a whole bunch of 4/16 results, found quite easily,
to C&P several years ago, but decided that 5/32 was _hard_. However, hard
problems can sometimes be solved by throwing a combination of the right
algorithm and the right (quantity of) hardware, and enough time. Therefore I'd
like to revisit it. I can let you have what I have too, in case it's useful,
but I don't think it will be, as it surely doesn't scale to 5/32, and also
makes _absolutely_ no sense to me at all any more.

Phil

()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

I am pleased to annouce that I found the largest known Woodall prime.

1195203*2^1195203-1 is 359799 digits long

It was found using my MultiSieve program for sieving and Jean Penne's
LLR for the primality test.  Once verified it should be #63 in Chris
Caldwell's list.

--Mark

Congratulations!
Gary

Mark Rodenkirch <mgrogue@...> wrote:
I am pleased to annouce that I found the largest known Woodall prime.

1195203*2^1195203-1 is 359799 digits long

It was found using my MultiSieve program for sieving and Jean Penne's
LLR for the primality test.  Once verified it should be #63 in Chris
Caldwell's list.

--Mark




Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/





---------------------------------
YAHOO! GROUPS LINKS


     Visit your group "primenumbers" on the web.

     To unsubscribe from this group, send an email to:
  primenumbers-unsubscribe@yahoogroups.com

     Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


---------------------------------




---------------------------------
Yahoo! Messenger NEW - crystal clear PC to PCcalling worldwide with voicemail

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

Mark,
Congratulations on a huge and so rare prime!
I just noticed on the Top-5000 status page and I was
very surprised. The old record was almost 5 years old.
I was also there, testing the numbers on the 1.1M level,
but not close enough...

Predrag


--- In primenumbers@yahoogroups.com, "Mark Rodenkirch" <mgrogue@w...>
wrote:
> I am pleased to annouce that I found the largest known Woodall prime.
>
> 1195203*2^1195203-1 is 359799 digits long
>

For those of you with access a PowerPC, I want to direct you to Phil
Carmody's PIES project (the pies_project group in Yahoo).

Over the weekend, I found this 100070 digit prime:
Phi(3,-1642659500503^4096)

On my 2.5 GHz G5, the PRP test took only 4 minutes.  According to
Phil, a 2.0 GHz P4 does this same test in about 10 minutes which means
that the PowerPC is very competitive with x86 for numbers of this
form.  AFAIK, it is the only prime on Chris Caldwell's list that has
been found with a PowerPC CPU.

--Mark

Hi There:

I thought the group might be interested in this sculpture:

It's a clock that displays the time only if it's a Prime Number.

http://www.primetimeclock.com

Please do not consider this post irrelevant...

We are now 1087 in number (total members in our group).
And that's a prime number...

What is so interesting about this prime number?

-Sudarshan

Could somebody please give me some online references to information
about the benefits of sieving.
E.g. Suppose a number K is a random integer then it has a 1 in 1/ln K
chance of being prime but if K is not divisible by 2 or 3 then the
chance of it being prime is 2/(3lnK)
etc
That type of thing.
Thanks in advance
Gary

As usual a typo on my formula!
I know it was just an example but if K is not divisible by 2 or 3 then the
chance of it being prime is 3/(lnK)
Gary
garychaffey2 <garychaffey2@...> wrote:
Could somebody please give me some online references to information
about the benefits of sieving.
E.g. Suppose a number K is a random integer then it has a 1 in 1/ln K
chance of being prime but if K is not divisible by 2 or 3 then the
chance of it being prime is 2/(3lnK)
etc
That type of thing.
Thanks in advance
Gary




Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/





---------------------------------
YAHOO! GROUPS LINKS


     Visit your group "primenumbers" on the web.

     To unsubscribe from this group, send an email to:
  primenumbers-unsubscribe@yahoogroups.com

     Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.


---------------------------------




---------------------------------
Yahoo! Messenger NEW - crystal clear PC to PCcalling worldwide with voicemail

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

hi,

--- Sudarshan Iyengar <sudarshan@...>
wrote:
> We are now 1087 in number (total members in our
> group).And that's a prime number...
> What is so interesting about this prime number?

Its a Kynea prime number with index 5?

Sarad.



____________________________________________________
Sell on Yahoo! Auctions – no fees. Bid on great items.
http://auctions.yahoo.com/

hi,

The following observation might help.

From 1-10, the numbers not divisible by 2,3 are 1,5,7.
I.e 3 in number.

Between 11-20,the numbers not divisible by 2,3 are
11,13,17,19.
I.e 4 in number.

Between 21-30,the numbers not divisible by 2,3 are
23,25,29.
I.e 3 in number.

So, between any 10 consecutive numbers of the form xx1
and xx0.

Either of the 3 cases occur.
3 | xx1   and so 3| xx1,xx4,xx7.(Case 1)
3 | xx1+1 and so 3| xx2,xx5,xx8.(Case 2)
3 | xx1+2 and so 3| xx3,xx6,xx9.(Case 3)

The favourable condition in Case 1 is the occurance of
xx1 and xx7 because 2|xx4 anyway. So, the number of
favourable case is 2.

The favourable condition in Case 2 is the occurance of
xx5 because 2|xx2 and 2|xx8 anyway. So, the number of
favourable case is 1.

The favourable condition in Case 3 is the occurance of
xx3 and xx9 because 2|xx6 anyway. So, the number of
favourable case is 2.

Between any 10 consecutive numbers xx1 and xx0, all
the time 3 divides (2  of the numbers) or (one of the
numbers) in accordance to the favourable cases in Case
1,2 and 3.

Since 5 of the numbers between 10 consecutive numbers
xx1 and xx0 is divisibe by 2, the total of numbers
divisible by 2 and 3 is

Case 1: 5+2=7
Case 2: 5+1=6
Case 3: 5+2=7.

Therefore 6 out of every 10 or 7 out of every 10
consecutive numbers is divisible by 2 and 3, which are
respectively 70% and 60% respectively. So, the total
of numbers divisible by 2 and 3 between 1 and 100 is
7+6+7+7+6+7+7+6+7+7=67 out of 100, which is 67%.

Between 100 and 200.
6+7+7+6+7+7+6+7+7+6= 66%.

Trying out a few times and finding the average we see
that the percentage of numbers divisible by 2 and 3 is
about 66.67%.

According to Dr.Schneier's book,testing an odd number
is not divisible by 3,5,7 eliminates 54% of odd
numbers under test. It is found in general that the
fraction of odd candidates which is not a multiple of
any prime less than n is 1.12/ln n.

Hope this helps.

Sarad.



--- Gary Chaffey <garychaffey2@...> wrote:

> As usual a typo on my formula!
> I know it was just an example but if K is not
> divisible by 2 or 3 then the
> chance of it being prime is 3/(lnK)
> Gary
> garychaffey2 <garychaffey2@...> wrote:
> Could somebody please give me some online references
> to information
> about the benefits of sieving.
> E.g. Suppose a number K is a random integer then it
> has a 1 in 1/ln K
> chance of being prime but if K is not divisible by 2
> or 3 then the
> chance of it being prime is 2/(3lnK)
> etc
> That type of thing.
> Thanks in advance
> Gary




____________________________________________________
Sell on Yahoo! Auctions – no fees. Bid on great items.
http://auctions.yahoo.com/

Hi,
I am a new member of primeform and as well primenumbers.
I downloaded the pfgw source code version for win32.
When I issue build command when opened in MS VC++ 6.0 the following error
occured.

Linking...
LINK : fatal error LNK1104: cannot open file
"..\..\pfconfig\objects\decimal.obj"
Error executing link.exe.
pfgw.exe - 1 error(s), 0 warning(s)

Can u please advice how to overcome this problem.


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

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

From: "garychaffey2" <garychaffey2@...>
> Subject: Benefits of sieving. References please
>
> Could somebody please give me some online references to information
> about the benefits of sieving.

Mertens' Theorem.

Phil

()  ASCII ribbon campaign      ()    Hopeless ribbon campaign
/\    against HTML mail        /\  against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around
http://mail.yahoo.com

Can't think of anything off the top of my head, and David
Wells's "Curious and Interesting Numbers" does not have an entry.
According to Chris Caldwell's Prime Curios

1087 is a prime factor of the 32nd Lucas number (the first such
number with index of form 2^n that is composite).
The largest known number such that (10000^n+1)/10001 is probably
prime.


Perhaps we should try and find another half a dozen new members, then
we are 1093. Wells's entry for 1093 is a bit more interesting:

"2^1092 - 1 is divisible by 1093. Only one other number is known
below 4 * 10^12 with this property, 3511.
In 1909 Wieferich created a sensation by proving that if Fermat's
equation, x^p + y^p = z^p, has a solution in whih p is an odd prime
that does notr divide any of x, y or z, then 2^(p-1) - 1 is divisible
by p^2. As facts about Fermat's last theorem go, this is remarkably
simple. That 1093 and 3511 are the only solutions below 4 * 10^12
means that only these two cases of Fermat's theorem need to be
considered, below that limit, of p does not divide xyz."

Douglas Chester







--------------------------------------------------------------------------------
Do you Yahoo!?
Try Yahoo! Photomail Beta: Send up to 300 photos in one email!


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

Hello,

New to the list and I've got a few questions about sieving Proth
numbers in relation to the Sierpinski conjecture.

I know Mikael Klasson and Paul Jobling have written an insanely
fast siever for x86 via lots of optimisations and hand hackery
of assembly. I'm using this very program to contribute to the
SeventeenOrBust.com project.

I'm looking to get something done in C (although I am using the
GMP library which does use assembly for some processors). The
biggest 'problem' with this library is a lack of a modmul
operation. I might have to grab Knuth and see what I can magic
up.

I've 'stolen' lots of good ideas from what I can see in the output
of proth_sieve during initialisation (finding the optimal mod value
of n's for each k and combining this into one large group).

I then implement the baby-steps giant-steps algorithm for solving
the discrete log (right now it picks 15840 for m instead of using
sqrt(p) which can be huge).

I'm just reading up on Silver-Pohlig-Hellman and how that can
help when p-1 is smooth.

My main question though, is about removing k or p candidates
before I even bother trying to calculate the discrete log to
solve for n. I've noticed that the stat.txt value from
proth_sieve claims that roughly 1/4 of all p's were 'whacked'
along with 1/2 of the k values for each p.

Under what conditions is a k or p not even tested?

Right now I only have 2 possible conditions, based on requirements
of Baby-Steps Giant-Steps, but they rarely ever stop a k or p
being tested.

1) a whole p is untested if (2^-1 mod p) doesn't exist.
2) an individial k is untested if (k^-1 mod p) doesn't exist.

Is it something to do with the Jacobi symbols that are computed
during initialisation, and I'd guess it has to do with the
k-values but I just can't see what it could be.

I had previously looked at the problem a different way, that is
making me think that there must be a way to detect it:-

Compute initial_r = k*2+1 mod p.
If initial_r == 1 then stop, p will never factor k
set r=initial_r
set n=1
while( n < 50000000 ) {
    if( r == 0 ) {
        stop. p is a factor for n
    }
    r=((2*r)+1) mod p
    n=n+1
    if( r == initial_r ) {
        stop. p will never be a factor. cyclic loop of r.
    }
}

Many k,p values will enter loops (of a size which is a factor of
p-1) and r will never equal 0. I could never work out whether it
was possible to detect this 'in advance'.

Thanks in advance,

-Alex

Let's take the sequence  :

u(n) = nextprime >=n
(n >= 0 ) - Sloane A007918

2,2,2,3,5,5,7,7,11,11,11,11,13,13,17,17,17,17,19,19,23,23,
23,23,29,29,29,29,29,29,31,31,37,37,37,37,37,37,41,41,41,41

Now take a look at  the serie :   s(n) =  1/u(0) + 1/u(1) + .... + 1/u(n)

s(n) is divergent. (includes all primes as denominators)

I seems that s(n) = log(n) + K  -- where K = 0.2934581.... when n goes to
infinity.

Ex : (tested from = n=10 to n = 10^10)
  n = 10^10
s(n)= 23.3193090775   log(n) = 23.0258509299  s(n) - log(n) =  0.2934581....

** Question: does anybody have an idea about that ?

(trying to look into Samaranche papers, and found nothing).

thx.



-------------------------------
http://www.echolalie.com
---------------------------