Prime numbers and primality testing is a Restricted Group with 1137 members. Yahoo Groups Re: Square factors of b^p-1 mikeoakes2 Message 1 of 81 , Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "djbroadhurst" 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 djbroadhurst Sep 22, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "leavemsg1" wrote: > all Mersenne numbers, Mp, are square-free and then degenerated into nonsense. We know from http://primes.utm.edu/notes/proofs/SquareMerDiv.html that square factors of 2^p-1, with prime p, are improbable. Here is a problem on b^p-1. Puzzle: Find a pair of primes (b,p) with b < p and b^p-1 divisible by a square greater than 10^20. Comment: There are at least two solutions on the internet. David djbroadhurst Sep 22, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Puzzle: Find a pair of primes (b,p) with b < p > and b^p-1 divisible by a square greater than 10^20 I should have added that this square must be coprime to b-1, else the puzzle is trivial. David elevensmooth Sep 22, 2011 ----------------------- > > Puzzle: Find a pair of primes (b,p) with b < p > > and b^p-1 divisible by a square greater than 10^20 > > I should have added that this square must be coprime > to b-1, else the puzzle is trivial. David, You probably have some additional requirement in mind, too. As stated, this is easy via Hensel lifting. My personal favorite is b=5 p=26410234807918766140553131804776270369245047565555936354982011228\ 53066670050005276556869333546277218004385324387952809374139721102968\ 397416420646868802087685498586223 which is divisible by 2801^48, which is of course the square of 2801^24. William Lipp Poohbah of oddperfect.org djbroadhurst Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "elevensmooth" wrote: > > Puzzle: Find a pair of primes (b,p) with b < p > > and b^p-1 divisible by a square greater than 10^20 > > > I should have added that this square must be coprime > > to b-1, else the puzzle is trivial. > As stated, this is easy via Hensel lifting. My personal favorite is > b=5 > p=26410234807918766140553131804776270369245047565555936354982011228\ > 53066670050005276556869333546277218004385324387952809374139721102968\ > 397416420646868802087685498586223 > > which is divisible by 2801^48 Sorry, William, but I could not get that to compute. You have p = 1023 mod 2800 and hence b^p - 1 = 5^1023 - 1 mod 2801 = 1816 mod 2081. > You probably have some additional requirement in mind, too. Here is a more restrictive puzzle: 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. Comment: William knows well an internet page containing precisely two solutions. I do not yet know of any solution with q^2 > 10^21. David (with apologies to Kurt Wilhelm Sebastian Hensel, if I have still left a loop-hole) djbroadhurst Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Sorry, William, but I could not get that to compute. You have > p = 1023 mod 2800 and hence > b^p - 1 = 5^1023 - 1 mod 2801 = 1816 mod 2081. Ah, I have decoded William's error. He found a big square in p^b-1 with b 10^20 in b^p-1: > 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. which ain't so easy, but has been done at least twice. David mikeoakes2 Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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. > > which ain't so easy, but has been done at least twice. I can enumerate the 125 solutions with q < 10^6 in a few minutes. However, we poor WinDoze users of pari-GP are restricted to primelimit ~4*10^9, making it hard to investigate problems involving b,p,q ~ 10^10. Mike mikeoakes2 Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > Here is a more restrictive puzzle: > > 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. David, May I chime in with a related puzzle. Puzzle 3a: Find distinct primes b1 < p1 < q, b2 < p2 < q s.t. b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2). Puzzle 3b: Remarkably, it appears that in all such cases p1 = p2; is this necessary, and if so, why? Mike mikeoakes2 Sep 23, 2011 ----------------------- > Puzzle 3a: Find distinct primes b1 < p1 < q, b2 < p2 < q s.t. > b1^p1 = b2^p2 = 1 mod q^2, (with no limits on q^2). I don't want to prevent p1 and p2 being the same (see Puzzle 3b!), so should have written: 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). djbroadhurst Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "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). 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] All have p1 = p2, but I have no proof that this must always be so. David djbroadhurst Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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] David mikeoakes2 Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > --- In primenumbers@yahoogroups.com, > "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). > > 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] > > All have p1 = p2, but I have no proof > that this must always be so. Yes. Exactly the same 5 pairs I found, after a few hours. Mike Lélio Sep 23, 2011 ----------------------- > > ** > > >--- In primenumbers@yahoogroups.com, > >"djbroadhurst" 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 6 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] > > > >[ 417961, 5699017, 22796069] > >[1997161, 5699017, 22796069] > > > >David > > q = 1 mod (p) in all 6 triples may be a hint to the need of p1 = p2 Lélio [Non-text portions of this message have been removed] djbroadhurst Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Lélio wrote: > q = 1 mod (p) in all 6 triples > may be a hint to the need of p1 = p2 It is easy to prove that b^p = 1 mod q, with primes b < p < q, implies that q = 1 mod p so your observation tells us nothing further about Mike's double congruence b1^p1 = 1 mod q^2 b2^p2 = 1 mod q^2 with b1 < b2. David djbroadhurst Sep 23, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Exactly the same 5 pairs I found, after a few hours. Googling was quicker :-) David Kevin Acres Sep 24, 2011 ----------------------- At 08:54 AM 24/09/2011, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >"mikeoakes2" wrote: > > > Exactly the same 5 pairs I found, after a few hours. > >Googling was quicker :-) > >David So these pairs are all instances of znorder(Mod(b,q^2))= znorder(Mod(2,q))? Wieferich primes revisted :-) Could have saved a few hours myself if I had I tried googling first. Kevin. mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > Exactly the same 5 pairs I found, after a few hours. > > Googling was quicker :-) > > David Putting the search 555383,1767407,2103107,2452757 into google leads one quickly to this page:- http://www.cecm.sfu.ca/~mjm/WieferichBarker/ Which made me realize that if b1^p1 = b2^p2 = 1 mod q^2 then b1^(q-1) = b2^(q-1) = 1 mod q^2 so that (b1,q) and (b2,q) are what he calls "Wieferich Prime Pairs" and so will show up in his tables. Haven't yet tried to find a solution to your Puzzle 2 using this. Presumably it helps? Mike mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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 10^8 4499 2.4 10^8.5 10797 2.4 10^9 25912 2.4 10^9.5 62188 2.4 10^10 149251 2.4 all these q^2 have <=20 digits 10^10.5 358203 2.4 all these q^2 have <=21 digits Mike djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" 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. Of which precisely 2 may be extracted from a paper by Wilfrid Keller and Jörg Richstein, with none other being available from related pages maintained by Wilfrid Keller, by Michael Mossinghoff, or by William Lipp (who really should have known how to farm his own page). David (google coach:-) djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > Wieferich primes revisted :-) > > Could have saved a few hours myself > if I had I tried googling first. Indeed :-) David mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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. > > which ain't so easy, but has been done at least twice. 239^6251114333 mod 12502228667^2=1 613^9209676191 mod 18419352383^2=1 [ Candidates were a subset of http://www.cecm.sfu.ca/~mjm/WieferichBarker/Data/q3p11.txt ] Mike mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" 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. > > Of which precisely 2 may be extracted from a paper by > Wilfrid Keller and Jörg Richstein, with none other being > available from related pages maintained by Wilfrid Keller, > by Michael Mossinghoff, or by William Lipp (who really > should have known how to farm his own page). > > David (google coach:-) Before seeing this, I have just posted 2 solutions which I found via the Mossinghoff page I mentioned earlier. Mike [thanking the master for the tip to use google] mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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. Does b^p = 1 mod q^3 have any known solutions? (There are none for q < 10^6.) Mike j_chrtn Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > > --- In primenumbers@yahoogroups.com, > "leavemsg1" wrote: > > > all Mersenne numbers, Mp, are square-free > > and then degenerated into nonsense. We know from > http://primes.utm.edu/notes/proofs/SquareMerDiv.html > that square factors of 2^p-1, with prime p, are > improbable. Hi David, Extending this to Mike and I favorite numbers M(b,p)=b^p-(b-1)^p, the "square free or not square free... that is the question" shakepearian problem is also interesting. In general, for b > 2, M(b,p) is not square free. An easy counter example is for b=3 and p=11: 3^11-2^11 which is divisible by 23^2 (notice 11 is a Sophie Germain prime (or SG) as discuss below). Other less trivial examples are : b=26,p=2699 : 26^2699-25^2699 is divisible by 5399^2 (SG) b=26,p=17939 : 26^17939-25^17939 is divisible by 35879^2 (SG) b=50,p=11743 : 50^11743-49^11743 is divisible by 281833^2 (not SG) b=59,p=33773 : 59^33773-58^33773 is divisible by 67547^2 (SG) However, for a significative amount of bases b, M(b,p) seems to behave like 2^p-1, that is, finding a prime p such that the number is not square free is a hard puzzle. Example of such bases are 4, 6, 7, 9, 10, 11, ... I wonder what makes those bases so "hard"? Since factors of M(b,p) are k*p+1 for some k (or 2*k*p+1 if p >= 3), if q^2 (q prime) divides M(b,p), then b^(q-1)-(b-1)^(q-1) = 0 mod (q^2). Of course, when b=2 we recognize that q is a Wieferich prime. By analogy, for b > 2, we could call q a "base b Wieferich like prime" For b > 2, those "base b Wieferich like primes" seems to be quite rare too. It's well known (Euler) that if p is a SG prime such that p = 3 mod 4 then 2p+1 divides M(2,p) = 2^p-1. This result also applies to M(b, p) for b > 2 this way: If p is a SG prime such that p = 3 mod 4 then 2p+1 divides M(b,p) for all b such that b = 2 mod (2p+1). Other possible case: if p is a SG and b and b-1 are both squares mod (2p+1) then 2p+1 divides M(b,p). So the SG primes may be good candidates to start with to find M(b,p) that are not square free. There is quite a lot of SG primes p that divide many M(b,p). Then if we are a bit lucky, a couple of them will be such that p^2 divides M(b,p). J-L djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "j_chrtn" wrote: > So the SG primes may be good candidates to start with Indeed. Note that both known solutions to > 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. have (p,q) as an SG pair: 239^6251114333 = 1 mod 12502228667^2 613^9209676191 = 1 mod 18419352383^2 It is clearly necessary that q = 2*k*p+1, where k = 1 gives an SG pair. In the pair 417961^5699017 = 1 mod 22796069^2 1997161^5699017 = 1 mod 22796069^2 we have k = 2. Small k is favoured since 2*k must divide (q-1)/znorder(Mod(b,q^2)). Note that your proposed extension b^p = (b-1)^p mod q^2 with primes p < q and any integer b such that 1 < b < q may be rewritten as c^p = 1 mod q^2 ........ [1] c = b/(b-1) mod q^2 .... [2] where tables will tell you about [1] and [2] is easily investigated :-) David djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Does > b^p = 1 mod q^3 > have any known solutions? http://www.cecm.sfu.ca/~mjm/WieferichBarker/Data/wieferich3.txt appears to contains no (b,q) pair with b < q. David djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" 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. > 239^6251114333 mod 12502228667^2=1 > 613^9209676191 mod 18419352383^2=1 Well googled :-) Larger SG solutions may be googled: 4397^43814458559 = 1 mod 87628917119^2 8461^39566097563 = 1 mod 79132195127^2 David mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > Larger SG solutions may be googled: > > 4397^43814458559 = 1 mod 87628917119^2 > 8461^39566097563 = 1 mod 79132195127^2 You said yesterday > I do not yet know of any solution with q^2 > 10^21. So, you've now found 2 such. Congratulations. Are they the biggest known (so far)? Mike djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > 4397^43814458559 = 1 mod 87628917119^2 > > 8461^39566097563 = 1 mod 79132195127^2 > > You said yesterday > > I do not yet know of any solution with q^2 > 10^21. Later yesterday, I got better at googling in German http://www.fermatquotient.com/FermatQuotienten/ > So, you've now found 2 such. Congratulations. > Are they the biggest known (so far)? The biggest known to me, today. David mikeoakes2 Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > > 4397^43814458559 = 1 mod 87628917119^2 > > > 8461^39566097563 = 1 mod 79132195127^2 > > > > You said yesterday > > > I do not yet know of any solution with q^2 > 10^21. > > Later yesterday, I got better at googling in German > http://www.fermatquotient.com/FermatQuotienten/ I have checked, and agree that of the "Top 36 der bisher entdeckten Fermatquotienten nur mit Primbasen" at http://www.fermatquotient.com/FermatQuotienten/Statistik only (alas) the 2 you list give solutions to Puzzle 2. Mike djbroadhurst Sep 24, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > I have checked, and agree that of the > "Top 36 der bisher entdeckten Fermatquotienten nur mit Primbasen" > at > http://www.fermatquotient.com/FermatQuotienten/Statistik > only (alas) the 2 you list give solutions to Puzzle 2. Ich danke dir ganz herzlich! I believe that Wilfrid watches our diversions with grandfatherly amusement and hope that he is enjoying these adumbrations on http://tinyurl.com/3zb6afs David mikeoakes2 Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "djbroadhurst" 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 djbroadhurst Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "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 djbroadhurst Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "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 :-) djbroadhurst Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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 djbroadhurst Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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 mikeoakes2 Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > --- In primenumbers@yahoogroups.com, "djbroadhurst" 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 mikeoakes2 Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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 djbroadhurst Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "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 djbroadhurst Oct 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" 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 djbroadhurst Oct 4, 2011 ----------------------- Prime q=2*p+1 with primes b wrote: > > Prime q=2*p+1 with primes b > 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 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 Congrats on establishing that substantial sequence, David. It must be worthy of submission to Neil's OEIS. Your upper limit on q is about 5 times higher that I have reached for the "more general case" - which my code would take about 5^2*4=100 days on one 3.6GHz core to complete. Mike djbroadhurst Oct 4, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: >> Prime q=2*p+1 with primes b Congrats on establishing that substantial sequence, David. Thanks for your stimulus. > It must be worthy of submission to Neil's OEIS. I'll wait for some more data. The 43rd term is q=156529403. With processes now in synchrony, no more sporadic values :-) David djbroadhurst Oct 5, 2011 ----------------------- Primes q = 2*p+1 for which there are primes b > http://www.primenumbers.net/prptop/searchform.php?form=(x^x%2By^y)? > reveals 10 PRPS, of which 3 give examples of multiple > square factors of n^n+(n+1)^(n+1): > > (7186^7186+7187^7187)/(3*7^2*31^2*101*79333^2) > (4576^4576+4577^4577)/(3*557*1609^2*4339^2*61483) > (3376^3376+3377^3377)/(3*7^2*13^2*19*3361*41761^2*3884884187) > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > with prime p, is more likely than for other cases? > Be f(n)=n^n+(n+1)^(n+1), n>0. If n==4 (mod 6) it looks like c^2|f(n), where c=12*x^2+18*x+7, x=(n-4)/6 (looking for a proof now). So you can obtain a good number of multiple square factors when c is highly composite. All the above examples are of this form. [Non-text portions of this message have been removed] Bernardo Boncompagni Oct 11, 2011 ----------------------- > c=12*x^2+18*x+7, x=(n-4)/6 Easier than that, c=(n^2+n+1)/3 mikeoakes2 Oct 11, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > http://www.primenumbers.net/prptop/searchform.php?form=(x^x%2By^y)? > reveals 10 PRPS, of which 3 give examples of multiple > square factors of n^n+(n+1)^(n+1): > > (7186^7186+7187^7187)/(3*7^2*31^2*101*79333^2) > (4576^4576+4577^4577)/(3*557*1609^2*4339^2*61483) > (3376^3376+3377^3377)/(3*7^2*13^2*19*3361*41761^2*3884884187) > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > with prime p, is more likely than for other cases? I investigated this form, and also the corresponding one with "-", in 2003/2004. Henri and I have 5 PRPs in his databse: http://www.primenumbers.net/prptop/searchform.php?form=x^x-%3F&action=Search I'm trying to find my notes on this work... Mike mikeoakes2 Oct 11, 2011 ----------------------- > I'm trying to find my notes on this work... Found them; here's the gist. Whether or not a prime p is a factor of n^n+(n+1)^(n+1) depends only on the residue m = n mod (p*(p-1)), by Fermat's Little Theorem. For each p < 1000, I let n range over these p*(p-1) values, and set "count" equal to the number of times p was a factor. This count is never zero (for p>2) and is either a bit more or less than p, with no obvious pattern. The table starts:- p count 2 0 3 1 5 2 7 4 11 8 13 8 17 12 19 18 ... Remarks:- count = p-3 for following p:- 5,7,11,23,47,59,73,83,107,167,179,227,263,347,359,383,467,479,503,563,587,719,839,863,887,983; and all these are = 5 mod 6 except for 7,73. count = p-5 for following p:- 13,17,29,37,53,131,149,173,239,269,293,317,353,389,509,557,653,773,797; and all these are = 5 mod 6 except for 17,37. However, this doesn't seem to offer much help towards answering your query, David. Mike Walter Nissen Oct 11, 2011 ----------------------- Hi , all , Most of the early observations of this expression can be found in the : a ) 31? messages in the thread beginning at : http://tech.groups.yahoo.com/group/primenumbers/message/16145 b ) not even draft yet , let alone published : http://upforthecount.com/math/nnp.html Where inter alia you will find : 846 337 * 911 * 911 * 271651 * and 1429 179 * 179 * 971 * 6793 * Note that the warning there about ECM producing only prps does not apply to the complete factorizations which have been checked by Primo/Titanix or APRT-CLE.UB or c ) thread beginning at message # 589 in http://www.mersenneforum.org/showthread.php?t=12981&page=24 There is a precis within message # 592 . Note the word "certain" . All have been completely factored for n < 87 , sieving of which is now underway and more than 1/3 done . Only 5 remain unfactored for n < 103 . There are more factorizations beginning at : http://factordb.com/index.php?query=n^n%2B%28n%2B1%29^%28n%2B1%29&use=n&n=1&VP=on&VC=on&EV=on&OD=on&PR=on&FF=on&PRP=on&CF=on&U=on&C=on&perpage=25&format=1 David , what software/hardware did you use/would you use to locate the prps shown at : http://www.primenumbers.net/prptop/searchform.php?form=(x^x%2By^y)? Cheers , Walter djbroadhurst Oct 11, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "Walter Nissen" wrote: > early observations of this expression can be found in > http://tech.groups.yahoo.com/group/primenumbers/message/16145 [et seqq] In particular see my proof that for positive integer n = 4 mod 6, it is impossible for n^n+(n+1)^(n+1)to be squarefree: http://tech.groups.yahoo.com/group/primenumbers/message/20849 The PRPs (7186^7186+7187^7187)/(3*7^2*31^2*101*79333^2) (4576^4576+4577^4577)/(3*557*1609^2*4339^2*61483) (3376^3376+3377^3377)/(3*7^2*13^2*19*3361*41761^2*3884884187) bearing witness to that. This partly answers my question: > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > with prime p, is more likely than for other cases? but I was asking for more. > David , what software/hardware did you use/would you use to > locate the prps shown at : > http://www.primenumbers.net/prptop/searchform.php?form=(x^x%2By^y)? OpenPFGW with deep factoring in ABC2 mode; i.e. the method that Mark has booby-trapped by the bomb concealed in PFGW Version 3.5.5 but hopes to mend in 3.5.6. David mikeoakes2 Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > http://www.primenumbers.net/prptop/searchform.php?form=(x^x%2By^y)? > reveals 10 PRPS, of which 3 give examples of multiple > square factors of n^n+(n+1)^(n+1): > > (7186^7186+7187^7187)/(3*7^2*31^2*101*79333^2) > (4576^4576+4577^4577)/(3*557*1609^2*4339^2*61483) > (3376^3376+3377^3377)/(3*7^2*13^2*19*3361*41761^2*3884884187) > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > with prime p, is more likely than for other cases? Preliminary answer (cpu still beavering away):- p=59 There are other primes like this, but none smaller. I find this extraordinary. I expect you came on this already, David, which is why you continued this thread, yes? Mike Maximilian Hasler Oct 12, 2011 ----------------------- Do you find that 59^2 divides more n^n+(n+1)^(n+1) than does 7^2 ? I find that 7^2 divides in 4.7% of all cases, while 59^2 does only divide for 0.35% of all n. Below the counts I get: Listed is: p, #{ n<=1e6 | n^n+(n+1)^(n+1)=0 (mod p²) } I believe these counts correspond quite well to an asymptotic density, since for n<1e5 I get about the same counts divided by 10. Of course my script could be buggy... Maximilian forprime(p=1,1000,d=p^2;L=1;print(p" "sum(n=2,1e6,-L==L=Mod(n,d)^n))) 2 0 3 0 5 0 7 47620 11 0 13 25642 17 0 19 17543 23 0 29 0 31 10752 37 9010 41 0 43 7752 47 0 53 0 59 3506 61 5464 67 4974 71 0 73 4566 79 4869 83 881 89 0 97 3436 101 0 103 3237 107 0 109 3058 113 0 127 2624 131 0 137 0 139 2398 149 0 151 2208 157 2122 163 2046 167 0 173 0 179 187 181 1842 191 0 193 1780 193 1780 197 0 199 1676 211 1580 223 1496 227 116 229 1456 233 0 239 0 241 1384 251 0 257 0 263 0 269 0 271 1230 277 1204 281 0 283 1178 293 0 307 1086 311 0 313 1066 317 0 331 1007 337 1008 347 0 349 956 353 0 359 0 367 908 373 894 379 880 383 0 389 0 397 840 401 0 409 814 419 35 421 802 431 0 433 770 439 760 443 30 449 0 457 739 461 0 463 720 467 0 479 0 487 685 491 0 499 668 503 0 509 0 521 0 523 636 541 616 547 622 557 0 563 0 569 0 571 583 577 578 587 0 593 0 599 0 601 559 607 548 613 544 617 0 619 548 631 528 641 0 643 518 647 0 653 0 659 0 661 505 673 496 677 0 683 0 691 486 701 20 709 470 719 0 727 458 733 454 739 452 743 0 751 444 757 454 761 0 769 432 773 0 787 430 797 0 809 0 811 412 821 0 823 404 827 0 829 402 839 0 853 391 857 6 859 388 863 0 877 380 881 0 883 377 887 7 907 375 911 25 919 363 929 6 937 356 941 0 947 0 953 0 967 345 971 5 977 4 983 0 991 336 997 335 mikeoakes2 Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > In particular see my proof that for positive integer n = 4 mod 6, > it is impossible for n^n+(n+1)^(n+1)to be squarefree: > http://tech.groups.yahoo.com/group/primenumbers/message/20849 > > The PRPs > (7186^7186+7187^7187)/(3*7^2*31^2*101*79333^2) > (4576^4576+4577^4577)/(3*557*1609^2*4339^2*61483) > (3376^3376+3377^3377)/(3*7^2*13^2*19*3361*41761^2*3884884187) > bearing witness to that. The 2 key insights in your marvellous proof were to work in the field Q(sqrt(-3)) and to use the binomial theorem. If I may be so bold, I would like to provide a simpler (IMHO) version of your proof. [You used a different "n", and also worked with prime factors; neither of these is necessary.] Theorem: u(n)=n^n+(n+1)^(n+1) is divisible by 3*(n^2+n+1)^2 iff n=4 mod 6. Proof: Working in Q(sqrt(-3)), set omega=(-1+sqrt(-3))/2, and [using a biblical reference] set n=alpha+omega. Then modulo alpha^2 we have, using the binomial theorem:- u(n)=n^n+(n+1)^(n+1) =(alpha+omega)^n+(alpha+(1+omega))^(n+1) =n*alpha*omega^(n-1)+omega^n + (n+1)*alpha*(1+omega)^n+(1+omega)^(n+1) =omega*alpha*omega^(n-1)+omega^n+(omega+1)*alpha*(1+omega)^n+(1+omega)^(n+1) =(alpha+1)*[omega^n+(1+omega)^n] =(1+alpha)*[omega^n+(-omega^2)^n] =0 iff n=4 mod 6; i.e. (n-omega)^2 divides u(n) iff n=4 mod 6. Taking complex conjugates, we also have that (n-omega^2)^2 divides u(n) iff n=4 mod 6. So (n-omega)^2*(n-omega^2)^2 divides u(n) iff n=4 mod 6, i.e. (n^2+n+1)^2 divides u(n) iff n=4 mod 6. It is trivial to prove that in this case there is the extra factor 3. Q.E.D. Mike Chris Caldwell Oct 12, 2011 ----------------------- From Maximilian Hasler > I find that 7^2 divides in 4.7% of all cases, while 59^2 does only divide for 0.35% of all n. I think you should get *exactly* 1/21 for 7 and 6/1171 for 59. CC mikeoakes2 Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Maximilian Hasler wrote: > > Do you find that 59^2 divides more n^n+(n+1)^(n+1) than does 7^2 ? > > I find that 7^2 divides in 4.7% of all cases, while 59^2 does only > divide for 0.35% of all n. > > Below the counts I get: > Listed is: p, #{ n<=1e6 | n^n+(n+1)^(n+1)=0 (mod p²) } > > I believe these counts correspond quite well to an asymptotic density, > since for n<1e5 I get about the same counts divided by 10. > > Of course my script could be buggy... > Maximilian I was ignoring the "algebraic" factor (n^2+n+1)^2, which is completely understood (see David's original and my just-posted proofs.) Mike djbroadhurst Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > > with prime p, is more likely than for other cases? > > Preliminary answer (cpu still beavering away):- > p=59 Thanks Mike for ignoring the case p = 1 mod 6, which is trivial: http://physics.open.ac.uk/~dbroadhu/cert/cong5m6.txt Maximilian's data confirms that p = 59 is a record-holder for p = 5 mod 6: [59, 3506] [83, 881] [179, 187] [227, 116] [419, 35] [443, 30] [701, 20] [857, 6] [887, 7] [911, 25] [929, 6] [971, 5] [977, 4] I have conjectured that this is because 59 is the first prime in http://www.research.att.com/~njas/sequences/A068209 59, 83, 179, 227, 419, 443, 701, 857, 887, 911, 929, 971, 977 But the connection with A068209 is still mysterious, to me, at least. David mikeoakes2 Oct 12, 2011 ----------------------- Typo, sorry. As I'm sure anyone following the algebra will have realized:- > =(alpha+1)*[omega^n+(1+omega)^n] > =(1+alpha)*[omega^n+(-omega^2)^n] should have been: =(alpha+1)*[omega^n+(1+omega)^(n+1)] =(1+alpha)*[omega^n+(-omega^2)^(n+1)] Mike Maximilian Hasler Oct 12, 2011 ----------------------- On Wed, Oct 12, 2011 at 12:38 PM, Chris Caldwell wrote: > From Maximilian Hasler >> I find that 7^2 divides in 4.7% of all cases, while 59^2 does only divide for 0.35% of all n. > > I think you should get *exactly* 1/21 for 7 and 6/1171 for 59. I agree on the 1/21 and apologize again for my premature posting (without thinking) of the "trivial" values (with algebraic factors). I dare to correct the ratio for 59 to 6/1711. Maximilian mikeoakes2 Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > > > with prime p, is more likely than for other cases? > > > > Preliminary answer (cpu still beavering away):- > > p=59 > > Thanks Mike for ignoring the case p = 1 mod 6, which is trivial: > http://physics.open.ac.uk/~dbroadhu/cert/cong5m6.txt "trivial"? - I don't think so. One peculiar case I've uncovered is this:- n=22846 = 4 mod 6 p=907 = 1 mod 6 p^2|n^n+(n+1)^(n+1) but NOT p|(n^2+n+1). Mike mikeoakes2 Oct 12, 2011 ----------------------- Sorry again: got my factors of 3 in a muddle. Should be:- Theorem: u(n)=n^n+(n+1)^(n+1) is divisible by (n^2+n+1)^2/3 iff n=4 mod 6. Mike djbroadhurst Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > n=22846 = 4 mod 6 > p=907 = 1 mod 6 > p^2|n^n+(n+1)^(n+1) > but > NOT p|(n^2+n+1). p=907 is the first in a new sequence of primes, which I here give with their first n values, of Mike's type: [907, 22846] [1039, 364426] [1093, 400036] [1231, 280840] [1303, 381442] [1531, 351232] [1993, 72964] [2377, 895162] [2647, 1347868] [2713, 4289842] [2731, 1145458] [3001, 1096462] [3331, 8301784] [4003, 1025596] [4177, 9687706] [4243, 35668] [4339, 9521416] [4447, 2232424] (complete for p < 5000) David djbroadhurst Oct 12, 2011 ----------------------- Primes p == 1 (mod 6) with n == 4 (mod 6) such that gcd(n^2+n+1,p) = 1 and n^n == -(n+1)^(n+1) (mod p^2). 907, 1039, 1093, 1231, 1303, 1531, 1993, 2377, 2647, 2713, 2731, 3001, 3331, 4003, 4177, 4243, 4339, 4447, 5281, 5419, 5623, 5827, 6007, 6211, 6367, 7591, 7879, 9013, 9277, 9349, 9679, 9931 Comments: a(1) = 907 was found by Mike Oakes. The sequence is now complete up to a(32) = 9931. Link: http://tech.groups.yahoo.com/group/primenumbers/message/23431 David Broadhurst, 12 October 2011 mikeoakes2 Oct 12, 2011 ----------------------- Theorem: v(n)=-n^n+(n+1)^(n+1) is divisible by (n^2+n+1)^2/3 iff n==1 (mod 6). Proof: Follow the same steps as per http://tech.groups.yahoo.com/group/primenumbers/message/23421 mutatis mutandis. Q.E.D. Furthermore, the same primes p == 1 mod 6 which David enumerated in http://tech.groups.yahoo.com/group/primenumbers/message/23433 also figure in this case, being now defined by: Primes p == 1 (mod 6) with n == 1 (mod 6) such that gcd(n^2+n+1,p) = 1 and n^n == (n+1)^(n+1) (mod p^2). I have not programmed a dedicated search, but have unearthed the following 3 examples so far:- p=1039 (first n=83005) p=1303 (first n=20905) p=7879 (first n=94165) Mike djbroadhurst Oct 12, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Primes p == 1 (mod 6) with n == 1 (mod 6) such that > gcd(n^2+n+1,p) = 1 and n^n == (n+1)^(n+1) (mod p^2). > > I have not programmed a dedicated search, > but have unearthed the following 3 examples so far:- > p=1039 (first n=83005) > p=1303 (first n=20905) > p=7879 (first n=94165) [907, 204859] [1039, 83005] [1093, 715351] [1231, 165139] [1303, 20905] [1531, 301933] [1993, 1110571] [2377, 2020669] [2647, 780259] [2713, 2743381] [2731, 6310171] [3001, 1460473] [3331, 2790445] [4003, 214363] [4177, 2179981] [4243, 493693] [4339, 8127265] [4447, 12118105] [5281, 18250477] [5419, 3688903] [5623, 2754127] [5827, 717025] [6007, 1268347] [6211, 11029075] [6367, 4085635] [7591, 2560861] [7879, 94165] [9013, 56763853] [9277, 78764497] [9349, 55894351] [9679, 34845535] [9931, 1162225] As Mike suggested, it seems that there is nothing new here: simply continue http://tech.groups.yahoo.com/group/primenumbers/message/23433 to negative n (mod p*(p-1)). David mikeoakes2 Oct 13, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > with prime p, is more likely than for other cases? Excluding the "algebraic factorisation" case [n=4 mod 6 and p|(n^2+n+1)], it is remarkable that always ** p < n ** with the single exception (p,n)=(911,846). Anyone know why this should be so, or how to prove it? Mike Phil Carmody Oct 13, 2011 ----------------------- --- On Thu, 10/13/11, mikeoakes2 wrote: > "djbroadhurst" wrote: > > Is there any rule for (p,n) such that p^2|n^n+(n+1)^(n+1), > > with prime p, is more likely than for other cases? > > Excluding the "algebraic factorisation" case [n=4 mod 6 and > p|(n^2+n+1)], it is remarkable that always > ** p < n ** > with the single exception > (p,n)=(911,846). > > Anyone know why this should be so, or how to prove it? Assuming there's nothing special about the factors, then because sum 1/p^2 converges, the chance of getting large repeated factors is low even when n is high. This assumption is of course not quite fair, as the (n+1)-residuality of -1/(n+1) decides what factors can and can't be found. But all it does is skew a few up by a bit and others down by a bit. Phil djbroadhurst Oct 13, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Excluding the "algebraic factorisation" case > [n=4 mod 6 and p|(n^2+n+1)], it is remarkable that always > ** p < n ** > with the single exception > (p,n)=(911,846). On the contrary, I conjecture that there is an infinity of such "exceptions" and hazard the guess that number of primes p = 5 mod 6 with x > p > 911 for which there exists a positive integer n < p with p^2|n^n+(n+1)^(n+1) is not smaller than (1/12)*log(log(x)/log(911)), for very large x. I conjecturally obtain a constant no less that 1/12 from http://www.mathpages.com/home/kmath411.htm which I conjecturally relate to the current problem via http://physics.open.ac.uk/~dbroadhu/cert/cong5m6.txt and the associated sparsity of http://oeis.org/A165284 If this be the case, then you have a probability of /at least/ 1 - exp(-1) =~ 63% for finding a second "exception" with p = 5 mod 6 and p < 911^exp(12) =~ 6.25*10^481675, which is beyond the range of Mike's current search :-) In my bones, I think that the constant might be as big as 1/2, rather than as small as 1/12, since when we have a root, there are usually 5 others, with n < p*(p-1). That would mean that Mike has a reasonable chance if he hunts the range p < 911^exp(2) =~7.38*10^21, which is also practical. I have less feeling about the case p = 1 mod 5, ignoring algebraic factors. If that had the same constant 1/2, then the range p < 911^exp(1) =~ 1.11*10^8, becomes imaginable, but still rather remanding. In any case, when dealing with a notional O(log(log(x))) heuristic, one should avoid falling into the trap of http://en.wikipedia.org/wiki/Strong_Law_of_Small_Numbers Yet I cannot resist making the observation that (1/2)*log(log(911)) =~ 0.96. David djbroadhurst Oct 13, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > In my bones, I think that the constant might be as big as 1/2, > rather than as small as 1/12, since when we have a root, there > are usually 5 others, with n < p*(p-1). That would mean that > Mike has a reasonable chance if he hunts the range > p < 911^exp(2) =~7.38*10^21, which is also practical. but meant to say "impractical". djbroadhurst Oct 14, 2011 ----------------------- Primes p for which there are positive integers n < p such that n^n == (n+1)^(n+1) (mod p^2) and gcd(n^2+n+1,p) = 1. 600529 hard Comments: The sequence might be infinite, yet only one such prime is known, namely a(1) = 600529, whose square divides 120099^120099-120098^120098. For n == 1 (mod 6) the square of (n^2+n+1)/3 always divides (n+1)^(n+1)-n^n. cf. Mike Oakes' sequence: Primes p for which there are positive integers n < p such that n^n == -(n+1)^(n+1) (mod p^2) and gcd(n^2+n+1,p) = 1. 911 hard Comments: The sequence might be infinite, yet only one such prime is known, namely a(1) = 911, whose square divides 847^847+846^846. For n == 4 (mod 6) the square of (n^2+n+1)/3 always divides (n+1)^(n+1)+n^n. David Broadhurst, 14 October 2011 Phil Carmody Oct 14, 2011 ----------------------- From: djbroadhurst > Primes p for which there are positive integers n < p such that > n^n == (n+1)^(n+1) (mod p^2) and gcd(n^2+n+1,p) = 1. > > 600529 Is there any reason you're excluding primes p which are both in the algebraic factor and its remainder? (so that at least p^3 divides the whole.) Phil djbroadhurst Oct 14, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > > From: djbroadhurst > > Primes p for which there are positive integers n < p such that > > n^n == (n+1)^(n+1) (mod p^2) and gcd(n^2+n+1,p) = 1. > > > > 600529 > > Is there any reason you're excluding primes p which are > both in the algebraic factor and its remainder? A cubic factor would be off topic, in this thread, and then a moderator might object :-? David (per proxy Peter Pan) thefatphil Oct 14, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > > From: djbroadhurst > > > Primes p for which there are positive integers n < p such that > > > n^n == (n+1)^(n+1) (mod p^2) and gcd(n^2+n+1,p) = 1. > > > > > > 600529 > > > > Is there any reason you're excluding primes p which are > > both in the algebraic factor and its remainder? > > A cubic factor would be off topic, in this thread, The primes p for which p^3 is a cubic factor are a subset of the primes p' for which p'^2 is a square factor, which are a superset of the primes p'' for which p''^2 is a square factor, but where p'' does not divide the algebraic factor. It's hardly unrelated. Your change of subject to looking at a different form is a bigger change, Herr Schwartzentopf. > and then a moderator might object :-? You appear to have a difficulty distinguishing topic drift, and topics which shouldn't have started in the first place. Your petulance is unbecoming. Phil djbroadhurst Oct 14, 2011 ----------------------- Puzzle: Find a prime p for which there exist an integer n such that p^3 divides n^n+(n+1)^(n+1) and 10^500 < n < p*sqrt(3) < 10^600. Comment: It takes a few CPU-seconds to find such a PRP, by a systematic method, and less than a minute to prove it prime. David djbroadhurst Oct 15, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Puzzle: Find a prime p for which there exists an integer n such that > p^3 divides n^n+(n+1)^(n+1) and 10^500 < n < p*sqrt(3) < 10^600. Hint: n=661236610717237398793705709083854763671279646; p=381765135195632792959100810331957408101589361; if(Mod(n,p^3)^n+Mod(n+1,p^3)^(n+1)==0,print("use google")); use google David (encouraging googling) Walter Nissen Oct 18, 2011 ----------------------- mikeoakes2 counted the number of times small p divides small np ( n ) = n^n + (n+1)^(n+1) and wrote : > This count is never zero (for p>2) This is an easy consequence of p | np ( 2p - 2 ) . The case of even p is very different . A related question is : When is that p the least prime factor of np ( 2p - 2 ) ? Cheers , Walter djbroadhurst Oct 18, 2011 ----------------------- For p = 5 mod 6, let N(p) be the number of positive integers n < p*(p-1) such that p^2 divides n^n+(n+1)^(n+1). Then I conjecture that 1) the average value of N(p) is close to 1; 2) N(p) = 0 for about 5/6 of the primes p = 5 mod 6; 3) N(106751) = 1050 is the maximum for p < 10^6. The third conjecture is dependent on a previous conjecture in http://physics.open.ac.uk/~dbroadhu/cert/cong5m6.txt David djbroadhurst Oct 21, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Puzzle: Find a prime p for which there exist an integer n such that > p^3 divides n^n+(n+1)^(n+1) and 10^500 < n < p*sqrt(3) < 10^600. As there were no takers, I shall post a solution: Lucas solution: p = V(4,1,971)/4; n = (3*U(4,1,971) - 1)/2. I have some concise explanatory notes on this problem, with larger historical examples, if anyone will ask me to post them. Else, silence... David djbroadhurst Oct 21, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > I have some concise explanatory notes on this problem, > with larger historical examples, if anyone will ask me > to post them. Phil has kindly asked me to do so. > Puzzle: Find a prime p for which there exist an integer n such that > p^3 divides n^n+(n+1)^(n+1) and 10^500 < n < p*sqrt(3) < 10^600. > Lucas solution: p = V(4,1,971)/4; n = (3*U(4,1,971) - 1)/2. Notes: p = V(4,1,k)/4 is a proven prime for these primes k: 3, 5, 7, 11, 13, 17, 19, 79, 151, 199, 233, 251, 317, 863, 971, 3049, 7451, 7487, 18869. At present, http://oeis.org/A117808 lists primes only up to V(4,1,79)/4 = 381765135195632792959100810331957408101589361 and chooses to include 3, as the floor of V(4,1,2)/4 = 7/2. With n = (3*U(4,1,k) - 1)/2, we solve n^2 + n + 1 = 3*p^2. Then (n+1)^(n+1) == +/- n^n (mod p^4) for k == +/- 1 (mod 4). Pari-GP took 0.3 seconds to find k = 971 and proved primality in 30 seconds, thus solving the puzzle, at 555 digits. We also have Williams-Lenstra proofs at k = 7451 and 7487: http://tech.groups.yahoo.com/group/primenumbers/message/2485 while the cases k = 3049 and 18869 solve a different puzzle, with p^4|(n+1)^(n+1)-n^n. The first is an easy proof for PFGW: > Calling N-1 BLS with factored part 47.12% > and helper 15.11% (156.54% proof) > lucasV(4,1,3049)/4 is prime! (2.7309s+0.0453s). and the second, at 10792 digits, was proven in 2009: http://tech.groups.yahoo.com/group/primenumbers/message/20127 David Broadhurst, 22 October 2011 djbroadhurst Oct 22, 2011 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Lucas solution: p = V(4,1,971)/4; n = (3*U(4,1,971) - 1)/2. > > Notes: p = V(4,1,k)/4 is a proven prime for these primes k: > 3, 5, 7, 11, 13, 17, 19, 79, 151, 199, 233, > 251, 317, 863, 971, 3049, 7451, 7487, 18869. PS: I know of no proof of the primality of http://www.primenumbers.net/prptop/searchform.php?form=?32869)? David Walter Nissen Message 81 of 81 , Nov 29 9:34 AM ----------------------- Hi , all , Not even draft yet , let alone published : http://upforthecount.com/math/nnp.html still needs a lot of work . But , I have updated the top of the main table : http://upforthecount.com/math/nnp2.txt with complete factorizations now extending through np ( 90 ) . When is np ( n ) prime ? So far , only for 1 , 2 and 3 . When n mod 6 = 4 , np ( n ) has at least 3 algebraic factors , 3 and n^2 + n + 1 ( twice ) . But what about the residue ( primitive part ? ) ? When is this prime ? n t n^n + (n+1)^(n+1) 4 4 3 * 7 * 7 * 23 16 6 3 * 7 * 7 * 13 * 13 * 34041259347101651 Any others ? Cheers , Walter