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: 1090
  • Category: Number Theory
  • Founded: Dec 27, 2000
  • Language: English
? Already a member? Sign in to Yahoo!

Yahoo! Groups Tips

Did you know...
Real people. Real stories. See how Yahoo! Groups impacts members worldwide.

Messages

Advanced
Messages Help
Messages 16113 - 16142 of 25181   Oldest  |  < Older  |  Newer >  |  Newest
Messages: Show Message Summaries Sort by Date ^  
#16113 From: "John W. Nicholson" <reddwarf2956@...>
Date: Mon Feb 21, 2005 1:31 am
Subject: Proof of less-fortunate numbers
reddwarf2956
Send Email Send Email
 
Proof of less-fortunate numbers (as seen on
http://primes.utm.edu/glossary/page.php?sort=FortunateNumber ):

By observation: The largest prime of the solution for each
primordial to "Carl Pomerance
Observation" by Said El Aidi on
http://www.primepuzzles.net/problems/prob_002.htm are less-fortunate
numbers.

Knowing the above fact, how big does the size of the gap to the next
prime, assuming with and without that p_n# (+/-) 1 is prime, have to
be in order to fail to be a Fortunate Number? Chris stated on the
page (I changed the notation) "So we are looking for a prime gap
near p_n# of about (log p_n# log log p_n#)^2." But two things are
for sure, there is a gap with a size >= p_n after p_n# and . (For
the same reason that there is a gap after p_n! >= p_n but with a
common multiple added to p_n#.) Is this the only thing that can be
said about this gap?

Can a modification of Aidi's work be stated to prove a Fortunate
number, q, exist between p_n# + p_n < q < p_n# + (p_(n+1))^2, so
that r = q - p_n# with r being prime? Does knowing the status of
less-fortunate numbers satisfy a necessary or sufficient condition
for Fortunate number q? I am thinking that the number of primes in
the Aidi range is greater than this range but there is always one
prime because of the required solutions to the congruence of numbers
between p_n# and p_n! in the range p_n# + p_n < q < p_n# + (p_(n+1))
^2. Another words the solutions must be spread out, this small group
can not be the last grouping.

On a different note, I am rewriting Aidi's statements, I am hoping
someone can read and send suggestions back to me about the
document.  The two page paper is in MSWord format and is not
downloadable to the web page. Can someone look at it by writing me
personally?

Thanks for your answers,

John

#16114 From: "John W. Nicholson" <reddwarf2956@...>
Date: Mon Feb 21, 2005 7:51 am
Subject: Omega and Smarandache constants
reddwarf2956
Send Email Send Email
 
0.567143290... Omega
http://mathworld.wolfram.com/OmegaConstant.html
http://www.research.att.com/cgi-
bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A030178

0.567148...  Smarandache

http://mathworld.wolfram.com/AndricasConjecture.html
http://mathworld.wolfram.com/SmarandacheConstants.html

Why are these two constants so close? Note the differance, and how
do they (or do they) relate to the delta ~ 1/(4*10^6)? (in this
paper:

Andrew Granville,
Unexpected irregularities in the distribution of prime numbers
Proceedings of the International Congress of Mathematicians (Zurich,
Switzerland, 1994), Vol. I (1995), 388-399.
Can be found here:
http://www.dms.umontreal.ca/~andrew/agpapers.html#A7 )

Is there a proof that there is no other primes which have a closer
number to omega? What about the primes which have a high "figure of
merit for the gap?" (which can be found on:
http://www.trnicely.net/gaps/gaplist.html )

#16115 From: Bill Krys <billkrys@...>
Date: Mon Feb 21, 2005 3:55 pm
Subject: Prime # Odometer = Prime # Generator
billkrys
Send Email Send Email
 
Hello,

take a circle of 1 unit circumference, with a mark at top dead center (TDC).
Rotate it
360 degrees, back to TDC. Then rotate it again 360 degrees. Then add to this
circle
another circle of 2 units circumference. Rotate the first circle again 360
degrees. #1
circle is back to TDC, but #2 circle, which rotates like an odometer along with
circle
#1, but 1/2 the distance, is off TDC. As only #1 circle is back to TDC after
another 360
degrees rotation, make another circle of 3 units circumference. Rotate #1 circle
360
degrees. Now #1 and #2 circles are at TDC, so don't add the #4 circle. Rotate #1
again
through to TDC and as only #1 is at TDC and #2 and #3 are off TDC, add another
circle,
this time of 5 units circumference. Continue adding circles of P units
circumference only
when the #1 circle is at TDC and all other (prime #) circles are off TDC. You
will
generate all the primes.

Bill

=====
Bill Krys
Email: billkrys@...
Phone: 780.474.9493
Cell: (780) 995-6214
ICQ: 122663993
12112-50 Street
Edmonton, Canada T5W 3C5

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

#16116 From: "mcnamara_gio" <mcnamara_gio@...>
Date: Tue Feb 22, 2005 7:58 pm
Subject: Re:prime sums +-1
mcnamara_gio
Send Email Send Email
 
Let s(n) be sum of first n primes. Has anyone studied sequence of n
for which none of the three numbers s(n)-1, s(n), s(n)+1 is prime? The
first few terms are:
8,10,11,15,16,18,20,21,22..................................
Perhaps it is more interesting of such n for which at least one of the
three numbers is prime. The first few terms are:
2,3,4,5,6,7,9,12,13,14,17,19,25,29...........................

#16117 From: "Michael Gian" <work.gian@...>
Date: Wed Feb 23, 2005 1:08 pm
Subject: (im)perfect numbers revisited
pastmyprime2
Send Email Send Email
 
A previous post discussed the fact that all perfect mumbers are the
sum of positive odd cubes.  I also said that all numbers "in the
form of" perfect numbers also are.  Decio pointed out that the form
holds not only for odd prime exponents, but also for all positive
odd exponents.  He and I both have proofs, his is posted; let's
move on.

Suffering notation restrictions while posting, I beg your patience.

Consider the sum (dotty notation) 1^3+3^3+...+(2^n-3)^3 +(2^n-1)^3.
It is also (Mathematica convention) Sum[(2k-1)^3,{k, 1, 2n-1}].
Notice that the ultimate term is a Mersenne number.
It totals to 2^((2n-1)-1)*(2^(2n-1)-1,which has the form of a
perfect number.  Let it be called S_n.

Not suprisingly, for n>1, S_n==0(mod 2).  When n>2 the interval from
n-1 to n always has an even number of terms, etc.

That, apparently, for n>1, S_n==1(mod 3) is suprising to me, as is
the apparent repeating cycles for all greater modulo primes.  For
instance S_n=={3, 1}(mod 5) and S_n=={0, 6, 1}(mod 7}, etc.  The
{lists} repeat exactly for the small n>1 and small mod p that I test.

I would appreciate being pointed to appropriate studies in order to
better understand this.

Michael

#16118 From: "mcnamara_gio" <mcnamara_gio@...>
Date: Wed Feb 23, 2005 1:55 pm
Subject: prime sums
mcnamara_gio
Send Email Send Email
 
Let s(n) be sum of first n primes. a=s(n)-n and b=s(n)+1. Is it true
that there is at least one prime p so that a<=p<=b.

#16119 From: "Jean-Pierre Pratali" <jpierre.pratali@...>
Date: Wed Feb 23, 2005 2:42 pm
Subject: Goldbach : Two new conjectures inside the first ?
jppratali
Send Email Send Email
 
According to the Goldbach conjecture every even integer >2 is, by
one or several manners, the sum of two primes.
I suppose it exists a large table of such decompositions for a wide
range of even numbers. Personally I could not find where.
So I built, "by hand",  a small table for even numbers :
...
14  =  3 + 11  =  7 + 7
16  =  3 + 13  =  5 + 11
18  =  5 + 13  =  7 + 11
...
46  =  3 + 43  =    5 + 41  =  17 + 29  =  23 +23
48  =  5 + 43  =    7 + 41  =  11 + 37  =  17 + 31  =  19 + 29
50  =  3 + 47  =    7 + 43  =  13 + 37  =  19 + 31
...
90  =  3 + 87  =    7 + 83  =  11 + 79  =  17 + 73  =  19 + 71  =
23 + 67  =  29 + 61  =  31 + 59  =  37 + 53  =  43 + 47
92  =  3 + 89  =  13 + 79  =  19 + 73  =  31 + 61
94  =  5 + 89  =  11 + 83  =  23 + 71  =  41 + 53  =  47 + 47
96  =  7 + 89  =  13 + 83  =  17 + 79  =  23 + 73  =  37 + 59  =  43
+ 53
98  =  19 + 79  =  31 + 67  =  37 + 61

Now let us examine each set of decomposition for each even.
We remember that a prime is either a "gaussian" one (-1 mod 4) or
a "not gaussian" one (1 mod 4) (they also call it "rational"; it is
also the sum of 2 squares )

So let us look at the pairs of primes for each even : We can see
that

1. the corresponding pairs are either all "homogeneous" (gaussian-
gaussian or rational-rational)  or all "mixed" (gaussian-rational or
rational-gaussian).

Next, if we consider the set of all the even numbers >4, we can see
that

2. a "mixed" (m) always succeeds to a "homogeneous" (h) and
inversely.

For example (with (g) for "gaussian", (r) for "rational", (h) for
homogeneous" and (m) for "mixed" :

46(h)  =  3(g) + 43(g)  =  5(r) + 41(r)  =  17(r) + 29(r)  =  23g)
+ 23(g)
48(m)  =  5(r) + 43(g)  =  7(g) + 41(r)  =   11(g) + 37(r)  =  17(r)
+ 31(g)  =  19(g) + 29(r)
50(h)  =   3(g) + 47(g)  =  7(g) + 43(g)  =  13(r) + 37(r)  =  19(g)
+ 31(g)
52(m)  =  5(r) + 47(g)  =  11(g) + 41(r)  =  23(g) + 29(r)
...
90(h)  =  3(g) + 87(g)  =    7(g) + 83(g)  =  11(g) + 79(g)  =  17
(r) + 73(r)  =  19(g) + 71(g)  =  23(g) + 67(g)  =  29(r) + 61(r)
=  31(g) + 59(g)  =  37(r) + 53(r)  =  43(g) + 47(g)
92(m)  =  3(g) + 89(r)  =  13(r) + 79(g)  =  19(g) + 73(r)  =  31(g)
+ 61(r)
94(h)  =  5(r) + 89(r)  =  11(g) + 83(g)  =  23(g) + 71(g)  =  41(r)
+ 53(r)  =  47(g) + 47(g)
96(m)  =  7(g) + 89(r)  =  13(r) + 83(g)  =  17(r) + 79(g)  =  23(g)
+ 73(r)  =  37(r) + 59(g)  =  43(g) + 53(r)

Does a large table confirm (1) and (2) indefinitely ?

#16120 From: Décio Luiz Gazzoni Filho <decio@...>
Date: Wed Feb 23, 2005 3:24 pm
Subject: Re: [PrimeNumbers] (im)perfect numbers revisited
deciogazzoni
Send Email Send Email
 
On Wednesday 23 February 2005 10:08, you wrote:
> A previous post discussed the fact that all perfect mumbers are the
> sum of positive odd cubes.  I also said that all numbers "in the
> form of" perfect numbers also are.  Decio pointed out that the form
> holds not only for odd prime exponents, but also for all positive
> odd exponents.  He and I both have proofs, his is posted; let's
> move on.
>
> Suffering notation restrictions while posting, I beg your patience.
>
> Consider the sum (dotty notation) 1^3+3^3+...+(2^n-3)^3 +(2^n-1)^3.
> It is also (Mathematica convention) Sum[(2k-1)^3,{k, 1, 2n-1}].
> Notice that the ultimate term is a Mersenne number.
> It totals to 2^((2n-1)-1)*(2^(2n-1)-1,which has the form of a
> perfect number.  Let it be called S_n.
>
> Not suprisingly, for n>1, S_n==0(mod 2).  When n>2 the interval from
> n-1 to n always has an even number of terms, etc.
>
> That, apparently, for n>1, S_n==1(mod 3) is suprising to me, as is
> the apparent repeating cycles for all greater modulo primes.  For
> instance S_n=={3, 1}(mod 5) and S_n=={0, 6, 1}(mod 7}, etc.  The
> {lists} repeat exactly for the small n>1 and small mod p that I test.

The fact that cycles happen is an easy consequence of Fermat's little theorem.
We have 2^(p-1) == 1 mod p and 2^p == 2 mod p, or equivalently 2^p - 1 == 1
mod p. Then clearly 2^(p-1) (2^p - 1) == 1*1 = 1 mod p.

Now consider 2^(2p - 2) (2^(2p - 1) - 1) == 2^(2(p-1)) (2^p 2^(p-1) - 1) ==
(2^(p-1))^2 (2^(p-1) 2^p - 1) == 1 (1*2^p - 1) == 1*1 == 1 mod p.

More generally, consider 2^(k(p-1)) (2^(k(p-1) + 1) - 1) mod p, and it's
easily seen that the cycle is bounded at p-1, although there are less in some
cases: in particular, if 2 isn't a primitive root mod p, so that 2^((p-1)/d)
== 1 mod p for some divisor d of p-1, then the cycle size is (p-1)/d (taking
the largest valid d here, of course).

I leave as an exercise to you to prove that S_n mod p == S_c mod p, where c =
n % (p-1)/d. Hint: remember that 2^0 (2^1 - 1) = 1.

Hope that settles the problem for you.

Décio


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

#16121 From: richard042@...
Date: Wed Feb 23, 2005 3:40 pm
Subject: Re: (im)perfect numbers revisited
richard042
Send Email Send Email
 
Hello,

--- In primenumbers@yahoogroups.com, "Michael Gian" <work.gian@s...>
wrote:
> Consider the sum (dotty notation) 1^3+3^3+...+(2^n-3)^3 +(2^n-1)^3.
> It is also (Mathematica convention) Sum[(2k-1)^3,{k, 1, 2n-1}].

I think you mean {k,1,n} for the range of the mathematica sum.

> Notice that the ultimate term is a Mersenne number.

The ultimate term is a cube, how can it be a Mersenne number?

> It totals to 2^((2n-1)-1)*(2^(2n-1)-1,which has the form of a
> perfect number.  Let it be called S_n.
>
> Not suprisingly, for n>1, S_n==0(mod 2).

S(3), S(5), S(7), etc.. are not==0mod2

> When n>2 the interval from
> n-1 to n always has an even number of terms, etc.

The interval from n-1 to n is 1
The interval from S(n-1) to S(n) are two terms of the series,
as opposed to the sequence, but really, I can't infer what you mean
here.

> That, apparently, for n>1, S_n==1(mod 3) is suprising to me, as is

S(3)==0mod3, so you should be surprised if that were true.

> the apparent repeating cycles for all greater modulo primes.  For
> instance S_n=={3, 1}(mod 5) and S_n=={0, 6, 1}(mod 7}, etc.  The
> {lists} repeat exactly for the small n>1 and small mod p that I
test.

Quadratic reciprocity should tell you what you want to know here.

> I would appreciate being pointed to appropriate studies in order to
> better understand this.

You need to proofread and rewrite your inquiry first, hard to know
what you might be asking otherwise.

Sincerely,

Dick Boland

#16122 From: "sopadeajo2001" <sopadeajo2001@...>
Date: Wed Feb 23, 2005 7:17 pm
Subject: Re: Goldbach : Two new conjectures inside the first ?
sopadeajo2001
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "Jean-Pierre Pratali"
<jpierre.pratali@w...> wrote:
>
> According to the Goldbach conjecture every even integer >2 is, by
> one or several manners, the sum of two primes.
> I suppose it exists a large table of such decompositions for a wide
> range of even numbers. Personally I could not find where.
> So I built, "by hand",  a small table for even numbers :
> ...
> 14  =  3 + 11  =  7 + 7
> 16  =  3 + 13  =  5 + 11
> 18  =  5 + 13  =  7 + 11
> ...
> 46  =  3 + 43  =    5 + 41  =  17 + 29  =  23 +23
> 48  =  5 + 43  =    7 + 41  =  11 + 37  =  17 + 31  =  19 + 29
> 50  =  3 + 47  =    7 + 43  =  13 + 37  =  19 + 31
> ...
> 90  =  3 + 87  =    7 + 83  =  11 + 79  =  17 + 73  =  19 + 71  =
> 23 + 67  =  29 + 61  =  31 + 59  =  37 + 53  =  43 + 47
> 92  =  3 + 89  =  13 + 79  =  19 + 73  =  31 + 61
> 94  =  5 + 89  =  11 + 83  =  23 + 71  =  41 + 53  =  47 + 47
> 96  =  7 + 89  =  13 + 83  =  17 + 79  =  23 + 73  =  37 + 59  =
43
> + 53
> 98  =  19 + 79  =  31 + 67  =  37 + 61
>
> Now let us examine each set of decomposition for each even.
> We remember that a prime is either a "gaussian" one (-1 mod 4) or
> a "not gaussian" one (1 mod 4) (they also call it "rational"; it is
> also the sum of 2 squares )
>
> So let us look at the pairs of primes for each even : We can see
> that
>
> 1. the corresponding pairs are either all "homogeneous" (gaussian-
> gaussian or rational-rational)  or all "mixed" (gaussian-rational
or
> rational-gaussian).
>
> Next, if we consider the set of all the even numbers >4, we can see
> that
>
> 2. a "mixed" (m) always succeeds to a "homogeneous" (h) and
> inversely.
>
> For example (with (g) for "gaussian", (r) for "rational", (h) for
> homogeneous" and (m) for "mixed" :
>
> 46(h)  =  3(g) + 43(g)  =  5(r) + 41(r)  =  17(r) + 29(r)  =  23g)
> + 23(g)
> 48(m)  =  5(r) + 43(g)  =  7(g) + 41(r)  =   11(g) + 37(r)  =  17
(r)
> + 31(g)  =  19(g) + 29(r)
> 50(h)  =   3(g) + 47(g)  =  7(g) + 43(g)  =  13(r) + 37(r)  =  19
(g)
> + 31(g)
> 52(m)  =  5(r) + 47(g)  =  11(g) + 41(r)  =  23(g) + 29(r)
> ...
> 90(h)  =  3(g) + 87(g)  =    7(g) + 83(g)  =  11(g) + 79(g)  =  17
> (r) + 73(r)  =  19(g) + 71(g)  =  23(g) + 67(g)  =  29(r) + 61(r)
> =  31(g) + 59(g)  =  37(r) + 53(r)  =  43(g) + 47(g)
> 92(m)  =  3(g) + 89(r)  =  13(r) + 79(g)  =  19(g) + 73(r)  =  31
(g)
> + 61(r)
> 94(h)  =  5(r) + 89(r)  =  11(g) + 83(g)  =  23(g) + 71(g)  =  41
(r)
> + 53(r)  =  47(g) + 47(g)
> 96(m)  =  7(g) + 89(r)  =  13(r) + 83(g)  =  17(r) + 79(g)  =  23
(g)
> + 73(r)  =  37(r) + 59(g)  =  43(g) + 53(r)
>
> Does a large table confirm (1) and (2) indefinitely ?



The answer is that we do not need any experimental checking.

Every even number is of the form 4k or 4k+2
If the even number is 4k=4(k1+k2+1)=(4k1+1)+(4k2+3)
If the even number is 4k+2=4(k3+k4)+2=(4k3+1)+(4k4+1)
                       4k+2=4(k5+k6+1)+2=(4k5+3)+(4k6+3)

So even 4k+2 are always "homogeneous" and even 4k are always "mixed"

#16123 From: "thmsschuessler" <tls60@...>
Date: Wed Feb 23, 2005 9:20 pm
Subject: Definition of "Prime Number"
thmsschuessler
Send Email Send Email
 
Does anyone else have a major problem with the following
definition of "Prime Number" that is so ubiquitions in the
literature?

    "A positive integer that is divisible solely by itself and 1"?

#16124 From: Jud McCranie <j.mccranie@...>
Date: Wed Feb 23, 2005 10:15 pm
Subject: Re: [PrimeNumbers] Definition of "Prime Number"
judmccr
Send Email Send Email
 
At 04:20 PM 2/23/2005, thmsschuessler wrote:

>   Does anyone else have a major problem with the following
>definition of "Prime Number" that is so ubiquitions in the
>literature?
>
>    "A positive integer that is divisible solely by itself and 1"?

I don't except that a prime is > 1.  There are people who do have a problem
with that definition.

#16125 From: "Michael Gian" <work.gian@...>
Date: Fri Feb 25, 2005 1:14 pm
Subject: Re: (im)perfect numbers revisited
pastmyprime2
Send Email Send Email
 
I should proof more thoroughly, sorry.

The Mathematica range for the Sum is actually {k, 1, 2^(n-1)}; I had
omitted the parentheses.

When I mentioned that for n>2 the interval from n-1 to n has an even
number of terms, I meant that as n increases by 1 an even number of
(odd cube) terms are added.
The ultimate term is (2^n-1)^3, the cube of a Mersenne.

For instance:
S_1 = 1^3                                                [1 = 2^1-1]
S_2 = 1^3 + 3^3                                          [3 = 2^2-1]
S_3 = 1^3 + 3^3 + 5^3 + 7^3                              [7 = 2^3-1]
S_4 = 1^3 + 3^3 + 5^3 + 7^3 +9^3 + 11^3 + 13^3 + 15^5   [15 = 2^4-1]
,etc.

I trust that S_n = 2^((2n-1)-1)*(2^(2n-1)-1) is now clearly stated.
The request for help and guidance was to investigate S_n modulo
prime in general.  This inquiry was probably off the point of this
group as it is peripheral to prime numbers and more about number
theory.  Can anyone suggest a group more in line with such?

Michael

--- In primenumbers@yahoogroups.com, richard042@y... wrote:
>
> Hello,
>
> --- In primenumbers@yahoogroups.com, "Michael Gian"
<work.gian@s...>
> wrote:
> > Consider the sum (dotty notation) 1^3+3^3+...+(2^n-3)^3 +(2^n-1)
^3.
> > It is also (Mathematica convention) Sum[(2k-1)^3,{k, 1, 2n-1}].
>
> I think you mean {k,1,n} for the range of the mathematica sum.
>
> > Notice that the ultimate term is a Mersenne number.
>
> The ultimate term is a cube, how can it be a Mersenne number?
>
> > It totals to 2^((2n-1)-1)*(2^(2n-1)-1,which has the form of a
> > perfect number.  Let it be called S_n.
> >
> > Not suprisingly, for n>1, S_n==0(mod 2).
>
> S(3), S(5), S(7), etc.. are not==0mod2
>
> > When n>2 the interval from
> > n-1 to n always has an even number of terms, etc.
>
> The interval from n-1 to n is 1
> The interval from S(n-1) to S(n) are two terms of the series,
> as opposed to the sequence, but really, I can't infer what you
mean
> here.
>
> > That, apparently, for n>1, S_n==1(mod 3) is suprising to me, as
is
>
> S(3)==0mod3, so you should be surprised if that were true.
>
> > the apparent repeating cycles for all greater modulo primes.
For
> > instance S_n=={3, 1}(mod 5) and S_n=={0, 6, 1}(mod 7}, etc.  The
> > {lists} repeat exactly for the small n>1 and small mod p that I
> test.
>
> Quadratic reciprocity should tell you what you want to know here.
>
> > I would appreciate being pointed to appropriate studies in order
to
> > better understand this.
>
> You need to proofread and rewrite your inquiry first, hard to know
> what you might be asking otherwise.
>
> Sincerely,
>
> Dick Boland

#16126 From: Décio Luiz Gazzoni Filho <decio@...>
Date: Fri Feb 25, 2005 1:21 pm
Subject: Re: [PrimeNumbers] Re: (im)perfect numbers revisited
deciogazzoni
Send Email Send Email
 
On Friday 25 February 2005 10:14, you wrote:
> I trust that S_n = 2^((2n-1)-1)*(2^(2n-1)-1) is now clearly stated.
> The request for help and guidance was to investigate S_n modulo
> prime in general.  This inquiry was probably off the point of this
> group as it is peripheral to prime numbers and more about number
> theory.  Can anyone suggest a group more in line with such?

I don't think we mind to have this discussion. Personally I think it's much
better than the lame Goldbach proof attempts.

Anyway, what do you make of my other reply to your post?

Décio


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

#16127 From: Décio Luiz Gazzoni Filho <decio@...>
Date: Sat Feb 26, 2005 9:23 pm
Subject: An interesting complexity issue
deciogazzoni
Send Email Send Email
 
It's no secret that I'm sieving and PRP-testing `primo-factorials', integers
of the form n! +/- n# +/- 1. Initially I was PRP-testing directly, and was
kindly advised by Jens, David and Jim to do some sieving or trial-factoring
first. Mark Rodenkirch was so kind as to modify his MultiSieve program to
sieve for primofactorials, so I've been able to reach the p = 2^31 mark a few
days ago.

Not being sure that MultiSieve could handle primes > 2^32, and as a fun
exercise, I decided to write my own sieve. The algorithm was laid out by Jens
and is very simple:

1. compute fac = nmin! mod p and prim = nmin# mod p;
2. for i = nmin to nmax,
2a. test if fac +/- prim +/- 1 == 0 mod p, and report any successes;
2b. fac = (i+1)*fac mod p;
2c. if i+1 is prime, then prim = (i+1)*prim mod p.

Given the relative sizes of nmin (I'm at 13000 already) and p, this algorithm
can be improved by the use of Jens' TreeSieve/Bernstein's product tree. I
have implemented this, and even without any tuning, it's already 10+ times
faster than individually computing nmin! mod p and nfac! mod p.

Despite the fact that I implemented steps 2a, 2b and 2c in an optimized
fashion (including a very quick remaindering routine that uses a single
64-by-32-bit division instruction, even for modulos slightly larger than
2^32), they dominate the running time of the algorithm. I believe I
benchmarked with parameters nmin = 25000, nmax = 100000, p = 2^32 + 15 (the
first 33-bit prime) and the product tree step accounted for 0.8% of the
running time.

This leads me to believe that my sieving strategy is not optimal. Currently
I'm sieving from nmin = 13000 to nmax = 100000 on a separate computer from
the one who's PRP-ing the survivors. As I eventually intend to check the
entire range up to 100000, this isn't actually wasteful. However, if I were
checking the range, say, nmin = 13000 to nmax = 22000, the sieve would be
nearly ten times as fast, as step 1 of the algorithm doesn't influence the
runtime too much. This way I would eliminate candidates 10 times faster at
this range of interest, and of course PFGW would have to do less work.

Now, the problem is that I'll have to redo the nmin! mod p and nmax# mod p
calculations every time I perform the sieve for different ranges. Say I
partition the 13000 to 100000 range in 10 pieces, then I'll have to redo the
product tree calculations 10 times. The question that arises is, at which
point are the savings in PFGW time offset by having to redo step 1 of the
algorithm every time? A generic formula in terms of the relative time between
PRP tests, step 1, and steps 2a/2b/2c would be appreciated, as I'll be
continually tuning my sieve as I go.

Thanks for any help,

Décio


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

#16128 From: "Cino Hilliard" <hillcino368@...>
Date: Sun Feb 27, 2005 8:08 am
Subject: Re: Definition of "Prime Number"
hillcino368
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Jud McCranie <j.mccranie@a...>
wrote:
> At 04:20 PM 2/23/2005, thmsschuessler wrote:
>
> >   Does anyone else have a major problem with the following
> >definition of "Prime Number" that is so ubiquitions in the
> >literature?
> >
> >    "A positive integer that is divisible solely by itself and 1"?
>
> I don't except that a prime is > 1.  There are people who do have a
problem
> with that definition.

I don't like that definition either. I think -1 should be definable
as a prime number in certain contexts. Then 1 = (-1)*(-1) would be
a composite number. I left a post in another forum asking what great
infractions to mathematical truth it would be to consider 1 as
composite and there were no replies. So I assume there is no paper
or exposition or theorem or conjecture that absolutely requires 1 to
be a unit, invertable, or what ever we want to conjure to distinguish
it form prime or composite. I searched the net and found little about
the early thinkers view on this subject. I do recall reading that
Carl Sagen, Martin Gardner and others considered 1 as prime.

In Pari
(00:50) gp > factor(1)
%3 = [;]
in Maple ifactor(1);
                                      1
If we allow 1 and 0 to be composite then there is an infinity of
solutions to consecutive composite numbers x^p - y^q = 1 namely
1^p - 0^q = 1 for all p and all q <> 0.

I realize that 1 inch = 2.54 cm exactly. But it is hard in my mind
to not wonder is it 2.540000001 or 2.5399999998 or what effect
the real difference would have 10 million yrs from now? Will it
change? Maybe.

My point? Things change according to need. Necessity is the mother of
invention not convention.

Have fun,
Cino

ps.
Remember "in anger unkind words are said" Cold Cold Heart by
Hank Williams Sr. who died at the age of 29.

#16129 From: "Dr. Michael Paridon" <dr.m.paridon@...>
Date: Sun Feb 27, 2005 9:13 am
Subject: Re: [PrimeNumbers] Re: Definition of "Prime Number"
m_paridon
Send Email Send Email
 
In terms of set theory a prime is an positive integer, whos set of divisors
has exactly two elements. This is meant by "divisible solely by itself and
1", implying that "itself" and "1" are different. Remember that elements of
a set *must* differ.

"1" is not composite, as it has no prime factors. Per definitionem it is not
a prime as well.

Of course you can change definitions to your needs. Most probably the
mathematic community will not follow these changes at least for now.

Best regards

Michael Paridon



----- Original Message -----
From: "Cino Hilliard" <hillcino368@...>
To: <primenumbers@yahoogroups.com>
Sent: Sunday, February 27, 2005 9:08 AM
Subject: [PrimeNumbers] Re: Definition of "Prime Number"


>
> --- In primenumbers@yahoogroups.com, Jud McCranie <j.mccranie@a...>
> wrote:
> > At 04:20 PM 2/23/2005, thmsschuessler wrote:
> >
> > >   Does anyone else have a major problem with the following
> > >definition of "Prime Number" that is so ubiquitions in the
> > >literature?
> > >
> > >    "A positive integer that is divisible solely by itself and 1"?
> >
> > I don't except that a prime is > 1.  There are people who do have a
> problem
> > with that definition.
>
> I don't like that definition either. I think -1 should be definable
> as a prime number in certain contexts. Then 1 = (-1)*(-1) would be
> a composite number. I left a post in another forum asking what great
> infractions to mathematical truth it would be to consider 1 as
> composite and there were no replies. So I assume there is no paper
> or exposition or theorem or conjecture that absolutely requires 1 to
> be a unit, invertable, or what ever we want to conjure to distinguish
> it form prime or composite. I searched the net and found little about
> the early thinkers view on this subject. I do recall reading that
> Carl Sagen, Martin Gardner and others considered 1 as prime.
>
> In Pari
> (00:50) gp > factor(1)
> %3 = [;]
> in Maple ifactor(1);
>                                      1
> If we allow 1 and 0 to be composite then there is an infinity of
> solutions to consecutive composite numbers x^p - y^q = 1 namely
> 1^p - 0^q = 1 for all p and all q <> 0.
>
> I realize that 1 inch = 2.54 cm exactly. But it is hard in my mind
> to not wonder is it 2.540000001 or 2.5399999998 or what effect
> the real difference would have 10 million yrs from now? Will it
> change? Maybe.
>
> My point? Things change according to need. Necessity is the mother of
> invention not convention.
>
> Have fun,
> Cino
>
> ps.
> Remember "in anger unkind words are said" Cold Cold Heart by
> Hank Williams Sr. who died at the age of 29.
>
>
>
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
>       Yahoo! Groups Sponsor
>             ADVERTISEMENT
>
>
>
>
>
> --------------------------------------------------------------------------
------
> Yahoo! Groups Links
>
>   a.. To visit your group on the web, go to:
>   http://groups.yahoo.com/group/primenumbers/
>
>   b.. To unsubscribe from this group, send an email to:
>   primenumbers-unsubscribe@yahoogroups.com
>
>   c.. Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.
>
>
>

#16130 From: "chrisdarroch" <chrisdarr2@...>
Date: Sun Feb 27, 2005 7:31 pm
Subject: Three questions??
chrisdarroch
Send Email Send Email
 
Hi,

1. I am aware that people often say that the solution to Goldbach's
Conjecture would be of little or no mathematical significance outside
of itself, as it were.
However, does anyone think that the solution could be worth a Fields
Medal?

2. Why do people choose to broadcast their solutions to this problem
on the internet?

3.Does the solution have to be couched in formal mathematical language
and thus symbolism?
Would it still be acceptable if it made logical sense?
When I say acceptable, I mean, acceptable as a solution to the
mathematical community at large and the formal mathematical journals?

Chris

#16131 From: Décio Luiz Gazzoni Filho <decio@...>
Date: Sun Feb 27, 2005 7:43 pm
Subject: Re: [PrimeNumbers] Three questions??
deciogazzoni
Send Email Send Email
 
On Sunday 27 February 2005 16:31, you wrote:
> Hi,
>
> 1. I am aware that people often say that the solution to Goldbach's
> Conjecture would be of little or no mathematical significance outside
> of itself, as it were.
> However, does anyone think that the solution could be worth a Fields
> Medal?

Probably. Either if some significant new mathematics were developed, or if a
very simple proof which eluded the geniuses of the past were presented, it'd
be a notable accomplishment.

> 2. Why do people choose to broadcast their solutions to this problem
> on the internet?

Beats me. But it makes no difference, because anyone who had a chance in hell
of having a real proof of Goldbach's conjecture would submit it to a
reputable journal and not `publish' it on the internet. Each and every
`solution' you see on the internet is deeply flawed and probably written by
clueless newbies who have no idea what they're talking about.

Although, from time to time, some people do present interesting ideas and
developments, but never claiming that they solved Goldbach. Anyone who
presents a Goldbach proof is either a world-class renowned mathematician or a
crank.

You seem to be suggesting that it's stupid to publish such an important thing
on the internet. Supposing I had a proof of Goldbach, first thing I'd do is
submit it to the NMBRTHRY mailing list -- once it's `published' there, anyone
who tries to steal your work will be accused of plagiarism and suffer the
consequences.

> 3.Does the solution have to be couched in formal mathematical language
> and thus symbolism?
> Would it still be acceptable if it made logical sense?
> When I say acceptable, I mean, acceptable as a solution to the
> mathematical community at large and the formal mathematical journals?

Listen, if you think you have a Goldbach solution, you're wrong. But in the
off chance that you're not, it'll be very easy to find an expert to help you
format it for publication.

But rest assured, if you don't even know the notation, you don't know enough
mathematics to solve Goldbach.

Décio


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

#16132 From: "chrisdarroch" <chrisdarr2@...>
Date: Sun Feb 27, 2005 10:00 pm
Subject: Some more questions?!
chrisdarroch
Send Email Send Email
 
Hi,

1. Is there one man who could verify a solution to Goldbach's
Conjecture, whom the rest of the community would trust as able to do
so?
I am not assuming that such a man (or small group of men, would be
willing to do such a thing)

2. What other prizes might such a solution be likely to claim?

Chris (a member of the set of cranks?)

#16133 From: Décio Luiz Gazzoni Filho <decio@...>
Date: Mon Feb 28, 2005 1:16 am
Subject: Re: [PrimeNumbers] Some more questions?!
deciogazzoni
Send Email Send Email
 
On Sunday 27 February 2005 19:00, you wrote:
> Hi,
>
> 1. Is there one man who could verify a solution to Goldbach's
> Conjecture, whom the rest of the community would trust as able to do
> so?
> I am not assuming that such a man (or small group of men, would be
> willing to do such a thing)

Yes, there are many of them. Fortunately they have much better things to do
than check flawed proofs of Goldbach's conjecture. If you post it here, some
good soul might read it and point out the flaws in your reasoning. I hope
nobody replies, though; by reinforcing inappropriate behavior, they lead
others to believe that it is acceptable, and then everyone will have to deal
with the flawed-proofs spam that will ensue.

> 2. What other prizes might such a solution be likely to claim?

Why do you care? You don't have a valid proof.

Décio


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

#16134 From: Chris Caldwell <caldwell@...>
Date: Mon Feb 28, 2005 1:21 pm
Subject: Re: [PrimeNumbers] Some more questions?!
primemogul
Send Email Send Email
 
At 04:00 PM 2/27/2005, you wrote:
>1. Is there one man who could verify a solution to Goldbach's
>Conjecture, whom the rest of the community would trust as able to do
>so?
>I am not assuming that such a man (or small group of men, would be
>willing to do such a thing)

No.  Any one man can overlook something.  That is why the usual approach is
to a solution to an important problem is to

(a) present the proof publicly (preprint server, Internet site, conference),
(b) publish in a refereed journal
(c) wait and see.

Clay prizes I think suggest two years minimum for step three.  What
'cranks' often overlook is that the way you establish claim to a proof
is by publication.  Secrecy is your enemy.  If you got it; you publish
so everyone knows you do.

>2. What other prizes might such a solution be likely to claim?
>
>Chris (a member of the set of cranks?)

If you are working for a prize, history suggests you don't have a chance.
Those that win tend to have deeper motivations.

#16135 From: Chris Caldwell <caldwell@...>
Date: Mon Feb 28, 2005 1:34 pm
Subject: Re: [PrimeNumbers] Three questions??
primemogul
Send Email Send Email
 
At 01:43 PM 2/27/2005, Décio Luiz Gazzoni Filho wrote:
>> 2. Why do people choose to broadcast their solutions to this problem
>> on the internet?
>
>Beats me. But it makes no difference, because anyone who had a chance in hell

Depends what you mean by broadcast.  Virtually all mathematics that
will eventually be in reputable journals is first circulated by preprint;
often on the Internet.  Mathematicians often say if you are waiting
to read journals then you are two-years behind the current research.
Example: "Primes in P" was circulated on the net, gained acceptance,
was improved on repeatedly, all well before its first publication.

You circulate in any media to share what you have.  Often you get corrections
and suggestions.  Sometimes references that you missed.  (Amateurs
often miss the point of references--you must show you know how your
works fits in with the current literature.)

But if instead you mean why do they have "Goldbach Proof" websites.
That is because no one would publish their trash.  Audience is the
key--who are you writing to?

#16136 From: Chris Caldwell <caldwell@...>
Date: Mon Feb 28, 2005 1:36 pm
Subject: Re: [PrimeNumbers] Three questions??
primemogul
Send Email Send Email
 
At 01:31 PM 2/27/2005, chrisdarroch wrote:
>3.Does the solution have to be couched in formal mathematical language
>and thus symbolism?

Yes.  If you want acceptance by any community, you must present your
message in the language of that community.  Use a translator if necessary.
But always use your audience's language.

#16137 From: "Mark Underwood" <mark.underwood@...>
Date: Mon Feb 28, 2005 6:44 pm
Subject: The Music of the Primes
marku606
Send Email Send Email
 
Recently finished reading a book by Marcus du Sautoy called The Music
of the Primes.  My brother in law had given it to me on my birthday.
I had been free from my amateurish doodling habit in primes, (nearly
a year?) but the book brought back some of the primal passion and I
thought I would pay the Yahoo Prime group a visit after a long
absence!


I found the book very entertaining and hard to put down. Plenty of
excursions into the lives of many mathematicians who have tried their
hand at the Riemann Hypothesis. I didn't realize that Riemann was
also a physicist who had been working on rotating balls of liquid and
the vibrations associated with this. It turns out that Riemann zeros
and the physics of energy vibrations - notably now in quantum physics
regarding heavy nuclei - are closely related.  The book states that
it may well be a physicist who solves Reimann's hypothesis, which is
almost certainly true. And who knew that the zeros 'on the line' are
uniformly spaced, as if the 'repel' each other?  And that (if I
recall correctly), the first several billion zeros have been
confirmed to be on the line.


The book references about fifteen websites, including Chris
Caldwell's www.utm.edu/research/primes/

Marcus Du Sautoy has a website as well:

http://www.musicoftheprimes.com


Mark

#16138 From: "Mark Underwood" <mark.underwood@...>
Date: Mon Feb 28, 2005 7:31 pm
Subject: Re: prime sums
marku606
Send Email Send Email
 
Just checked, and it is alluring that the number of primes between s
(n)-n and s(n)+1 is exactly TWO for the first NINE values of n! Then
(of course!)the tenth value breaks from the pattern and dips to one.
But that is an all time low and it climbs steadily from there. So yes
your observation is true.


Mark





--- In primenumbers@yahoogroups.com, "mcnamara_gio"
<mcnamara_gio@y...> wrote:
>
> Let s(n) be sum of first n primes. a=s(n)-n and b=s(n)+1. Is it true
> that there is at least one prime p so that a<=p<=b.

#16139 From: "Cino Hilliard" <hillcino368@...>
Date: Mon Feb 28, 2005 7:38 pm
Subject: Re: Definition of "Prime Number"
hillcino368
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "Dr. Michael Paridon"
<dr.m.paridon@g...> wrote:
> In terms of set theory a prime is an positive integer, whos set of
divisors
> has exactly two elements. This is meant by "divisible solely by
itself and
> 1", implying that "itself" and "1" are different. Remember that
elements of
> a set *must* differ.

While I realize this is the convention, I have difficulty grasping
why the list of fibonacci numbers is not a set. For  in
{0,1,1,2,3,5,8,..} = {0,1,2,3,5,8,..)

And
(3,1,4,1,5,9,2,6,5,3,5,..) = (0,1,2,3,4,5,6,7,8,9)

I wonder how set theory was overlooked prior to Cantor and also
wonder if it was known, bloomed and died and that is why it was
re-invented in the presence of a specific need.

Certain things that do not speak to the man on the street eventually
will die.

It would be interesting to list those theorems regarding prime numbers
that cannot be proved without the use of modern algebra.
My guess PNT is one. But my guess also it is less than 100.

MTC
Cino

#16140 From: "Mark Underwood" <mark.underwood@...>
Date: Mon Feb 28, 2005 8:29 pm
Subject: Prime between n^2 and (n+1)^2
marku606
Send Email Send Email
 
It's true that there is at least one prime between n^2 and (n+1)^2,
although I can't recall if it has been proven.


Now n*(n+1) lies between n^2 and (n+1)^2, and we observe a tighter
result, namely that for n>1 there is always a prime between

n^2 and n*(n+1)

and also between

n*(n+1) and (n+1)^2

(This is yet another way to divide all odd primes into two groups!)


******************


Also, I was toying with a minimum  value of c such that there is
always a prime between n^c and (n+1)^c.

I'm not totally certain but pretty sure that the lowest value of c is
about 1.5683. Some lower values come very close but no cigar.


For example, there is one prime between 12^1.5683 and 13^1.5683. That
is, 53 lies between 49.258 and 55.846.


Let s(n) be the number of primes between n^1.5683 and (n+1)^1.5683.


s(n) for n=1 to n=14 is 1,2,1,1,1,2,1,2,1,1,2,1,2,1.

s(n) = 1 for 18 values of n from 1 to 100.

s(n) = 1 for 33 values of n from 1 to 737. After that s(n) is always
greater than 1.


Mark

#16141 From: Décio Luiz Gazzoni Filho <decio@...>
Date: Mon Feb 28, 2005 8:49 pm
Subject: Re: [PrimeNumbers] Prime between n^2 and (n+1)^2
deciogazzoni
Send Email Send Email
 
On Monday 28 February 2005 17:29, you wrote:
> It's true that there is at least one prime between n^2 and (n+1)^2,
> although I can't recall if it has been proven.

No, it hasn't.

>
> Now n*(n+1) lies between n^2 and (n+1)^2, and we observe a tighter
> result, namely that for n>1 there is always a prime between
>
> n^2 and n*(n+1)
>
> and also between
>
> n*(n+1) and (n+1)^2
>
> (This is yet another way to divide all odd primes into two groups!)

If this result is proved, then the above follows immediately. So it hasn't
been proven either.

>
> ******************
>
>
> Also, I was toying with a minimum  value of c such that there is
> always a prime between n^c and (n+1)^c.
>
> I'm not totally certain but pretty sure that the lowest value of c is
> about 1.5683. Some lower values come very close but no cigar.
>
>
> For example, there is one prime between 12^1.5683 and 13^1.5683. That
> is, 53 lies between 49.258 and 55.846.

By the PNT, the n-th prime is ~n log n, so it follows that all c's are
acceptable at infinity, since any power > 1 of n grows faster than n log n.
Whatever value of c that ends up being the smallest possible is just a quirk
of the start of the sequence. If you disregard the `first' primes, then any c
= 1 + e will do (for a suitable definition of `first' that's a function of
e).

> Let s(n) be the number of primes between n^1.5683 and (n+1)^1.5683.
>
>
> s(n) for n=1 to n=14 is 1,2,1,1,1,2,1,2,1,1,2,1,2,1.
>
> s(n) = 1 for 18 values of n from 1 to 100.
>
> s(n) = 1 for 33 values of n from 1 to 737. After that s(n) is always
> greater than 1.

See the PNT argument above.

Décio


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

#16142 From: Bill Krys <billkrys@...>
Date: Tue Mar 1, 2005 1:13 am
Subject: Prime # Odometer (prime # wheel) & Carmichael #
billkrys
Send Email Send Email
 
Hello,

why would a prime # odometer (Brute Force Prime seive) not seive out Carmichael
#'s when
it is composite. When the carmichael # had it's turn to come up for evaluation
it would
have the prime factors at TDC? For example, take the Carmichael number
561=11*17*3. When
561 is evaluated, 1, 3, 11 & 17 are all TDC, so it would not be added as a prime
to the
prime # odometer.

take a circle of 1 unit circumference, with a mark at top dead center (TDC).
Rotate it
360 degrees, back to TDC. Then rotate it again 360 degrees. Then add to this
circle
another circle of 2 units circumference. Rotate the first circle again 360
degrees. #1
circle is back to TDC, but #2 circle, which rotates like an odometer along with
circle
#1, but 1/2 the distance, is off TDC. As only #1 circle is back to TDC after
another 360
degrees rotation, make another circle of 3 units circumference. Rotate #1 circle
360
degrees. Now #1 and #2 circles are at TDC, so don't add the #4 circle. Rotate #1
again
through to TDC and as only #1 is at TDC and #2 and #3 are off TDC, add another
circle,
this time of 5 units circumference. Continue adding circles of P units
circumference only
when the #1 circle is at TDC and all other (prime #) circles are off TDC. You
will
generate all the primes.

Bill


=====
Bill Krys
Email: billkrys@...
Phone: 780.474.9493
Cell: (780) 995-6214
ICQ: 122663993
12112-50 Street
Edmonton, Canada T5W 3C5



__________________________________
Do you Yahoo!?
Yahoo! Mail - Easier than ever with enhanced search. Learn more.
http://info.mail.yahoo.com/mail_250

Messages 16113 - 16142 of 25181   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