--- In primenumbers@yahoogroups.com,
Devaraj Kandadai <dkandadai@...> wrote:

> In my next post I hope to furnish the proof

but then merely made the obvious remark:

> highly improbable

No progress has been reported since the posting by Max Alekseyev
http://www.mersenneforum.org/showthread.php?p=55271#post55271
> 01 Jun 05, 11:39 PM

David

True; recall that I  used the phrase  " Hope to prove"; Also  the
improbabality indicated  by me is so  great that   I can safely challenge
anyone to produce a counter example. Also note  the improbabality reasoned
has nothing to do with rarity of Mersenn primes.
Devaraj

On Mon, Jun 1, 2009 at 2:20 PM, David Broadhurst <d.broadhurst@...>wrote:

>
>
> --- In primenumbers@yahoogroups.com <primenumbers%40yahoogroups.com>,
> Devaraj Kandadai <dkandadai@...> wrote:
>
> > In my next post I hope to furnish the proof
>
> but then merely made the obvious remark:
>
> > highly improbable
>
> No progress has been reported since the posting by Max Alekseyev
> http://www.mersenneforum.org/showthread.php?p=55271#post55271
> > 01 Jun 05, 11:39 PM
>
> David
>
>
>


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

(1600616052+n*52323192)*617#+1 (n=0-9) describes a 265 digit ap10

cheers
Ken

Primality testing (1600616052+0*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 34.812%
(1600616052+0*52323192)*617#+1 is prime! (0.0186s+0.0004s)
Primality testing (1600616052+1*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 35.040%
(1600616052+1*52323192)*617#+1 is prime! (0.0166s+0.0004s)
Primality testing (1600616052+2*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 34.471%
(1600616052+2*52323192)*617#+1 is prime! (0.0193s+0.0005s)
Primality testing (1600616052+3*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 35.267%
(1600616052+3*52323192)*617#+1 is prime! (0.0231s+0.0009s)
Primality testing (1600616052+4*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 35.267%
(1600616052+4*52323192)*617#+1 is prime! (0.0194s+0.0010s)
Primality testing (1600616052+5*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 34.432%
(1600616052+5*52323192)*617#+1 is prime! (0.0183s+0.0009s)
Primality testing (1600616052+6*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 34.886%
(1600616052+6*52323192)*617#+1 is prime! (0.0224s+0.0010s)
Primality testing (1600616052+7*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 34.659%
(1600616052+7*52323192)*617#+1 is prime! (0.0191s+0.0011s)
Primality testing (1600616052+8*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 35.000%
(1600616052+8*52323192)*617#+1 is prime! (0.0204s+0.0009s)
Primality testing (1600616052+9*52323192)*617#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 34.545%
(1600616052+9*52323192)*617#+1 is prime! (0.0184s+0.0009s)

Ken Davis wrote:
> (1600616052+n*52323192)*617#+1 (n=0-9) describes a 265 digit ap10

Congratulations on continuing your AP record sweep, now AP4 to AP10.
http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated.

--
Jens Kruse Andersen

Hi Jens,

Thanks for the congrats
I think I'll move on to something else for a while.
My method is not well suited for searches above ap10
Poisson was kind to me this time

Details of this one were
Newpgen sieved 1e9 to 2e9
pfgw yielded 18,894,798 prps
C++ AP Search program (combined total of 2700 ghz hrs over 5 PCs)
Resulted in
71214 ap7s
1133 ap8s
14 ap9s
0 ap10s
Ran pfgw script files to extend AP7s, 8 and 9's (up and down) where appropriate
Resulted in additional
409 ap8s
11 ap9s
1 ap10

cheers
Ken

On the other hand  all the factors of  a Carmichael Number  can be Mangammal
primes (see A123239-OEIS); example 29341. It is inteesting to note that
Maxal had proved(in Mersenneforum.org) that Mersenne primes and  Mangammal
primes are almost disjoint sets -3 is the only common member.

Devaraj


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

In my presentation of “Minimum Universal exponent generalisation of Fermat's
theorem” at the Hawaii Intl conference in 2006 I had stated that 31 is a
factor of the following and that 127, 157 and 8191 are not factors :



2^97500641752017987211 + 29.


Can anyone verify this by PFGW pl?
Devaraj


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

Devaraj Kandadai wrote:
> In my presentation of “Minimum Universal exponent generalisation of Fermat's
> theorem” at the Hawaii Intl conference in 2006 I had stated that 31 is a
> factor of the following and that 127, 157 and 8191 are not factors :
>
> 2^97500641752017987211 + 29.
>
> Can anyone verify this by PFGW pl?

    I didn't use PFGW, but it's easy to test.  In short, your statement
is correct.  The two smallest factors are 31 and 817469483.  If you want
to exhaustively find more factors, the following simple program should help:

Frink program below:  ( http://futureboy.us/frinkdocs/ )
--------------------------------------------------

test[p] := (modPow[2,97500641752017987211,p]+29) mod p

n = 1
do
{
    n = nextPrime[n]
    if test[n] == 0
       print[n + " "]
} while true

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

    See the thread in this group 'Checking Large "Prime Numbers"?'
beginning on 2006-05-08 for related GP/PARI scripts that can be modified
to find other factors.

--
    Alan Eliasen
    eliasen@...
    http://futureboy.us/

Thank you very much;  my knowledge  of programming is limited to some
elementary programming in pari. My approach is purely mathematical. By this
I can find some factors and non-factors of very large numbers  with an
exponential shape (like the number I had asked about).
Thanking u once again,
Devaraj



On Tue, Jun 2, 2009 at 1:35 PM, Alan Eliasen <eliasen@...> wrote:

>  Devaraj Kandadai wrote:
> > In my presentation of “Minimum Universal exponent generalisation of
> Fermat's
> > theorem” at the Hawaii Intl conference in 2006 I had stated that 31 is a
> > factor of the following and that 127, 157 and 8191 are not factors :
> >
> > 2^97500641752017987211 + 29.
> >
> > Can anyone verify this by PFGW pl?
>
>   I didn't use PFGW, but it's easy to test.  In short, your statement
> is correct.  The two smallest factors are 31 and 817469483.  If you want
> to exhaustively find more factors, the following simple program should
> help:
>
> Frink program below:  ( http://futureboy.us/frinkdocs/ )
> --------------------------------------------------
>
> test[p] := (modPow[2,97500641752017987211,p]+29) mod p
>
> n = 1
> do
> {
>   n = nextPrime[n]
>   if test[n] == 0
>      print[n + " "]
> } while true
>
> -----------------------------------------------------
>
>   See the thread in this group 'Checking Large "Prime Numbers"?'
> beginning on 2006-05-08 for related GP/PARI scripts that can be modified
> to find other factors.
>
> --
>   Alan Eliasen
>   eliasen@...
>   http://futureboy.us/
>


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

Hi All,

Tom Wu wrote:
>The CHG proof of (89^11971-1)/88 at 25.965% took about
>284 AMD64 GHZ-days.

David Broadhurst wrote:
>Wow!

Phil Carmody wrote:
>Seconded.

I third that "wow".  I have updated
http://www.primes.viner-steward.org/andy/titans.html and
http://www.primes.viner-steward.org/andy/annual.html

Best Regards,
Andy Steward

Factor Triangle

  0
  1    0
  4    3    0
  9    8    5    0
16   15   12    7    0
25   24   21   16    9    0
36   35   32   27   20   11

To construct the triangle:

Sequence number the rows, starting with zero.
Sequence number the columns, starting with zero.

Column zero is the square of row number.
In row t,  cell (t,s) = cell(t,s-1) - cell(s,s-1)

cell(2,1) = cell(2,0) - cell(1,0) ;  3 = 4 - 1
cell(2,2) = cell(2,1) - cell(2,1) ;  0 = 3 - 3
cell(3,1) = cell(3,0) - cell(1,0) ;  8 = 9 - 1
cell(3,2) = cell(3,1) - cell(2,1) ;  5 = 8 - 3
etc

Study of the internal properties of this triangle might
or might not be of use for deriving factor algorithms.

An example of an internal property:



  0
  1    0
  4    3    0
  9    8    5    0
16   15   12    7    0
25   24   21   16    9    0
36   35   32   27   20   11


35 = 35 + 0 = 32 + 3 = 27 + 8 = 20 + 15 = 11 + 24

32 = 32 + 0 = 27 + 5 = 20 + 12 = 11 + 21

27 = 27 + 0 = 20 + 7 = 11 + 16

20 = 20 + 0 = 11 + 0

cell(t,s) = cell(t,b) + cell(b,s)  for s < b < t.

Kermit

The corners of the Ulam Spiral are

4n^2-2n+1 (NE)

4n^2+1 (NW)

4n^2+2n+1 (SW)  and

4n^2-4n+2 (SE) [this is always divisible by 2]

The first one produces good primes, and the line parallel to it

4n^2-2n-1  produces even more

11, 29, (55), 89, 131, 181, 239, ...

Milton L. Brown
miltbrown@...

For those interested, exhaustive searching has
verified the 2nd HL conjecture for all widths up
to 2529 integers.

The bounds for the first contradiction are now
2529 < y <= 3159.

Note that 2529 is a crossover width where 369 primes
can be packed in an interval of 2529 integers and the
number of primes <=2529 is 369.

Also, the next crossover at 2655 has been verified that
no more than 383 primes can exist in an interval of 2655
integers.

The known crossovers are:
1417 at 223 - verified as maximum density
2529 at 369 - verified as maximum density
2655 at 383 - verified as maximum density
3153 at 446 - pattern does exist
3157 at 446 - pattern does exist

then the violation
3159 at 447 - pattern does exist

The database now contains about 44.8 million unique
patterns for widths up to 41741.

HOME page: http://www.opertech.com/primes/k-tuples.html
  Extremes: http://www.opertech.com/primes/trophycase.html
   Updates: http://www.opertech.com/primes/updates.html
      Plot: http://www.opertech.com/primes/trophy.bmp
Variation: http://www.opertech.com/primes/varcount.bmp

Thomas J Engelsma

In fact if n is the exponent in 2^n + 29, any value of n ending in  1 or 6
is divisible by 31.  This has something to do with group theory.
Devaraj

On Tue, Jun 2, 2009 at 1:35 PM, Alan Eliasen <eliasen@...> wrote:

>  Devaraj Kandadai wrote:
> > In my presentation of “Minimum Universal exponent generalisation of
> Fermat's
> > theorem” at the Hawaii Intl conference in 2006 I had stated that 31 is a
> > factor of the following and that 127, 157 and 8191 are not factors :
> >
> > 2^97500641752017987211 + 29.
> >
> > Can anyone verify this by PFGW pl?
>
>   I didn't use PFGW, but it's easy to test.  In short, your statement
> is correct.  The two smallest factors are 31 and 817469483.  If you want
> to exhaustively find more factors, the following simple program should
> help:
>
> Frink program below:  ( http://futureboy.us/frinkdocs/ )
> --------------------------------------------------
>
> test[p] := (modPow[2,97500641752017987211,p]+29) mod p
>
> n = 1
> do
> {
>   n = nextPrime[n]
>   if test[n] == 0
>      print[n + " "]
> } while true
>
> -----------------------------------------------------
>
>   See the thread in this group 'Checking Large "Prime Numbers"?'
> beginning on 2006-05-08 for related GP/PARI scripts that can be modified
> to find other factors.
>
> --
>   Alan Eliasen
>   eliasen@...
>   http://futureboy.us/
>


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

A QUESTION ABOUT PROGRAMMING


This pertains to my post: “An indirect primality test of......”


  For the sake of this example let x = 1000 i.e. The prime suspect is 1000^2
+ 1.


My operation in pari would be


if(Mod(1000^2+1,2)= =1, print(“It is an integer”)


if(Mod(1000^2+1,5)= =2,print(“It is an integer”)


if(Mod(1000^2+1,10)= =3,print(“It is an integer”)


.if(Mod(1000^2+1,17))= = 4,, print(“It is an integer”) and so on.


I can program the above as follows:


{p(k)=if (Mod(1000^2+1,k^2+1)= =k, print(“It is an integer”))}


for(k=1,500,print(p(k)))


Q: Is there a better program?


My knowledge of programming is elementary.

Devaraj


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

--- In primenumbers@yahoogroups.com, Devaraj Kandadai <dkandadai@...> wrote:

> My operation in pari would be
> if(Mod(1000^2+1,2)= =1, print("It is an integer")

The idea is to avoid large numbers.
If you write  Mod( big^something ...)
you did not avoid anything.
If you write  Mod( big, m )^something
then you create "big" as "an element of Z/mZ"
(and thus "smaller than" m)

The exponentiation is not a problem even for large exponents, since it can be
done in O(log(exponent)) steps.

When you do the calculation "in Z/mZ", then the number becomes never larger than
m, and so the calculation is very fast.


> .if(Mod(1000^2+1,17))= = 4,, print("It is an integer") and so on.

should be

if( Mod(1000,17)^2+1==4, print(integer))

well, actually this works since (I think)  a==4 is transformed into
  a-4 = 0,
and Mod(x,y)+z  is transformed into Mod(x+z,y)


> {p(k)=if (Mod(1000^2+1,k^2+1)= =k, print("It is an integer"))}
> for(k=1,500,print(p(k)))
>
> Q: Is there a better program?

yes:
{p(k)=if (Mod(1000,k^2+1)^2 + 1 == k, print("It is an integer"))}

> My knowledge of programming is elementary.

This is more "conceptual" than "programming", the idea being to work in Z/nZ
right from the start, and not to do the reduction mod n
only at the very end, when numbers may have grown huge.

Maximilian

I've been using Google Talk and thought you might like to try it out.
We can use it to call each other for free over the internet. Here's an
invitation to download Google Talk. Give it a try!

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

Devaraj Kandadai wants to stay in better touch using some of Google's
coolest new
products.

If you already have Gmail or Google Talk, visit:
http://mail.google.com/mail/b-39bb0cb899-7bb333dec5-f5147b9b7d0fa13a
You'll need to click this link to be able to chat with Devaraj Kandadai.

To get Gmail - a free email account from Google with over 2,800 megabytes of
storage - and chat with Devaraj Kandadai, visit:
http://mail.google.com/mail/a-39bb0cb899-7bb333dec5-f5147b9b7d0fa13a

Gmail offers:
- Instant messaging right inside Gmail
- Powerful spam protection
- Built-in search for finding your messages and a helpful way of organizing
   emails into "conversations"
- No pop-up ads or untargeted banners - just text ads and related information
   that are relevant to the content of your messages

All this, and its yours for free. But wait, there's more! By opening a Gmail
account, you also get access to Google Talk, Google's instant messaging
service:

http://www.google.com/talk/

Google Talk offers:
- Web-based chat that you can use anywhere, without a download
- A contact list that's synchronized with your Gmail account
- Free, high quality PC-to-PC voice calls when you download the Google Talk
   client

Gmail and Google Talk are still in beta. We're working hard to add new features
and make improvements, so we might also ask for your comments and suggestions
periodically. We appreciate your help in making our products even better!

Thanks,
The Google Team

To learn more about Gmail and Google Talk, visit:
http://mail.google.com/mail/help/about.html
http://www.google.com/talk/about.html

(If clicking the URLs in this message does not work, copy and paste them into
the address bar of your browser).

Jens Kruse Andersen's very nice "Primes in Arithmetic Progression Records" page
at:
http://users.cybercity.dk/~dsl522332/math/aprecords.htm
lists "The largestknown AP-k", for k=3..25.

The number of digits range from 137514 (k=3) to 17 (k=25).

I have played around with simple formulae to smoothly interpolate this huge
range of sizes, and offer the following, which gives a surprisingly close fit
over the whole range.

The "score" for an AP-k with d digits is defined to be:
s = (k+3)*log(d)

Inserting the latest records from Jens's page gives this table:-

k  d   log(d)  s=(k+3)*log(d)
-  -   ------  --------------
3  137514 11.831  70.989
4  11961  9.3894  65.726
5  7009   8.8550  70.840
6  1606   7.3815  66.434
7  1290   7.1624  71.624
8  1057   6.9632  76.595
9  425    6.0521  72.625
10 265    5.5797  72.536
11 195    5.2730  73.822
12 173    5.1533  77.299
13 78     4.3567  69.707
14 69     4.2341  71.980
15 48     3.8712  69.682
16 38     3.6376  69.114
17 29     3.3673  67.346
18 29     3.3673  70.713
19 27     3.2958  72.508
20 21     3.0445  70.024
21 20     2.9957  71.898
22 19     2.9444  73.611
23 19     2.9444  76.555
24 17     2.8332  76.497
25 17     2.8332  79.330

The average score is 72.063, and the median is 71.898 (for k=21).

Putting c=71.898, the values of d = exp(c/(k+3)) giving that same score would be
as follows:-

k  d
-  -
3  160011.345
4  28886.8819
5  8000.42545
6  2947.36452
7  1325.83801
8  689.648341
9  400.014181
10 252.299124
11 169.961413
12 120.686950
13 89.4450973
14 68.6687430
15 54.2896355
16 43.9962878
17 36.4120586
18 30.6831697
19 26.2611565
20 22.7826664
21 20.0003545
22 17.7417390
23 15.8839266
24 14.3376492
25 13.0369250

Comparison of these 2 tables indicate that, in terms of this fit, the k=25
record (79.330) fills the top spot, which seems reasonable (it is indeed very
impressive!),
while Jeff Anderson-Lee's record for k=12 (77.299) and Ken Davis's for k=8
(76.595) take the next 2 places.
Further corroboration that my measure is on the right track is that Ken's record
heads the table of "Weighted Record Primes of this Type" on Chris Caldwell's
"Arithmetic Progressions of Primes" page
http://primes.utm.edu/top20/page.php?id=14

At the other end of the scale, Ken's records for k=4 (65.726) and k=6 (66.434)
look rather weak.
Back in 2006 I held both these, and as a result of this little exercise have
decided to have a go at a major upgrade of the k=6 record.
The PFGW run will take 7 more weeks (at 3.79 GHz) to finish.
I'm also attacking the 3rd-weakest (k=17).

Who wants to have a crack at some of the other ("weaker") ones?

-Mike Oakes

I have extended the Ulam Spiral by starting with
a prime number (at the center). Then a large
number of primes are on the NW corner values.
For 101 at the center yields the numbers:

101,103,113,131,157,191,233,283,(341),(407),(481),
563,653,751,857,971,1093,1223,1361,(1507)

yielding 16/20 primes

The formula is 4n^2-10n+107

Milton L. Brown
miltbrown@...

--- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:
>
> The "score" for an AP-k with d digits is defined to be:
> s = (k+3)*log(d)
[snip]

I retract yesterday's post.

Further reflection and numerical experiments have shown that using "(k+3)" is no
better than using "(k+4)",
and it is the latter that has a theoretical motivation, as follows.

A typical search method is to sieve and then test for primality a block of N
numbers of the form m*p#+1,
for some fixed prime p and N consecutive values of m.
If the numbers are of size d digits, then by PNT a fraction of about 1/d of the
numbers will be prime.
In this block of N, there will be approximately (N/d) primes, and 0.5*(N/d)^2
prime pairs.
Considering each of these pairs as the start of a potential AP-k, the number of
AP-k's will be of order N^2/d^k.
For a search to get an even chance of finding an AP-k, we must have N^2/d^k of
order 1, i.e. N=d^(k/2).
To perform a primality test on a number of size d digits is of difficulty
approximately d^2 (neglecting terms of order log(d)).
The amount of computation involved in finding an AP-k is therefore of order
N*d^2=d^(k/2+2).
The log of this (if we multiply by 2) is (k+4)*log(d).

We therefore define the "score" for an AP-k with d digits to be
s = (k+4)*log(d)

NB If factors of order 1 are neglected, this coincides with Chris Caldwell's
definition of weight on his "Arithmetic Progressions of Primes" page
http://primes.utm.edu/top20/page.php?id=14
where he presents a detailed theoretical justification, with references, for the
algebraic expression he uses.

Inserting the latest records from Jens's page
http://users.cybercity.dk/~dsl522332/math/aprecords.htm
gives this table:-

k  d   log(d)  s=(k+4)*log(d)
-  -   ------  --------------
3  137514 11.831  82.817
4  11961  9.3894  75.115
5  7009   8.8550  79.695
6  1606   7.3815  73.815
7  1290   7.1624  78.786
8  1057   6.9632  83.558
9  425    6.0521  78.677
10 265    5.5797  78.116
11 195    5.2730  79.095
12 173    5.1533  82.453
13 78     4.3567  74.064
14 69     4.2341  76.214
15 48     3.8712  73.553
16 38     3.6376  72.752
17 29     3.3673  70.713
18 29     3.3673  74.081
19 27     3.2958  75.803
20 21     3.0445  73.068
21 20     2.9957  74.893
22 19     2.9444  76.554
23 19     2.9444  79.499
24 17     2.8332  79.330
25 17     2.8332  82.163

The mean score is 77.166, the median is 76.554 (for k=22).
The range of values is 70.713..82.817, giving a spread of 12.104,
which is better than the spread with "(k+3)" of 13.604.
This new fit has also a smaller relative variance: 0.002085 compared with
0.002258.

Putting c=76.554, the values of d = exp(c/(k+4)) giving that same score would be
as follows:-

k  d(theor.)  d(actual)
-  ---------  ---------
3  56178.293  137514
4  14317.674  11961
5  4944.3461  7009
6  2112.0198  1606
7  1053.0590  1290
8  589.63282  1057
9  360.96075  425
10 237.01960  265
11 164.61345  195
12 119.65648  173
13 90.303523  78
14 70.316044  69
15 56.213554  48
16 45.956716  38
17 38.299183  29
18 32.450871  29
19 27.894646  27
20 24.282356  21
21 21.373674  20
22 18.998967  19
23 17.036078  19
24 15.395441  17
25 14.010305  17

The rank-ordering is considerably different than when "(k+3)" was used in the
formula. The new ordering is:-

rank k  d      s=(k+4)*log(d)
---- -  -      --------------
1    8  1057   83.558  was 3rd
2    3  137514 82.817  was 14th
3    12 173    82.453  was 2nd
4    25 17     82.163  was 1st
5    5  7009   79.695  was 15th
6    23 19     79.499
7    24 17     79.330
8    11 195    79.095
9    7  1290   78.786  was 13th
10   9  425    78.677
11   10 265    78.116
12   22 19     76.554  MEDIAN
13   14 69     76.214
14   19 27     75.803
15   4  11961  75.115  was 23rd
16   21 20     74.893
17   18 29     74.081
18   13 78     74.064
19   6  1606   73.815  was 22nd
20   15 48     73.553
21   20 21     73.068
22   16 38     72.752
23   17 29     70.713

The main changes are that the records with smaller k have moved up in the
rankings - for k=3, dramatically so!
The k=4 and k=6 records don't now look quite so relatively weak (which should
please Ken:-)

The rank order now agrees with Chris's in his above-cited page, for d > 1000
(the lower limit for inclusion in his table).

Mike

Hi Mike,
You're right I like the second ranking better ;-)

  rank k  d      s=(k+4)*log(d)
  ---- -  -      --------------
  1    8  1057   83.558
  5    5  7009   79.695
  9    7  1290   78.786
  10   9  425    78.677
  11   10 265    78.116
  15   4  11961  75.115
  19   6  1606   73.815

Having found the above APs I tend to agree with your difficulty ranking. The AP8
was definitely the hardest.

cheers
Ken

--- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "Mike Oakes" <mikeoakes2@> wrote:
> >
> > The "score" for an AP-k with d digits is defined to be:
> > s = (k+3)*log(d)
> [snip]
>
> I retract yesterday's post.
>
> Further reflection and numerical experiments have shown that using "(k+3)" is
no better than using "(k+4)",
> and it is the latter that has a theoretical motivation, as follows.
>
> A typical search method is to sieve and then test for primality a block of N
numbers of the form m*p#+1,
> for some fixed prime p and N consecutive values of m.
> If the numbers are of size d digits, then by PNT a fraction of about 1/d of
the numbers will be prime.
> In this block of N, there will be approximately (N/d) primes, and 0.5*(N/d)^2
prime pairs.
> Considering each of these pairs as the start of a potential AP-k, the number
of AP-k's will be of order N^2/d^k.
> For a search to get an even chance of finding an AP-k, we must have N^2/d^k of
order 1, i.e. N=d^(k/2).
> To perform a primality test on a number of size d digits is of difficulty
approximately d^2 (neglecting terms of order log(d)).
> The amount of computation involved in finding an AP-k is therefore of order
N*d^2=d^(k/2+2).
> The log of this (if we multiply by 2) is (k+4)*log(d).
>
> We therefore define the "score" for an AP-k with d digits to be
> s = (k+4)*log(d)
>
> NB If factors of order 1 are neglected, this coincides with Chris Caldwell's
definition of weight on his "Arithmetic Progressions of Primes" page
> http://primes.utm.edu/top20/page.php?id=14
> where he presents a detailed theoretical justification, with references, for
the algebraic expression he uses.
>
> Inserting the latest records from Jens's page
> http://users.cybercity.dk/~dsl522332/math/aprecords.htm
> gives this table:-
>
> k  d   log(d)  s=(k+4)*log(d)
> -  -   ------  --------------
> 3  137514 11.831  82.817
> 4  11961  9.3894  75.115
> 5  7009   8.8550  79.695
> 6  1606   7.3815  73.815
> 7  1290   7.1624  78.786
> 8  1057   6.9632  83.558
> 9  425    6.0521  78.677
> 10 265    5.5797  78.116
> 11 195    5.2730  79.095
> 12 173    5.1533  82.453
> 13 78     4.3567  74.064
> 14 69     4.2341  76.214
> 15 48     3.8712  73.553
> 16 38     3.6376  72.752
> 17 29     3.3673  70.713
> 18 29     3.3673  74.081
> 19 27     3.2958  75.803
> 20 21     3.0445  73.068
> 21 20     2.9957  74.893
> 22 19     2.9444  76.554
> 23 19     2.9444  79.499
> 24 17     2.8332  79.330
> 25 17     2.8332  82.163
>
> The mean score is 77.166, the median is 76.554 (for k=22).
> The range of values is 70.713..82.817, giving a spread of 12.104,
> which is better than the spread with "(k+3)" of 13.604.
> This new fit has also a smaller relative variance: 0.002085 compared with
0.002258.
>
> Putting c=76.554, the values of d = exp(c/(k+4)) giving that same score would
be as follows:-
>
> k  d(theor.)  d(actual)
> -  ---------  ---------
> 3  56178.293  137514
> 4  14317.674  11961
> 5  4944.3461  7009
> 6  2112.0198  1606
> 7  1053.0590  1290
> 8  589.63282  1057
> 9  360.96075  425
> 10 237.01960  265
> 11 164.61345  195
> 12 119.65648  173
> 13 90.303523  78
> 14 70.316044  69
> 15 56.213554  48
> 16 45.956716  38
> 17 38.299183  29
> 18 32.450871  29
> 19 27.894646  27
> 20 24.282356  21
> 21 21.373674  20
> 22 18.998967  19
> 23 17.036078  19
> 24 15.395441  17
> 25 14.010305  17
>
> The rank-ordering is considerably different than when "(k+3)" was used in the
formula. The new ordering is:-
>
> rank k  d      s=(k+4)*log(d)
> ---- -  -      --------------
> 1    8  1057   83.558  was 3rd
> 2    3  137514 82.817  was 14th
> 3    12 173    82.453  was 2nd
> 4    25 17     82.163  was 1st
> 5    5  7009   79.695  was 15th
> 6    23 19     79.499
> 7    24 17     79.330
> 8    11 195    79.095
> 9    7  1290   78.786  was 13th
> 10   9  425    78.677
> 11   10 265    78.116
> 12   22 19     76.554  MEDIAN
> 13   14 69     76.214
> 14   19 27     75.803
> 15   4  11961  75.115  was 23rd
> 16   21 20     74.893
> 17   18 29     74.081
> 18   13 78     74.064
> 19   6  1606   73.815  was 22nd
> 20   15 48     73.553
> 21   20 21     73.068
> 22   16 38     72.752
> 23   17 29     70.713
>
> The main changes are that the records with smaller k have moved up in the
rankings - for k=3, dramatically so!
> The k=4 and k=6 records don't now look quite so relatively weak (which should
please Ken:-)
>
> The rank order now agrees with Chris's in his above-cited page, for d > 1000
(the lower limit for inclusion in his table).
>
> Mike
>

VERIFICATION II


The following are lists of some of the a) factors and b) non-factors of



2^(2^521-1) + 61


a) 3 and 7


b)5, 13, 23, 11, 11,31, 317, 191, 19, 37, 131, 353, 9371, 43711, 229, 29,
41, 33827, 8849, 119839, 2796223, 1525207 .............


They are given in the order of appearance.


This may pl be verified.


A.K. Devaraj


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

Hi Mike,

Having now "carefully" read your posting and while still thinking that the end
result gives a good indication of difficulty I have questions about the
statement "If the numbers are of size d digits, then by PNT a fraction of about
1/d of the numbers will be prime. If the numbers are of size d digits, then by
PNT a fraction of about 1/d of the numbers will be prime"

Firstly doesn't the prime number theorem that for a number N the  probability of
a random number N being prime is
~= 1/log(N)
~= 1/dlog(10)
so for a random 265 digit number the chance of it being prime would be
  ~= 1/610.185

Secondly using p# further increases this probability.
= (1/(dlog(10))*(1/2*2/3*4/5*....*p-1/p))
So for a 265 digit number of the form 617#+1 the probability would be
= 1/53.12 (not 1/265)
As a practical comparison for the ap10 mentioned (with 265 digits) I found
18,894,798 prps out of 1,000,000,000 candidates meaning that 1/52.92 numbers
were prps
With the 1057 digit numbers used for the ap8 ~= 1/174 were prps

Does this affect the rest of your calculations?

Cheers
Ken

? for(n=1,30,print([n,ceil(sqrtn(n^2,2))]))
[1, 1]
[2, 2]
[3, 4]
[4, 4]
[5, 5]
[6, 7]
[7, 8]
[8, 8]
[9, 10]
[10, 11]
[11, 11]
[12, 12]
[13, 13]
[14, 15]
[15, 16]
[16, 16]
[17, 17]
[18, 19]
[19, 20]
[20, 21]
[21, 21]
[22, 22]
[23, 23]
[24, 24]
[25, 25]
[26, 26]
[27, 28]
[28, 29]
[29, 30]
[30, 31]

? for(n=1,30,print([n,floor(sqrtn(n^2,2))]))
[1, 1]
[2, 2]
[3, 3]
[4, 4]
[5, 5]
[6, 6]
[7, 7]
[8, 8]
[9, 9]
[10, 10]
[11, 10]
[12, 11]
[13, 13]
[14, 14]
[15, 15]
[16, 16]
[17, 17]
[18, 18]
[19, 19]
[20, 20]
[21, 21]
[22, 21]
[23, 23]
[24, 23]
[25, 25]
[26, 26]
[27, 27]
[28, 28]
[29, 29]
[30, 30]

Is it a problem with the sqrtn(x,n) (n-th root of x)? Or wih floor and ceil
functions?

I wanted to search if some numbers were perfect powers using the trick:
If(floor(sqrt(x,n))==ceil(sqrt(x,n)),.....

and trying to use n (the n-th root ) as a variable in a for loop to look for
many possible n-roots if this was possible technically.


What is the way to solve my problem to detect if some kind of numbers are
perfect powers?


? for(n=1,30,print([n,floor(sqrtn(n^3,3))]))
[1, 1]
[2, 2]
[3, 3]
[4, 4]
[5, 5]
[6, 6]
[7, 7]
[8, 8]
[9, 9]
[10, 9]
[11, 10]
[12, 11]
[13, 13]
[14, 14]
[15, 15]
[16, 16]
[17, 16]
[18, 17]
[19, 19]
[20, 19]
[21, 21]
[22, 21]
[23, 23]
[24, 23]
[25, 25]
[26, 26]
[27, 27]
[28, 28]
[29, 29]
[30, 30]

--- In primenumbers@yahoogroups.com, "Paul Underwood" <paulunderwood@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "Paul Underwood" <paulunderwood@> wrote:
>
> As usual, a few typos:
> I meant of course discriminant where I wrote determinant.
> I wrote L(Y)-L(X) whereas I should have written L(X)-L(Y)
> and
>
> > Fortunately for computation speed, jacobi(D(X),n)==-1 implies "X" is a NQR.
>
> should read "...implies "D(X)" is a NQR."
>
> Paul
>
> > I will here derive a 5-selfridge composite test from another 6-selfridge
one. Whether any are proper primailty tests is yet unknown. I will endeavour to
use capital letters to represent 2-by-2 matrices and lower case letters for
scalars. Note that in general A*B is not the same B*A, as matrices do not always
commute under multiplication.
> >
> > Consider the classic Fermat Probable Prime Test (PRP): x^n==x (mod n).
Cleary, the same is true for the matrix:
> >
> > [x,0;0,x]
> >
> > This martix may be decomposed into:
> >
> > [x,-1;1,0]-[0,-1;1,-x]
> >
> > The two matrices in this expression behave the same under individual
exponentiation if we take into account the symmetry in the postions and the
signs of the elements of the matrices. Let the first matrix be:
> >
> > X==[x,-1;1,0]
> >
> > This matrix has the characteristic equation:
> >
> > X^2-x*X+1==0
> >
> > with determinant:
> >
> > D(X)=x^2-4
> >
> > For for prime, p, any non-quadratic residue (NQR) "D(X)" will map:
> >
> > X^n==1/X (mod p)
> >
> > Fortunately for computation speed, jacobi(D(X),n)==-1 implies "X" is a NQR.
> >
> > Note that D(X)=(x-2)*(x+2). When x is either +2 or -2 then D(X)=0. Without
loss of generality assume the zero is given by x=-2. NB: there is another such
characteristic equation with this zero for its determinant. It is Y^2-y*Y+1=0
with y=x+4 and therefore D(Y)=(x+2)*(x+6). The gist of the initial basic
6-selfridge test is:
> >
> > Find any x and y=x+4 such that D(X) and D(Y) are NQR and after check:
> > x^n==x (mod n)
> > y^n==y (mod n)
> > X^n==1/X (mod n)
> > Y^n==1/Y (mod n)
> >
> > (I can can quickly enumerate n<=11, and check gcd(n,15)==1 for a full cover
of n \in N.)
> >
> > I can reduce this by 1 selfridge. Let:
> >
> > L(X)==X-x (mod n)
> > L(Y)==Y-y (mod n)
> >
> > The new test is done by finding NQR D(X) and D(Y) with:
> >
> > x+4-y==0 (mod n)
> >
> > and checking "term-wise" the nth powers of:
> >
> > X+4-Y==L(Y)-L(X) (mod n)
> >
> > by checking individually:
> >
> > 4^n==4 (mod n)
> > X^n==1/X (mod n)
> > Y^n==1/Y (mod n)
> >
> > Paul^(1-eps)
> >
>

This is a follow-up, but taking y=x+2. Redefine:

x=a-1
y=a+1

where "a" is the mean of "x" and "y".

Redefine the matrices:

X=[a-1,-1;1,0]
Y=[a+1,-1;1,0]

and

L(X)=X-x
L(Y)=Y-y

The composite test is to choose any "a" such that jacobi(D,n)==-1 for both:

D(X)=(a-1)^2-4
D(Y)=(a+1)^2-4

and check:

2^n==2 (mod n)
X^n==1/X (mod n)
Y^n==1/Y (mod n)

This will satisfy:

X^n-L(X)^n+2^n==Y^n-L(Y)^n (mod n)

I also need to do two gcd tests. The first is gcd(210,n), to cover N. The second
is with "a" because if gcd(a,n)==d with d>1, then:

X==[-1,-1;1,0] (mod d)
Y==[+1,-1;1,0] (mod d)

and so the exponent tests on X and Y would be identical due to symmetry,
breaking the "5-selfridge rule".

Note that "x" is a zero of D(Y) and "y" is a zero of D(X).

I plan to run some tests on Richard Pinch's readily available list of fermat
2-PSPs, checking the composite test by the gcd tests and two lucas V sequences
-- the traces of the matrices.

Paul

ps. apologies for not saying quadratic non-residue instead of non quadratic
residue.

> What is the way to solve my problem to detect if some kind of numbers are
> perfect powers?

Perhaps ispower() is what you're looking for?

Peter

--
[Name] Peter Kosinar   [Quote] 2B | ~2B = exp(i*PI)   [ICQ] 134813278

Following are the ratios of primes to total

for Extended Ulam Spiral 107:

30  .8

40  .78

50  .72

60  .67

70  .63

80  .65

90  .63

100 .64

110 .63

Does this remain above 50% ?

I would call {n =1..., 4n^2-10n+107} a dense set of primes?

Milton L. Brown

miltbrown@...

I had  requested Ken (Kradenken)  to test whether  2^(3^53)  +  99   is
eactly divisible by  107 or not.  He replied that the number is too big for
any computer.  Do you agree?

Devaraj


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

--- On Tue, 6/9/09, Devaraj Kandadai <dkandadai@...> wrote:
> I had  requested Ken (Kradenken)  to test whether  2^(3^53) + 99   is
> eactly divisible by  107 or not.  He replied that
> the number is too big for any computer.  Do you agree?

If by "the number" you mean 2^(3^53)+99, then clearly it isn't too big for any
computer as it can trivially be represented using only 9 characters. It's binary
or decimal expansion is too big, but no-one's asking for its binary or decimal
expansion, so that's irrelevant.

To test whether it's divisible by 107 is trivial also, as 2^phi(107) == 1 (mod
107). So reduce 3^53 modulo phi(107):

? Mod(2,107)^lift(Mod(3,eulerphi(107))^53)+99
Mod(0, 107)

So indeed, it is divisible by 107.

Phil