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 23295 - 23324 of 25086   Oldest  |  < Older  |  Newer >  |  Newest
Messages: Show Message Summaries Sort by Date ^  
#23295 From: "mikeoakes2" <mikeoakes2@...>
Date: Sat Oct 1, 2011 10:18 am
Subject: Re: A question
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@> wrote:
> >
> > Let A be the least set of natural numbers with the following two properties:
> > (i) the number 1 belongs to A;
> > (ii) whenever x belongs to A, and y is a prime divisor of x+1, the product
x*y also belongs to A.
> > Let us call a prime number Euclid-style accessible if it is a divisor of
some number belonging to A. Are there prime numbers that are not Euclid-style
accessible, and if there are such ones, which is the least among them?
> >
>
> I can't think of a reason why any prime would be excluded from being a factor
of numbers in the set.

I agree.

> I've only gone 5 'deep', and thus far 19 is the only
> prime < 29 that hasn't shown up yet. 11 and 17 were
> late to the party, but they eventually surfaced at depth 5.

A is defined recursively so, rather than your "depth" (which I'm not sure I
understand) I favour a measure "recursion_depth", which would enumerate the
elements of A in order of their appearance as follows:-
x*y  recursion_depth
1    1
1*2  2
2*3  3
6*7  4
42*43 5
1806*13 6
1806*139 6
etc.

Going to recursion_depth=13, pari_GP take a couple of minutes to find that all
primes < 271 are Euclid-style accessible.

2621 elements have been inserted into A at this recursion_depth; but 86 others
have not been inserted, since they exceed the size limit of 10^64 which I
imposed on numbers so that they can be factorised in at most a few seconds.

Mike

#23296 From: "djbroadhurst" <d.broadhurst@...>
Date: Sat Oct 1, 2011 12:49 pm
Subject: Re: Number of factors
djbroadhurst
Send Email Send Email
 
In primenumbers@yahoogroups.com,
Bernardo Boncompagni <RedGolpe@...> wrote:

> Let's say we have a random number N:
> we know that we can expect
> log(log(N)) distinct prime factors.
> Great, we found the least of them, say p.
>
> In the end, my question is:
> how many factors should one expect in N/p?

Provided that p << N, I guess that the average value
of omega(n/p) for the numbers n up to N with least
prime divisor p is

log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)

with B_1 =
0.261497212847642783755426838608695859051566648261199206192...
but this is only a guess. (It is true for p = 2
and looks sensible for N >> p >> 2.)

David

#23297 From: "mikeoakes2" <mikeoakes2@...>
Date: Sat Oct 1, 2011 3:05 pm
Subject: Re: A question
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
>
> > > Let A be the least set of natural numbers with the following two
properties:
> > > (i) the number 1 belongs to A;
> > > (ii) whenever x belongs to A, and y is a prime divisor of x+1, the product
x*y also belongs to A.
> > > Let us call a prime number Euclid-style accessible if it is a divisor of
some number belonging to A. Are there prime numbers that are not Euclid-style
accessible, and if there are such ones, which is the least among them?
>
> x*y  recursion_depth
> 1    1
> 1*2  2
> 2*3  3
> 6*7  4
> 42*43 5
> 1806*13 6
> 1806*139 6
> etc.
>
> Going to recursion_depth=13, pari_GP take a couple of minutes
> to find that all primes < 271 are Euclid-style accessible.
>

Here are the results of running pari-GP on a single Intel core @ 1.8 GHz:-

depth first_inaccessible card(A) time
1     2                  1       0 secs
2     3                  2       0 secs
3     5                  3       0 secs
4     5                  4       0 secs
5     5                  5       0 secs
6     5                  7       0 secs
7     11                 11      0 secs
8     11                 20      0 secs
9     19                 44      0 secs
10    19                 96      0.05 secs
11    47                 261     0.28 secs
12    103                808     15.71 secs
13    271                2621    161.9 secs
14    827                8151    788.2 secs
15    1913               23884   3779.3 secs

At depth 12, 13, 14, 15, the number of elements of A > 10^64 (and so left
unfactorised) were 4, 86, 780, 3894, respectively.

Mike

#23298 From: "Dimiter Skordev" <skordev@...>
Date: Sat Oct 1, 2011 3:37 pm
Subject: Re: A question
dskordev
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
> > I can't think of a reason why any prime would be excluded from being a
factor of numbers in the set.
>
> I agree.
After the work Mark and Mike did, it really seems that any prime number is
Euclid-style accessible. Unfortunately, I have no idea how this could be proved.

> > I've only gone 5 'deep', and thus far 19 is the only
> > prime < 29 that hasn't shown up yet. 11 and 17 were
> > late to the party, but they eventually surfaced at depth 5.
>
> A is defined recursively so, rather than your "depth" (which I'm not sure I
understand) I favour a measure "recursion_depth", which would enumerate the
elements of A in order of their appearance as follows:-
> x*y  recursion_depth
> 1    1
> 1*2  2
> 2*3  3
> 6*7  4
> 42*43 5
> 1806*13 6
> 1806*139 6
> etc.
I also would understand the notion of depth in this way. When I wrote "No, I
have not gone even to that depth", I actually meant I did not go to a depth at
which, for instance, 11 and 17 are already shown to be Euclid-style accessible.

In addition to this notion of accessibility, maybe a stronger one also deserves
some attention, namely the one we get when we replace "y is a prime divisor of
x+1" with "y is the least prime divisor of x+1" in the definition of the set A.

Dimiter

#23299 From: "mikeoakes2" <mikeoakes2@...>
Date: Sat Oct 1, 2011 6:08 pm
Subject: Re: A question
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@...> wrote:
>
> In addition to this notion of accessibility, maybe a stronger one also
deserves some attention, namely the one we get when we replace "y is a prime
divisor of x+1" with "y is the least prime divisor of x+1" in the definition of
the set A.
>

In this case, of course, the tree degenerates into a list, and so is more
straightforward to program; and we have simply
card(A)=recursion_depth.

Defining the function s(m), for integer m, to be its smallest prime factor, your
set A is the set {u[n]}, with the (monotonically increasing) sequence u[] being
defined by:
u[1] = 1
u[n] = u[n-1] * s(u[n-1]+1), n >= 2

As with the earlier definition, I can see no reason why all primes should not be
accessible.

I removed any restriction on size of integer to (attempt to) factorise.

For 14 <= recursion_depth <= 28, the first inaccessible prime is 19.

I have now run into a brick wall:
u[28]=326408399720836161014262419152749\
231088487789442706259494316079679210912\
54869713984092316692981590
and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).

ecm anyone?

Mike

#23300 From: Bernardo Boncompagni <RedGolpe@...>
Date: Sat Oct 1, 2011 6:32 pm
Subject: Re: [PrimeNumbers] Re: A question
redgolpe
Send Email Send Email
 
>
> I have now run into a brick wall:
> u[28]=326408399720836161014262419152749\
> 231088487789442706259494316079679210912\
> 54869713984092316692981590
> and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).
>

PRP27 = 643679794963466223081509857
PRP28 = 2496022367830647867616317307
PRP44 = 20316223246552213835636779619145529457704309


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

#23301 From: "mikeoakes2" <mikeoakes2@...>
Date: Sat Oct 1, 2011 6:38 pm
Subject: Re: A question
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, Bernardo Boncompagni <RedGolpe@...> wrote:
>
> >
> > I have now run into a brick wall:
> > u[28]=326408399720836161014262419152749\
> > 231088487789442706259494316079679210912\
> > 54869713984092316692981590
> > and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).
> >
>
> PRP27 = 643679794963466223081509857
> PRP28 = 2496022367830647867616317307
> PRP44 = 20316223246552213835636779619145529457704309
>

Thanks, Bernardo.

Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)
:-)

Mike

#23302 From: "elevensmooth" <elevensmooth@...>
Date: Sun Oct 2, 2011 1:59 am
Subject: Re: A question
elevensmooth
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:

> Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)
> :-)

Somebody has been here before, carried it up to 256 digits, and saved it all in
the factordb

http://factorization.ath.cx/index.php?id=1100000000024656542
http://factorization.ath.cx/index.php?id=1100000000024656619
http://factorization.ath.cx/index.php?id=1100000000024656629
http://factorization.ath.cx/index.php?id=1100000000024361410
http://factorization.ath.cx/index.php?id=1100000000084404073
http://factorization.ath.cx/index.php?id=1100000000084404103
http://factorization.ath.cx/index.php?id=1100000000084404112
http://factorization.ath.cx/index.php?id=1100000000084404156
http://factorization.ath.cx/index.php?id=1100000000084404156
http://factorization.ath.cx/index.php?id=1100000000084405578
http://factorization.ath.cx/index.php?id=1100000000084405618
http://factorization.ath.cx/index.php?id=1100000000084405692
http://factorization.ath.cx/index.php?id=1100000000084405749
http://factorization.ath.cx/index.php?id=1100000000084405824
http://factorization.ath.cx/index.php?id=1100000000084405856
http://factorization.ath.cx/index.php?id=1100000000084406023
http://factorization.ath.cx/index.php?id=1100000000038159060
http://factorization.ath.cx/index.php?id=1100000000201891404
http://factorization.ath.cx/index.php?id=1100000000201895169
http://factorization.ath.cx/index.php?id=1100000000201898222
http://factorization.ath.cx/index.php?id=1100000000215895311

#23303 From: "Jens Kruse Andersen" <jens.k.a@...>
Date: Sun Oct 2, 2011 2:08 am
Subject: [PrimeNumbers] Re: A question
jkand71
Send Email Send Email
 
Mike wrote:
> Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)

We only need the smallest factor which is trivially found by trial
factoring to be 103.
The sequence of smallest prime factors is the Euclid-Mullin sequence.
See for example http://oeis.org/A000945 and
http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

The smallest missing prime in the 47 known terms is 31.

--
Jens Kruse Andersen

#23304 From: "djbroadhurst" <d.broadhurst@...>
Date: Sun Oct 2, 2011 3:01 am
Subject: Re: A question
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"Jens Kruse Andersen" <jens.k.a@...> wrote:

> The sequence of smallest prime factors is the Euclid-Mullin sequence.
> See for example http://oeis.org/A000945 and
> http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

It is notable that only one known factorization is incomplete:
http://www.rieselprime.de/Others/EuclidMullin.htm
and in that case it suffices to show that the composite
co-factor has no prime divisor less than 127.

David

#23305 From: Andrey Kulsha <Andrey_601@...>
Date: Sun Oct 2, 2011 10:25 am
Subject: Re: [PrimeNumbers] Re: the prime counts up to 2.5e16
andrey_601
Send Email Send Email
 
>>     And the next one is 188272405179937051081.
>
> Wow, that was quick! Thanks for updating A007097:
>
>> a(20) found by Andrey V. Kulsha using a program
>> by Xavier Gourdon, Sep 29 2011

     a(21) = 9332039515881088707361

     Triple-checking is in progress.

     Best regards,

     Andrey

#23306 From: Kermit Rose <kermit@...>
Date: Sun Oct 2, 2011 4:48 pm
Subject: p1, p2 mod q^2
kermit1941
Send Email Send Email
 
If 0 < b1 < p1 < q
and 0 < b2 < p2 < q

and

b1^p1 = 1 mod q^2

and
b2^p2 = 1 mod q^2


What can we conclude about relation between p1 and p2?

Consider the case where q is prime.

It must also be true that

b1^p1 = 1 mod q
and
b2^p2 = 1 mod q.

and since q is prime, p1 divides (q-1) and
p2 divides (q-1).

If p1 is not equal to p2, then it must be that

p1*p2 divides (q-1).

which means that q would have to be much larger, perhaps out of bounds
of calculation.

Kermit

#23307 From: Kermit Rose <kermit@...>
Date: Sun Oct 2, 2011 5:22 pm
Subject: b^p = 1 mod q^3
kermit1941
Send Email Send Email
 
Suppose b0^p = 1 mod q, where q is prime.

Let b = (b2 q^2 + b1 q + b0)

b^2 =  (b2 b0 + b1^2) q^2 + (b1 b0 ) q + b0^2 mod q^3

b^3 = (b2 b0^2 + 2 b1^2 b0) q^2 + (2 b1 b0^2) q + b0^3 mod q^3

...

b^p = J2 q^2 + J1 q + b0^p mod q^3

b^p = J2 q^2 + J1 q + 1 mod q^3

b^p = 1 mod q^3  ==>  J2 q^2 + J1 q = 0 mod q^3

==> J2 q + J1 = 0 mod q^2

==> J1 = 0 mod q and  J2 = 0 mod q.

Use formula for (b2 q^2 + b1 q + b0)^p to find

expansion mod q^3.

If I were more familiar with that formula, I could do it here.

Kermit

#23308 From: "djbroadhurst" <d.broadhurst@...>
Date: Sun Oct 2, 2011 5:53 pm
Subject: Re: b^p = 1 mod q^3
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
Kermit Rose <kermit@...> wrote:

> Suppose b0^p = 1 mod q, where q is prime.
> Let b = (b2 q^2 + b1 q + b0)
...
> Use formula for (b2 q^2 + b1 q + b0)^p to find
> expansion mod q^3.
> If I were more familiar with that formula,
> I could do it here.

Get Pari-GP to do it for you :-)

Assuming that p|q-1, with prime q,
we simply ask for

  bsol(p,q)=lift(znprimroot(q^3)^(q^2*(q-1)/p));
  \\ example:
  b=bsol(5,11);if(Mod(b,11^3)^5==1,print(b));

1170

David

#23309 From: "djbroadhurst" <d.broadhurst@...>
Date: Sun Oct 2, 2011 6:19 pm
Subject: Re: p1, p2 mod q^2
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
Kermit Rose <kermit@...> wrote:

> b1^p1 = 1 mod q^2
> b2^p2 = 1 mod q^2

> If p1 is not equal to p2, then it must be that
> p1*p2 divides (q-1).

Indeed. Moreover, (b1,q) and (b2,q) are Wieferich pairs
with the same q. Such conjunctions are rare.
Even when we find one, the probability that it solves
our problem, with p2 > p1 > 2, is low.
If q = 2*k*p1*p2 + 1, we might guess the probability as

(p1/(q-1))*(p2/(q-1)) = 1/(2*k*(q-1))

which is why this feat has not yet been accomplished.
But that does not mean that it cannot be done.

David

#23310 From: "djbroadhurst" <d.broadhurst@...>
Date: Sun Oct 2, 2011 6:25 pm
Subject: Re: the prime counts up to 2.5e16
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
Andrey Kulsha <Andrey_601@...> wrote:

>     a(21) = 9332039515881088707361
>     Triple-checking is in progress.

http://oeis.org/A007097
seems to indicate that the checks are completed?

David

#23311 From: Andrey Kulsha <Andrey_601@...>
Date: Sun Oct 2, 2011 6:31 pm
Subject: Re: [PrimeNumbers] Re: the prime counts up to 2.5e16
andrey_601
Send Email Send Email
 
> http://oeis.org/A007097
> seems to indicate that the checks are completed?

     No, they are still running, but I have some reasons to believe
that all will be OK :-)

     Best regards,

     Andrey

#23312 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 12:48 am
Subject: Re: Number of factors
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Provided that p << N, I guess that the average value
> of omega(n/p) for the numbers n up to N with least
> prime divisor p is
>
> log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)
>
> with B_1 =
> 0.261497212847642783755426838608695859051566648261199206192...

I have proven this for primes p up to 19,
but the general proof eludes me.
My proof for p = 19 was already laborious and is
equivalent to showing that test(19) is true, here:

  {T(n)=local(F=factor(n)[,1]);
  sum(k=1,n,sum(j=1,#F,gcd(k,F[j])==1))/n^2;}

  {test(p)=local(P=1,D=1,A=1-1/p);
  forprime(q=2,p-1,P*=q;D*=1-1/q;A-=1/q);
  sumdiv(P,n,moebius(n)*T(n*p))*p/D == A;}

  {gettime;forprime(p=2,19,if(test(p),
  print("p = "p" proven in "gettime" ms")));}

p = 2 proven in 0 ms
p = 3 proven in 0 ms
p = 5 proven in 0 ms
p = 7 proven in 0 ms
p = 11 proven in 8 ms
p = 13 proven in 141 ms
p = 17 proven in 2926 ms
p = 19 proven in 66089 ms

Challenge: prove that test(p) is true for all prime p.

David (unable to this, at present)

#23313 From: "mikeoakes2" <mikeoakes2@...>
Date: Mon Oct 3, 2011 7:42 am
Subject: Re: Square factors of b^p-1
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> --- In primenumbers@yahoogroups.com,
> "djbroadhurst" <d.broadhurst@> wrote:
>
> > > Puzzle 3a: Find primes b1 < p1 < q, b2 < p2 < q, b1 < b2, s.t.
> > > b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2).
> >
> > Here are 5 such pairs of triples:
> >
> > [132529, 277691, 555383]
> > [211811, 277691, 555383]
> >
> > [134507, 883703, 1767407]
> > [720901, 883703, 1767407]
> >
> > [292933, 1051553, 2103107]
> > [385079, 1051553, 2103107]
> >
> > [434243, 613189, 2452757]
> > [470711, 613189, 2452757]
> >
> > [1161143, 3700283, 7400567]
> > [2768789, 3700283, 7400567]
>
> and a sixth, also with p1 = p2:
>
> [ 417961, 5699017, 22796069]
> [1997161, 5699017, 22796069]

Using 4 days pari-GP at 3.6Ghz I have solidified these results.

For b1, b2, q < 10^7.5, the complete list of such q is:-
555383
1767407
2103107
2452757
7400567

12836987
14668163
15404867
16238303
19572647
22796069  [found by DB]
25003799
26978663
27370727

Each (q-1) is of the form 2^m*p, and p1 = p2 in each case.

Mike

#23314 From: Bernardo Boncompagni <RedGolpe@...>
Date: Mon Oct 3, 2011 8:27 am
Subject: Re: [PrimeNumbers] Re: Number of factors
redgolpe
Send Email Send Email
 
>
> Provided that p << N, I guess that the average value
> of omega(n/p) for the numbers n up to N with least
> prime divisor p is
>
> log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)
>
> with B_1 =
> 0.261497212847642783755426838608695859051566648261199206192...
>
Interestingly enough, if p>>1, sum=B_1+log(log(p)) and we get
log(log(N))-log(log(p)).

The chance of N being prime is 1/log(N). Invoking Mertens' 3rd theorem, the
chance of a number sieved up to p being prime should be
log(p)/(log(N)*exp(-gamma)), where gamma is the Euler-Mascheroni constant.
If the log(N) in the number of divisors is distantly related to the chance
of N being prime, one may squeeze this result into our formula obtaining
log(log(N)*exp(-gamma)/log(p))=log(log(N))-log(log(p))-gamma. Not sure if
this last passage makes sense but at this point I guess
log(log(N))-log(log(p)) is a very reasonable answer to the problem. By the
way, N>p^2 means log(log(N))-log(log(p))>log(2) which looks reasonable
enough.

It's even very elegant if one writes it as log(lg(N)), where lg is the
logarithm to base p...


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

#23315 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 9:37 am
Subject: Re: Number of factors
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
Bernardo Boncompagni <RedGolpe@...> wrote:

> > log(log(N)) + B_1 - sum(prime q < p, 1/q) + o(1)
>
> Interestingly enough, if p>>1, sum=B_1+log(log(p))
> and we get log(log(N))-log(log(p)).

For log(p) << log(N), the average of omega(n/p),
with n running from p to N and p the least
prime divisor of n, is (I claim) asymptotic to the
sum of 1/q, with prime q running from q = p up to
the greatest prime q <= N/p.

All I did was to use Mertens at the upper limit.
For log(2) << log(p) << log(N), one may also use
Mertens at the lower limit to get log(log(N)/log(p)),
as Bernardo has observed. However one should not push
this up to p = O(sqrt(N)), since there we may run into
a problem that worried Chebyshev:
http://tech.groups.yahoo.com/group/primenumbers/message/21565

David (per proxy Pafnuty Lvovich)

#23316 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 10:26 am
Subject: Re: Square factors of b^p-1
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> > Puzzle 3a: Find primes b1 < p1 < q, b2 < p2 < q, b1 < b2, s.t.
> > b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2).
>
> For b1, b2, q < 10^7.5, the complete list of such q is:-
> 555383
> 1767407
> 2103107
> 2452757
> 7400567
>
> 12836987
> 14668163
> 15404867
> 16238303
> 19572647
> 22796069  [found by DB]
> 25003799
> 26978663
> 27370727
>
> Each (q-1) is of the form 2^m*p, and p1 = p2 in each case.

In the course of this Mike Oakes found 8 pairs of
Wieferich pairs not recorded Michael Mosinghoff,
who condidered only q = 1 mod 4 when q > 10^7 and
hence missed SG pairs (p,q=2*p+1).

In the format [q,m,p,[b1,b2]] these new
double Wieferich results are:

[12836987, 1, 6418493, [2061197, 4631743]]
[14668163, 1, 7334081, [3692407, 7145591]]
[15404867, 1, 7702433, [2824163, 3123217]]
[16238303, 1, 8119151, [639167, 1005581]]
[19572647, 1, 9786323, [3204463, 7873399]]
[25003799, 1, 12501899, [59273, 4701583]]
[26978663, 1, 13489331, [2589553, 8582417]]
[27370727, 1, 13685363, [5002507, 5356201]]

Moreover M.O must have found many more
isolated Wieferich pairs with q > 10^7.
Perhaps these might be communicated to M.M ?

David

#23317 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 1:20 pm
Subject: Re: Square factors of b^p-1
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"mikeoakes2" <mikeoakes2@> wrote:

> > Puzzle 3a: Find primes b1 < p1 < q, b2 < p2 < q, b1 < b2, s.t.
> > b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2).

At q^2 > 10^15, I found

1634447^18090263 = 1 mod 36180527^2
1773371^18090263 = 1 mod 36180527^2

David (not by googling :-)

#23318 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 2:04 pm
Subject: Re: Square factors of b^p-1
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> > Puzzle 3a: Find primes b1 < p1 < q, b2 < p2 < q, b1 < b2, s.t.
> > b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2).
>
> At q^2 > 10^15, I found
>
> 1634447^18090263 = 1 mod 36180527^2
> 1773371^18090263 = 1 mod 36180527^2

Also

   3633673^26867849 = 1 mod 53735699^2
  21160553^26867849 = 1 mod 53735699^2

David

#23319 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 4:46 pm
Subject: Re: Square factors of b^p-1
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

>> Puzzle 3a: Find primes b1 < p1 < q, b2 < p2 < q, b1 < b2, s.t.
>> b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2).
>
> At q^2 > 10^15, I found
>
>  1634447^18090263 = 1 mod 36180527^2
>  1773371^18090263 = 1 mod 36180527^2
>
>  3633673^26867849 = 1 mod 53735699^2
> 21160553^26867849 = 1 mod 53735699^2

Also

    4232737^17591459 = 1 mod 35182919^2
   15865919^17591459 = 1 mod 35182919^2

    4144001^19276511 = 1 mod 38553023^2
   13038863^19276511 = 1 mod 38553023^2

    2963911^27536213 = 1 mod 55072427^2
    3658729^27536213 = 1 mod 55072427^2

David

#23320 From: "mikeoakes2" <mikeoakes2@...>
Date: Mon Oct 3, 2011 5:32 pm
Subject: Re: Square factors of b^p-1
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@> wrote:
> >
> > Puzzle 2: Find a triplet of primes (b,p,q) with b < p < q,
> > b^p = 1 mod q^2, and q^2 having precisely 21 decimal digits.
>
> I reckon there should be about 208952 solutions to this puzzle.
> Rationale:-
>
> max_q   solutions   ratio
> 10^1    0           -
> 10^1.5  1           -
> 10^2    1           1.0
> 10^3    1           1.0
> 10^3.5  1           1.0
> 10^4    3           3.0
> 10^4.5  6           2.0
> 10^5    22          3.667
> 10^5.5  58          2.636
> 10^6    125         2.155
> 10^6.5  322         2.576
> 10^7    781         2.435
> Taking the ratio to be about 2.4 then gives these estimates:-
> 10^7.5  1874        2.4
>...

New experimentally-determined data point supports the picture:-
  10^7.5  1944       2.489

Mike

#23321 From: "mikeoakes2" <mikeoakes2@...>
Date: Mon Oct 3, 2011 5:56 pm
Subject: Re: Square factors of b^p-1
mikeoakes2
Send Email Send Email
 
--- In primenumbers@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> >> Puzzle 3a: Find primes b1 < p1 < q, b2 < p2 < q, b1 < b2, s.t.
> >> b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2).
> >
> > At q^2 > 10^15, I found
> >
> >  1634447^18090263 = 1 mod 36180527^2
> >  1773371^18090263 = 1 mod 36180527^2
> >
> >  3633673^26867849 = 1 mod 53735699^2
> > 21160553^26867849 = 1 mod 53735699^2
>
> Also
>
>    4232737^17591459 = 1 mod 35182919^2
>   15865919^17591459 = 1 mod 35182919^2
>
>    4144001^19276511 = 1 mod 38553023^2
>   13038863^19276511 = 1 mod 38553023^2
>
>    2963911^27536213 = 1 mod 55072427^2
>    3658729^27536213 = 1 mod 55072427^2

Would I be right in supposing, from the facts that (a) these results are
appearing in random order of q and (b) very quickly, that you have given this
problem to one of your computer "farms"?
:-)

Mike

#23322 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 6:25 pm
Subject: Re: Square factors of b^p-1
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> (a) these results are appearing in random order of q and
> (b) very quickly

Combination of two effects: several cores and
specializing to the most lucrative case, p1=p2=(q-1)/2,
so I only look at q if it is the larger member
of a SG pair. Largest q so far is here:

25638913^35364419 = 1 mod 70728839^2
26450899^35364419 = 1 mod 70728839^2

David

#23323 From: "djbroadhurst" <d.broadhurst@...>
Date: Mon Oct 3, 2011 9:34 pm
Subject: Re: Square factors of b^p-1
djbroadhurst
Send Email Send Email
 
--- In primenumbers@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> ... the most lucrative case, p1=p2=(q-1)/2 ...
>
> 25638913^35364419 = 1 mod 70728839^2
> 26450899^35364419 = 1 mod 70728839^2

These have larger q:

   1783447^48649379 = 1 mod 97298759^2
  25659449^48649379 = 1 mod 97298759^2

   2076259^48687659 = 1 mod 97375319^2
  34543973^48687659 = 1 mod 97375319^2

David

#23324 From: "djbroadhurst" <d.broadhurst@...>
Date: Tue Oct 4, 2011 11:00 am
Subject: Re: Square factors of b^p-1 [SG double Wieferich sequence]
djbroadhurst
Send Email Send Email
 
Prime q=2*p+1 with primes b<c<p such that q^2|b^p-1 and q^2|c^p-1

555383, 1767407, 2103107, 7400567, 12836987, 14668163, 15404867,
16238303, 19572647, 25003799, 26978663, 27370727, 35182919,
36180527, 38553023, 39714083, 52503587, 53061143, 53735699,
55072427, 63302159, 70728839, 77199743, 77401679, 86334299,
97298759, 97375319, 103830599, 106208783, 106710287, 108711599,
112590683, 120441239, 124581719, 126236879, 128538659, 129881603,
133833983, 141132143, 141194387, 145553399, 151565087

Comments: (p,q) is a Sophie Germain prime pair; (b,q) and (c,q)
are Wieferich prime pairs; each of (b,c) is a square modulo q^2.
The sequence is now complete up to the 42nd term, q=151565087.
Mike Oakes set a puzzle on a more general case with primes such
that b<p1<q, c<p2<q, b<c, q^2|b^p1-1 and q^2|c^p2-1. His sequence
is complete only up q=27370727, containing only two new known
primes, q=2452757 and q=22796069, with p1=p2=(q-1)/4, found in
http://tech.groups.yahoo.com/group/primenumbers/message/23175 by
a simple analysis of http://www.cecm.sfu.ca/~mjm/WieferichBarker

David Broadhurst, 4 October 2011, with thanks to Mike Oakes

Messages 23295 - 23324 of 25086   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