## x^y - y^x

Expand Messages
• Paul Leyland maintains a table of primes of the form x^y + y^x. Has anyone looked into the form x^y - y^x, and if not, is there any reason or has it just been
Message 1 of 29 , Apr 24, 2005
Paul Leyland maintains a table of primes of the form x^y + y^x. Has anyone
looked into the form x^y - y^x, and if not, is there any reason or has it
just been overlooked?

I gave a bit of thought to them, and other than the condition gcd(x,y) = 1,
which was already known for x^y + y^x, I only came up with the following: x^y
- y^x = -(y^x - x^y), and in particular x^y - y^x is positive if x < y (the
sole exceptions are the trivial x = 1 ones and 2^3 - 3^2 = -1), so those two
conditions cut the search space by 6/pi^2 = 0.61 and 0.5 respectively.

I have exhaustively searched the range 1 < x < y <= 500 using a GP script with
ispseudoprime() calls, and later proving the primality of PRPs using PRIMO.
I'm currently using PFGW with the -f switch to search the range 1 < x,500 < y
<= 2000. I can't search far beyond this without a proper sieve. Perhaps Mark
Rodenkirch could patch MultiSieve to sieve this form? Since it already
supports x^y + y^x I guess the changes involved would be trivial.

Here are the proven primes:

3^4 - 4^3
2^5 - 5^2
2^7 - 7^2
6^7 - 7^6
2^9 - 9^2
3^10 - 10^3
9^10 - 10^9
8^11 - 11^8
6^13 - 13^6
12^13 - 13^12
5^14 - 14^5
11^14 - 14^11
2^17 - 17^2
2^19 - 19^2
7^20 - 20^7
7^24 - 24^7
12^25 - 25^12
5^26 - 26^5
21^32 - 32^21
6^35 - 35^6
13^38 - 38^13
31^42 - 42^31
32^43 - 43^32
44^45 - 45^44
24^49 - 49^24
9^50 - 50^9
2^51 - 51^2
32^51 - 51^32
3^52 - 52^3
2^53 - 53^2
6^53 - 53^6
23^60 - 60^23
41^60 - 60^41
15^68 - 68^15
34^69 - 69^34
24^71 - 71^24
19^72 - 72^19
11^80 - 80^11
2^81 - 81^2
2^83 - 83^2
42^85 - 85^42
50^87 - 87^50
63^88 - 88^63
81^88 - 88^81
8^89 - 89^8
14^89 - 89^14
30^91 - 91^30
58^93 - 93^58
68^95 - 95^68
20^97 - 97^20
29^98 - 98^29
81^98 - 98^81
14^101 - 101^14
74^109 - 109^74
47^110 - 110^47
3^112 - 112^3
15^112 - 112^15
6^115 - 115^6
2^119 - 119^2
63^124 - 124^63
109^134 - 134^109
98^135 - 135^98
50^143 - 143^50
6^145 - 145^6
109^150 - 150^109
115^168 - 168^115
125^168 - 168^125
54^169 - 169^54
98^169 - 169^98
20^173 - 173^20
130^177 - 177^130
150^179 - 179^150
61^180 - 180^61
30^181 - 181^30
132^181 - 181^132
103^182 - 182^103
2^189 - 189^2
95^198 - 198^95
21^200 - 200^21
8^201 - 201^8
115^206 - 206^115
24^211 - 211^24
3^212 - 212^3
11^212 - 212^11
2^219 - 219^2
63^220 - 220^63
18^221 - 221^18
145^222 - 222^145
15^224 - 224^15
2^227 - 227^2
11^230 - 230^11
109^234 - 234^109
139^240 - 240^139
66^245 - 245^66
44^247 - 247^44
57^250 - 250^57
234^251 - 251^234
255^268 - 268^255
203^270 - 270^203
219^272 - 272^219
10^273 - 273^10
93^278 - 278^93
119^282 - 282^119
18^283 - 283^18
257^284 - 284^257
255^292 - 292^255
205^294 - 294^205
56^295 - 295^56
192^295 - 295^192
2^301 - 301^2
6^307 - 307^6
117^310 - 310^117
171^310 - 310^171
12^325 - 325^12
32^327 - 327^32
95^332 - 332^95
177^332 - 332^177
321^334 - 334^321
44^335 - 335^44
137^338 - 338^137
127^342 - 342^127
3^346 - 346^3
193^360 - 360^193
96^365 - 365^96
62^373 - 373^62
240^383 - 383^240
354^391 - 391^354
128^397 - 397^128
10^399 - 399^10
342^403 - 403^342
3^406 - 406^3
71^408 - 408^71
354^415 - 415^354
104^417 - 417^104
195^418 - 418^195
337^420 - 420^337
133^422 - 422^133
42^425 - 425^42
24^427 - 427^24

Here are the pseudoprimes:

174^439 - 439^174
42^445 - 445^42
2^455 - 455^2
2^461 - 461^2
101^462 - 462^101
172^471 - 471^172
24^481 - 481^24
83^486 - 486^83
384^487 - 487^384
121^488 - 488^121
173^488 - 488^173
114^491 - 491^114
329^494 - 494^329
240^497 - 497^240
455^498 - 498^455
50^501 - 501^50
3^512 - 512^3
294^515 - 515^294
485^516 - 516^485
299^518 - 518^299
390^527 - 527^390
363^538 - 538^363
398^539 - 539^398
182^547 - 547^182
475^552 - 552^475
152^559 - 559^152
360^559 - 559^360
398^563 - 563^398
14^579 - 579^14
244^579 - 579^244
323^584 - 584^323
272^587 - 587^272
332^589 - 589^332
232^597 - 597^232
323^606 - 606^323
392^607 - 607^392
215^608 - 608^215
497^608 - 608^497
2^623 - 623^2
30^631 - 631^30
532^633 - 633^532
535^636 - 636^535
302^641 - 641^302
362^653 - 653^362
14^655 - 655^14
48^661 - 661^48
119^668 - 668^119
305^668 - 668^305
629^668 - 668^629
248^669 - 669^248
116^675 - 675^116
133^680 - 680^133
301^692 - 692^301
201^694 - 694^201
171^704 - 704^171
62^707 - 707^62
446^715 - 715^446
584^715 - 715^584
49^720 - 720^49
38^721 - 721^38
240^721 - 721^240
389^722 - 722^389
81^724 - 724^81
181^732 - 732^181
38^735 - 735^38
233^740 - 740^233
398^741 - 741^398
722^745 - 745^722
649^774 - 774^649
685^774 - 774^685
691^774 - 774^691
482^775 - 775^482
113^782 - 782^113
37^786 - 786^37
334^789 - 789^334
159^794 - 794^159
325^798 - 798^325
428^809 - 809^428
21^814 - 814^21
18^821 - 821^18
282^821 - 821^282
139^824 - 824^139
12^833 - 833^12
747^842 - 842^747
338^859 - 859^338
509^864 - 864^509
181^878 - 878^181
594^881 - 881^594
883^884 - 884^883
165^892 - 892^165
472^897 - 897^472
40^903 - 903^40
272^903 - 903^272
49^908 - 908^49
398^913 - 913^398
272^917 - 917^272
866^925 - 925^866
765^926 - 926^765
847^930 - 930^847
91^932 - 932^91
740^933 - 933^740
686^937 - 937^686
702^941 - 941^702
192^943 - 943^192
770^943 - 943^770
349^944 - 944^349
373^944 - 944^373
451^948 - 948^451
841^950 - 950^841
908^961 - 961^908
291^962 - 962^291
688^975 - 975^688
8^977 - 977^8
637^984 - 984^637
38^985 - 985^38
42^1003 - 1003^42
849^1018 - 1018^849
789^1030 - 1030^789
408^1031 - 1031^408

As anyone can check against Paul Leyland's tables at
http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y - y^x is
much more productive than x^y + y^x. For x,y < 1000, there are 254 x^y - y^x
primes and only 87 x^y + y^x primes. Frankly, this a mistery to a me. I see
no reason for them to be any different, even taking into account the fact
that x^y - y^x < x^y + y^x: the ratio x^y/y^x is always huge, even in the
most favorable case, x + 1 = y (here the ratio seems to be well approximated
by (x+y)/2e ~ 0.184(x+y)), so that the probability that each form is prime,
log(x^y + y^x) and log(x^y - y^x) are essentially the same.

Interestingly, 2^9 + 9^2 and 2^9 - 9^2 is a `twin' pair, and the only one I've
found yet. I'm not hoping to find a larger pair, but it would be a very
welcome surprise.

Décio
• Hi, I searched for a while using that form, but then switched to x^y +/- y^x +/- x*y. This gave fairly good results as regards the number of large PrP s found
Message 2 of 29 , Apr 24, 2005
Hi,

I searched for a while using that form, but then switched to x^y +/- y^x
+/- x*y. This gave fairly good results as regards the number of large
PrP's found with PFGW.

Kevin.

At 06:16 AM 25/04/2005, Décio Luiz Gazzoni Filho wrote:

>Paul Leyland maintains a table of primes of the form x^y + y^x. Has anyone
>looked into the form x^y - y^x, and if not, is there any reason or has it
>just been overlooked?
>
>I gave a bit of thought to them, and other than the condition gcd(x,y) = 1,
>which was already known for x^y + y^x, I only came up with the following: x^y
>- y^x = -(y^x - x^y), and in particular x^y - y^x is positive if x < y (the
>sole exceptions are the trivial x = 1 ones and 2^3 - 3^2 = -1), so those two
>conditions cut the search space by 6/pi^2 = 0.61 and 0.5 respectively.
>
>I have exhaustively searched the range 1 < x < y <= 500 using a GP script
>with
>ispseudoprime() calls, and later proving the primality of PRPs using PRIMO.
>I'm currently using PFGW with the -f switch to search the range 1 < x,500 < y
><= 2000. I can't search far beyond this without a proper sieve. Perhaps Mark
>Rodenkirch could patch MultiSieve to sieve this form? Since it already
>supports x^y + y^x I guess the changes involved would be trivial.
>
>Here are the proven primes:
>
>3^4 - 4^3
>2^5 - 5^2
>2^7 - 7^2
>6^7 - 7^6
>2^9 - 9^2
>3^10 - 10^3
>9^10 - 10^9
>8^11 - 11^8
>6^13 - 13^6
>12^13 - 13^12
>5^14 - 14^5
>11^14 - 14^11
>2^17 - 17^2
>2^19 - 19^2
>7^20 - 20^7
>7^24 - 24^7
>12^25 - 25^12
>5^26 - 26^5
>21^32 - 32^21
>6^35 - 35^6
>13^38 - 38^13
>31^42 - 42^31
>32^43 - 43^32
>44^45 - 45^44
>24^49 - 49^24
>9^50 - 50^9
>2^51 - 51^2
>32^51 - 51^32
>3^52 - 52^3
>2^53 - 53^2
>6^53 - 53^6
>23^60 - 60^23
>41^60 - 60^41
>15^68 - 68^15
>34^69 - 69^34
>24^71 - 71^24
>19^72 - 72^19
>11^80 - 80^11
>2^81 - 81^2
>2^83 - 83^2
>42^85 - 85^42
>50^87 - 87^50
>63^88 - 88^63
>81^88 - 88^81
>8^89 - 89^8
>14^89 - 89^14
>30^91 - 91^30
>58^93 - 93^58
>68^95 - 95^68
>20^97 - 97^20
>29^98 - 98^29
>81^98 - 98^81
>14^101 - 101^14
>74^109 - 109^74
>47^110 - 110^47
>3^112 - 112^3
>15^112 - 112^15
>6^115 - 115^6
>2^119 - 119^2
>63^124 - 124^63
>109^134 - 134^109
>98^135 - 135^98
>50^143 - 143^50
>6^145 - 145^6
>109^150 - 150^109
>115^168 - 168^115
>125^168 - 168^125
>54^169 - 169^54
>98^169 - 169^98
>20^173 - 173^20
>130^177 - 177^130
>150^179 - 179^150
>61^180 - 180^61
>30^181 - 181^30
>132^181 - 181^132
>103^182 - 182^103
>2^189 - 189^2
>95^198 - 198^95
>21^200 - 200^21
>8^201 - 201^8
>115^206 - 206^115
>24^211 - 211^24
>3^212 - 212^3
>11^212 - 212^11
>2^219 - 219^2
>63^220 - 220^63
>18^221 - 221^18
>145^222 - 222^145
>15^224 - 224^15
>2^227 - 227^2
>11^230 - 230^11
>109^234 - 234^109
>139^240 - 240^139
>66^245 - 245^66
>44^247 - 247^44
>57^250 - 250^57
>234^251 - 251^234
>255^268 - 268^255
>203^270 - 270^203
>219^272 - 272^219
>10^273 - 273^10
>93^278 - 278^93
>119^282 - 282^119
>18^283 - 283^18
>257^284 - 284^257
>255^292 - 292^255
>205^294 - 294^205
>56^295 - 295^56
>192^295 - 295^192
>2^301 - 301^2
>6^307 - 307^6
>117^310 - 310^117
>171^310 - 310^171
>12^325 - 325^12
>32^327 - 327^32
>95^332 - 332^95
>177^332 - 332^177
>321^334 - 334^321
>44^335 - 335^44
>137^338 - 338^137
>127^342 - 342^127
>3^346 - 346^3
>193^360 - 360^193
>96^365 - 365^96
>62^373 - 373^62
>240^383 - 383^240
>354^391 - 391^354
>128^397 - 397^128
>10^399 - 399^10
>342^403 - 403^342
>3^406 - 406^3
>71^408 - 408^71
>354^415 - 415^354
>104^417 - 417^104
>195^418 - 418^195
>337^420 - 420^337
>133^422 - 422^133
>42^425 - 425^42
>24^427 - 427^24
>
>Here are the pseudoprimes:
>
>174^439 - 439^174
>42^445 - 445^42
>2^455 - 455^2
>2^461 - 461^2
>101^462 - 462^101
>172^471 - 471^172
>24^481 - 481^24
>83^486 - 486^83
>384^487 - 487^384
>121^488 - 488^121
>173^488 - 488^173
>114^491 - 491^114
>329^494 - 494^329
>240^497 - 497^240
>455^498 - 498^455
>50^501 - 501^50
>3^512 - 512^3
>294^515 - 515^294
>485^516 - 516^485
>299^518 - 518^299
>390^527 - 527^390
>363^538 - 538^363
>398^539 - 539^398
>182^547 - 547^182
>475^552 - 552^475
>152^559 - 559^152
>360^559 - 559^360
>398^563 - 563^398
>14^579 - 579^14
>244^579 - 579^244
>323^584 - 584^323
>272^587 - 587^272
>332^589 - 589^332
>232^597 - 597^232
>323^606 - 606^323
>392^607 - 607^392
>215^608 - 608^215
>497^608 - 608^497
>2^623 - 623^2
>30^631 - 631^30
>532^633 - 633^532
>535^636 - 636^535
>302^641 - 641^302
>362^653 - 653^362
>14^655 - 655^14
>48^661 - 661^48
>119^668 - 668^119
>305^668 - 668^305
>629^668 - 668^629
>248^669 - 669^248
>116^675 - 675^116
>133^680 - 680^133
>301^692 - 692^301
>201^694 - 694^201
>171^704 - 704^171
>62^707 - 707^62
>446^715 - 715^446
>584^715 - 715^584
>49^720 - 720^49
>38^721 - 721^38
>240^721 - 721^240
>389^722 - 722^389
>81^724 - 724^81
>181^732 - 732^181
>38^735 - 735^38
>233^740 - 740^233
>398^741 - 741^398
>722^745 - 745^722
>649^774 - 774^649
>685^774 - 774^685
>691^774 - 774^691
>482^775 - 775^482
>113^782 - 782^113
>37^786 - 786^37
>334^789 - 789^334
>159^794 - 794^159
>325^798 - 798^325
>428^809 - 809^428
>21^814 - 814^21
>18^821 - 821^18
>282^821 - 821^282
>139^824 - 824^139
>12^833 - 833^12
>747^842 - 842^747
>338^859 - 859^338
>509^864 - 864^509
>181^878 - 878^181
>594^881 - 881^594
>883^884 - 884^883
>165^892 - 892^165
>472^897 - 897^472
>40^903 - 903^40
>272^903 - 903^272
>49^908 - 908^49
>398^913 - 913^398
>272^917 - 917^272
>866^925 - 925^866
>765^926 - 926^765
>847^930 - 930^847
>91^932 - 932^91
>740^933 - 933^740
>686^937 - 937^686
>702^941 - 941^702
>192^943 - 943^192
>770^943 - 943^770
>349^944 - 944^349
>373^944 - 944^373
>451^948 - 948^451
>841^950 - 950^841
>908^961 - 961^908
>291^962 - 962^291
>688^975 - 975^688
>8^977 - 977^8
>637^984 - 984^637
>38^985 - 985^38
>42^1003 - 1003^42
>849^1018 - 1018^849
>789^1030 - 1030^789
>408^1031 - 1031^408
>
>As anyone can check against Paul Leyland's tables at
>http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y - y^x is
>much more productive than x^y + y^x. For x,y < 1000, there are 254 x^y - y^x
>primes and only 87 x^y + y^x primes. Frankly, this a mistery to a me. I see
>no reason for them to be any different, even taking into account the fact
>that x^y - y^x < x^y + y^x: the ratio x^y/y^x is always huge, even in the
>most favorable case, x + 1 = y (here the ratio seems to be well approximated
>by (x+y)/2e ~ 0.184(x+y)), so that the probability that each form is prime,
>log(x^y + y^x) and log(x^y - y^x) are essentially the same.
>
>Interestingly, 2^9 + 9^2 and 2^9 - 9^2 is a `twin' pair, and the only one
>I've
>found yet. I'm not hoping to find a larger pair, but it would be a very
>welcome surprise.
>
>Décio
>
>
>
>Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
>The Prime Pages : http://www.primepages.org/
>
>
>
>
>
>
• ... Hmm, interesting and something to which I ve not given any thought. One almost trivial observation is that differences of powers tend to be less likely to
Message 3 of 29 , Apr 28, 2005
On Sun, 2005-04-24 at 21:16, Décio Luiz Gazzoni Filho wrote:
> Paul Leyland maintains a table of primes of the form x^y + y^x. Has anyone
> looked into the form x^y - y^x, and if not, is there any reason or has it
> just been overlooked?
...
> As anyone can check against Paul Leyland's tables at
> http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y - y^x is
> much more productive than x^y + y^x. For x,y < 1000, there are 254 x^y - y^x
> primes and only 87 x^y + y^x primes. Frankly, this a mistery to a me. I see
> no reason for them to be any different, even taking into account the fact
> that x^y - y^x < x^y + y^x: the ratio x^y/y^x is always huge, even in the
> most favorable case, x + 1 = y (here the ratio seems to be well approximated
> by (x+y)/2e ~ 0.184(x+y)), so that the probability that each form is prime,
> log(x^y + y^x) and log(x^y - y^x) are essentially the same.

Hmm, interesting and something to which I've not given any thought.

One almost trivial observation is that differences of powers tend to be
less likely to be prime than sums of powers because of the identity
(a-b)(a+b) = a^2-b^2. However, the requirement that gcd(x,y) = 1
prevents that identity being useful in the present circumstances. I
don't immediately see why x^y-y^x, with the condition that gcd(x,y) = 1,
should be more likely to be prime than x^y+y^x under the same
restriction.

I'll think about it. Thanks for drawing the problem my attention.

Perhaps I should host another table of primes and strong pseudoptimes.
Is there any support for this proposal

Paul
• ... However, consider the least prime of this form, 3^4 - 4^3 = 17. In this case, the expression could be rewritten as 9^2 - 8^2 = (9 - 8)(9 + 8) = 1*17 = 17.
Message 4 of 29 , Apr 28, 2005
On Thursday 28 April 2005 15:21, Paul Leyland wrote:
> On Sun, 2005-04-24 at 21:16, Décio Luiz Gazzoni Filho wrote:
> > Paul Leyland maintains a table of primes of the form x^y + y^x. Has
> > anyone looked into the form x^y - y^x, and if not, is there any reason or
> > has it just been overlooked?
>
> ...
>
> > As anyone can check against Paul Leyland's tables at
> > http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y - y^x is
> > much more productive than x^y + y^x. For x,y < 1000, there are 254 x^y -
> > y^x primes and only 87 x^y + y^x primes. Frankly, this a mistery to a me.
> > I see no reason for them to be any different, even taking into account
> > the fact that x^y - y^x < x^y + y^x: the ratio x^y/y^x is always huge,
> > even in the most favorable case, x + 1 = y (here the ratio seems to be
> > well approximated by (x+y)/2e ~ 0.184(x+y)), so that the probability that
> > each form is prime, log(x^y + y^x) and log(x^y - y^x) are essentially the
> > same.
>
> Hmm, interesting and something to which I've not given any thought.
>
> One almost trivial observation is that differences of powers tend to be
> less likely to be prime than sums of powers because of the identity
> (a-b)(a+b) = a^2-b^2. However, the requirement that gcd(x,y) = 1
> prevents that identity being useful in the present circumstances. I
> don't immediately see why x^y-y^x, with the condition that gcd(x,y) = 1,
> should be more likely to be prime than x^y+y^x under the same
> restriction.

However, consider the least prime of this form, 3^4 - 4^3 = 17. In this case,
the expression could be rewritten as 9^2 - 8^2 = (9 - 8)(9 + 8) = 1*17 = 17.
Checking through my logs unsurprisingly reveals that this is the only case
where both x^y and y^x are squares.

Décio

[Non-text portions of this message have been removed]
• ... I addressed that preemptively in the first email I sent. Have a look at the part emphasized above. Décio [Non-text portions of this message have been
Message 5 of 29 , Apr 28, 2005
On Thursday 28 April 2005 19:01, you wrote:
> Décio Luiz Gazzoni Filho wrote:
> >On Thursday 28 April 2005 15:21, Paul Leyland wrote:
> >>On Sun, 2005-04-24 at 21:16, Décio Luiz Gazzoni Filho wrote:
> >>>Paul Leyland maintains a table of primes of the form x^y + y^x. Has
> >>>anyone looked into the form x^y - y^x, and if not, is there any reason
> >>> or has it just been overlooked?
> >>
> >>...
> >>
> >>>As anyone can check against Paul Leyland's tables at
> >>>http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y - y^x
> >>> is much more productive than x^y + y^x. For x,y < 1000, there are 254
> >>> x^y - y^x primes and only 87 x^y + y^x primes. Frankly, this a mistery

----- PAY ATTENTION TO THIS PART -----

> >>> to a me. I see no reason for them to be any different, even taking into
> >>> account the fact that x^y - y^x < x^y + y^x: the ratio x^y/y^x is
> >>> always huge, even in the most favorable case, x + 1 = y (here the ratio
> >>> seems to be well approximated by (x+y)/2e ~ 0.184(x+y)), so that the
> >>> probability that each form is prime, log(x^y + y^x) and log(x^y - y^x)
> >>> are essentially the same.

----- PAY ATTENTION TO THIS PART -----

> >>
> >>Hmm, interesting and something to which I've not given any thought.
> >>
> >>One almost trivial observation is that differences of powers tend to be
> >>less likely to be prime than sums of powers because of the identity
> >>(a-b)(a+b) = a^2-b^2. However, the requirement that gcd(x,y) = 1
> >>prevents that identity being useful in the present circumstances. I
> >>don't immediately see why x^y-y^x, with the condition that gcd(x,y) = 1,
> >>should be more likely to be prime than x^y+y^x under the same
> >>restriction.
> >
> >However, consider the least prime of this form, 3^4 - 4^3 = 17. In this
> > case, the expression could be rewritten as 9^2 - 8^2 = (9 - 8)(9 + 8) =
> > 1*17 = 17. Checking through my logs unsurprisingly reveals that this is
> > the only case where both x^y and y^x are squares.
> >
> >Décio
> >
> >
> >[Non-text portions of this message have been removed]
>
> Hi!
> First it looks curious that x^y-y^x have more primes than x^y+y^x.
> However, while the number in the plus-case grow fast for large and about
> equal x and y,
> in the minus-case they get smaller while x and y come more equal.
> As the density of primes is larger for smaller number, this could be one
> possible reason.

I addressed that preemptively in the first email I sent. Have a look at the
part emphasized above.

Décio

[Non-text portions of this message have been removed]
• ... y^x is ... x^y - y^x ... me. Pierre de Fermat solves de mystery. In the case of N = x^y + y^x (only), if x or y is one less than a prime p, then x^y + y^x
Message 6 of 29 , Apr 28, 2005
--- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
<decio@d...> wrote:
>
> As anyone can check against Paul Leyland's tables at
> http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y -
y^x is
> much more productive than x^y + y^x. For x,y < 1000, there are 254
x^y - y^x
> primes and only 87 x^y + y^x primes. Frankly, this a mistery to a
me.

Pierre de Fermat solves de mystery.

In the case of N = x^y + y^x (only), if x or y is one less than a
prime p, then x^y + y^x contains a factor of p. (Assuming the other
term x or y doesn't contain a factor of p) . Thus x^y + y^n cannot be
prime if x or y is one less than a prime.

Proof:

Let x^y + y^x = N

Let x = p-1

Then y is odd. We assume that y has no factor of p.

(p-1)^y + y^(p-1) = N

-1 + y^(p-1) = N modp

By Fermat,

-1 + 1 = N modp

0=N modp

Thus N has a factor of p, so cannot be prime.

Mark
• Just an additional tidbit. For the expression x^y - y^x to be prime, neither x nor y can be an even square. Proof: Assume x is an even square, so x = (2m)^2
Message 7 of 29 , Apr 28, 2005
Just an additional tidbit. For the expression

x^y - y^x

to be prime, neither x nor y can be an even square.

Proof:

Assume x is an even square, so x = (2m)^2

Then

(2m)^2y - y^(2m*2m)

is clearly a difference of squares and is factored to

((2m)^y - y^(2m))((2m)^y + y^(2m))

and so is not prime unless the first term is +/- 1. (And that might
only occur when m=1 and y=3.)

Mark
• ... Amazing work, Mark. I would never have thought of that. I m not sure that it can account for all of the differences, but regardless, it s a very
Message 8 of 29 , Apr 28, 2005
On Thursday 28 April 2005 21:25, you wrote:
> Pierre de Fermat solves de mystery.
>
> In the case of N = x^y + y^x (only), if x or y is one less than a
> prime p, then x^y + y^x contains a factor of p. (Assuming the other
> term x or y doesn't contain a factor of p) . Thus x^y + y^n cannot be
> prime if x or y is one less than a prime.
>
> Proof:
>
> Let x^y + y^x = N
>
> Let x = p-1
>
> Then y is odd. We assume that y has no factor of p.
>
> (p-1)^y + y^(p-1) = N
>
> -1 + y^(p-1) = N modp
>
> By Fermat,
>
> -1 + 1 = N modp
>
> 0=N modp
>
> Thus N has a factor of p, so cannot be prime.

Amazing work, Mark. I would never have thought of that. I'm not sure that it
can account for all of the differences, but regardless, it's a very
interesting discovery. I wonder if it can be generalized?

Of note, divisibility of x^y - y^x by p means that x^y == y^x mod p. Surely
this equation must have interesting properties?

Décio

[Non-text portions of this message have been removed]
• ... Yes I think there is more to it if one looks closely. Paul s x^y + y^x somehow loses about 66 percent of prime candidates compared to x^y - y^x. Since
Message 9 of 29 , Apr 28, 2005
--- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
<decio@d...> wrote:
>I'm not sure that it
> can account for all of the differences, but regardless, it's a very
> interesting discovery. I wonder if it can be generalized?
>

Yes I think there is more to it if one looks closely. Paul's x^y + y^x
somehow loses about 66 percent of prime candidates compared to x^y -
y^x. Since there are 94 primes up to 500 and 250 even numbers, that
represents a loss of 'only' 39 percent by the p-1 aspect. There's
still a good percentage to account for. Perhaps as you say some kind o
of generalizing principle may account for much of the rest, I'm not
sure.

Mark
• ... p. Surely ... Sure. Of course, if x and y share a factor of p then x^y - y^x does. That s why we make sure x and y are relatively prime. But did we know
Message 10 of 29 , Apr 29, 2005
--- In primenumbers@yahoogroups.com, Décio Luiz Gazzoni Filho
<decio@d...> wrote:
> Of note, divisibility of x^y - y^x by p means that x^y == y^x mod
p. Surely
> this equation must have interesting properties?
>

Sure. Of course, if x and y share a factor of p then x^y - y^x does.
That's why we make sure x and y are relatively prime.

But did we know that x-1 and y-1 must also be relatively prime? It is
easy to show that if x-1 and y-1 share a factor of p, then x^y - y^x
does!

Futhermore, the even number -1 must also be relatively prime to the
other number + 1. It is easy to show that if the even number - 1
shares a factor p with the other (odd) number + 1, then x^y - y^n has
the same factor p as well!

In a related fashion with Paul's equation of x^y + y^x, not only must
x and y be relatively prime, but x+1 and y+1 must be relatively
prime. If x+1 and y+1 share a common factor of p, then so does x^y +
y^x !

Furthermore, the even number + 1 must be relatively prime to the
other number -1. If they share a common factor of p, then so does x^y
+ y^x !

When we count up all the qualifying x,y pairs up to 500 for x^y - y^x
and for x^y + y^x (with Paul's equation, x and y's one less than a
prime are disqualified), we find that about 2.2 times more pairs
qualify for your expression than for Paul's. This is starting to
better approach the prime count difference for yours and Paul's
expressions.

Mark
• Sorry for replying to a very old thread, but I wondered if anyone has explored further with X^Y-Y^X (or for that matter X^Y+Y^X) in recent years. Some of the
Message 11 of 29 , Aug 13, 2009
Sorry for replying to a very old thread, but I wondered if anyone has
explored further with X^Y-Y^X (or for that matter X^Y+Y^X) in recent
years. Some of the PRPs listed are within easy reach of Primo, and
I'd be interested in working on some of them, but just want to know

Nathan
• An anecdotal remark. I don t see the no use in USA warning. Can this software be used in USA now? http://www.ellipsa.eu/public/misc/license.html Cino To:
Message 12 of 29 , Aug 13, 2009
An anecdotal remark.

I don't see the no use in USA warning. Can this software be used in USA now?

Cino

From: windrunner@...
Date: Thu, 13 Aug 2009 11:46:00 -0400
Subject: Re: [PrimeNumbers] Re: x^y - y^x

Sorry for replying to a very old thread, but I wondered if anyone has
explored further with X^Y-Y^X (or for that matter X^Y+Y^X) in recent
years. Some of the PRPs listed are within easy reach of Primo, and
I'd be interested in working on some of them, but just want to know

Nathan

[Non-text portions of this message have been removed]
• Hello, I think you can use PRIMO. Look here : http://www.sourcecodeonline.com/details/primo.html best Norman [Non-text portions of this message have been
Message 13 of 29 , Aug 13, 2009
Hello, I think you can use PRIMO.

Look here :

http://www.sourcecodeonline.com/details/primo.html

best

Norman

[Non-text portions of this message have been removed]
• It looks from the homepage like it can be used in the US, just you are at your own risk for patents (and I think the chance of someone going after me is
Message 14 of 29 , Aug 13, 2009
It looks from the homepage like it can be used in the US, just you are
at your own risk for patents (and I think the chance of someone going
after me is approximately zero). Marcel also told me years ago that
as a paid user of the early versions, I had his permission to do so

Nathan

On Thu, Aug 13, 2009 at 12:31 PM, Norman Luhn<nluhn@...> wrote:
>
>
> Hello, I think you can use PRIMO.
>
> Look here :
>
> http://www.sourcecodeonline.com/details/primo.html
>
>
>
>
>
>
>
>
>
> best
>
> Norman
>
> [Non-text portions of this message have been removed]
>
>
• ... (snip) ... These four, at least, are prime. ... I am working on the above 3 now. Should probably just go ahead and do the last - it should take under a
Message 15 of 29 , Aug 13, 2009
2005/4/24 Décio Luiz Gazzoni Filho <decio@...>:
> Paul Leyland maintains a table of primes of the form x^y + y^x. Has anyone
> looked into the form x^y - y^x, and if not, is there any reason or has it
> just been overlooked?
>
> I gave a bit of thought to them, and other than the condition gcd(x,y) = 1,
> which was already known for x^y + y^x, I only came up with the following:
> x^y
> - y^x = -(y^x - x^y), and in particular x^y - y^x is positive if x < y (the
> sole exceptions are the trivial x = 1 ones and 2^3 - 3^2 = -1), so those two
> conditions cut the search space by 6/pi^2 = 0.61 and 0.5 respectively.
>
> I have exhaustively searched the range 1 < x < y <= 500 using a GP script
> with
> ispseudoprime() calls, and later proving the primality of PRPs using PRIMO.
> I'm currently using PFGW with the -f switch to search the range 1 < x,500 <
> y
> <= 2000. I can't search far beyond this without a proper sieve. Perhaps Mark
> Rodenkirch could patch MultiSieve to sieve this form? Since it already
> supports x^y + y^x I guess the changes involved would be trivial.
>
> Here are the proven primes:
(snip)
> 42^425 - 425^42
> 24^427 - 427^24
>
> Here are the pseudoprimes:
>
> 174^439 - 439^174
> 42^445 - 445^42
> 2^455 - 455^2
> 2^461 - 461^2

These four, at least, are prime.
> 101^462 - 462^101
> 172^471 - 471^172
> 24^481 - 481^24

I am working on the above 3 now. Should probably just go ahead and do
the last - it should take under a minute.

Nathan

> 83^486 - 486^83
> 384^487 - 487^384
> 121^488 - 488^121
> 173^488 - 488^173
> 114^491 - 491^114
> 329^494 - 494^329
> 240^497 - 497^240
> 455^498 - 498^455
> 50^501 - 501^50
> 3^512 - 512^3
> 294^515 - 515^294
> 485^516 - 516^485
> 299^518 - 518^299
> 390^527 - 527^390
> 363^538 - 538^363
> 398^539 - 539^398
> 182^547 - 547^182
> 475^552 - 552^475
> 152^559 - 559^152
> 360^559 - 559^360
> 398^563 - 563^398
> 14^579 - 579^14
> 244^579 - 579^244
> 323^584 - 584^323
> 272^587 - 587^272
> 332^589 - 589^332
> 232^597 - 597^232
> 323^606 - 606^323
> 392^607 - 607^392
> 215^608 - 608^215
> 497^608 - 608^497
> 2^623 - 623^2
> 30^631 - 631^30
> 532^633 - 633^532
> 535^636 - 636^535
> 302^641 - 641^302
> 362^653 - 653^362
> 14^655 - 655^14
> 48^661 - 661^48
> 119^668 - 668^119
> 305^668 - 668^305
> 629^668 - 668^629
> 248^669 - 669^248
> 116^675 - 675^116
> 133^680 - 680^133
> 301^692 - 692^301
> 201^694 - 694^201
> 171^704 - 704^171
> 62^707 - 707^62
> 446^715 - 715^446
> 584^715 - 715^584
> 49^720 - 720^49
> 38^721 - 721^38
> 240^721 - 721^240
> 389^722 - 722^389
> 81^724 - 724^81
> 181^732 - 732^181
> 38^735 - 735^38
> 233^740 - 740^233
> 398^741 - 741^398
> 722^745 - 745^722
> 649^774 - 774^649
> 685^774 - 774^685
> 691^774 - 774^691
> 482^775 - 775^482
> 113^782 - 782^113
> 37^786 - 786^37
> 334^789 - 789^334
> 159^794 - 794^159
> 325^798 - 798^325
> 428^809 - 809^428
> 21^814 - 814^21
> 18^821 - 821^18
> 282^821 - 821^282
> 139^824 - 824^139
> 12^833 - 833^12
> 747^842 - 842^747
> 338^859 - 859^338
> 509^864 - 864^509
> 181^878 - 878^181
> 594^881 - 881^594
> 883^884 - 884^883
> 165^892 - 892^165
> 472^897 - 897^472
> 40^903 - 903^40
> 272^903 - 903^272
> 49^908 - 908^49
> 398^913 - 913^398
> 272^917 - 917^272
> 866^925 - 925^866
> 765^926 - 926^765
> 847^930 - 930^847
> 91^932 - 932^91
> 740^933 - 933^740
> 686^937 - 937^686
> 702^941 - 941^702
> 192^943 - 943^192
> 770^943 - 943^770
> 349^944 - 944^349
> 373^944 - 944^373
> 451^948 - 948^451
> 841^950 - 950^841
> 908^961 - 961^908
> 291^962 - 962^291
> 688^975 - 975^688
> 8^977 - 977^8
> 637^984 - 984^637
> 38^985 - 985^38
> 42^1003 - 1003^42
> 849^1018 - 1018^849
> 789^1030 - 1030^789
> 408^1031 - 1031^408
>
> As anyone can check against Paul Leyland's tables at
> http://www.leyland.vispa.com/numth/primes/xyyx.htm, the form x^y - y^x is
> much more productive than x^y + y^x. For x,y < 1000, there are 254 x^y - y^x
> primes and only 87 x^y + y^x primes. Frankly, this a mistery to a me. I see
> no reason for them to be any different, even taking into account the fact
> that x^y - y^x < x^y + y^x: the ratio x^y/y^x is always huge, even in the
> most favorable case, x + 1 = y (here the ratio seems to be well approximated
> by (x+y)/2e ~ 0.184(x+y)), so that the probability that each form is prime,
> log(x^y + y^x) and log(x^y - y^x) are essentially the same.
>
> Interestingly, 2^9 + 9^2 and 2^9 - 9^2 is a `twin' pair, and the only one
> I've
> found yet. I'm not hoping to find a larger pair, but it would be a very
> welcome surprise.
>
> Décio
>
>
> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
> The Prime Pages : http://www.primepages.org/
>
>
>
>
> ________________________________
>
> To visit your group on the web, go to:
>
> To unsubscribe from this group, send an email to:
>
• Thanks Norman and Nathan to all for verifying it. I downloaded it and will use it. I have to confess, I used it before too but the results did not go anywhere.
Message 16 of 29 , Aug 13, 2009
Thanks Norman and Nathan to all for verifying it.

I downloaded it and will use it. I have to confess, I used it before too but

the results did not go anywhere.

Cino

To: nluhn@...
From: windrunner@...
Date: Thu, 13 Aug 2009 12:43:13 -0400
Subject: Re: [PrimeNumbers] Re: x^y - y^x

It looks from the homepage like it can be used in the US, just you are
at your own risk for patents (and I think the chance of someone going
after me is approximately zero). Marcel also told me years ago that
as a paid user of the early versions, I had his permission to do so

Nathan

On Thu, Aug 13, 2009 at 12:31 PM, Norman Luhn<nluhn@...> wrote:
>
>
> Hello, I think you can use PRIMO.
>
> Look here :
>
> http://www.sourcecodeonline.com/details/primo.html
>
>
>
>
>
>
>
>
>
> best
>
> Norman
>
> [Non-text portions of this message have been removed]
>
>

[Non-text portions of this message have been removed]
• Just in case you re unaware, Primo, like any other non-special-form tool, is going to be much slower than those aimed at special forms this . For example,
Message 17 of 29 , Aug 13, 2009
Just in case you're unaware, Primo, like any other "non-special-form"
tool, is going to be much slower than those aimed at special forms
this . For example, the numbers I'm testing now (around 3 kbit) are
taking about half an hour on my laptop. On the other hand, Mersenne
3,217 takes under a second, and Mersenne 44,497, about the size of any
number that might at all reasonably be ECPP tested in the next decade
or so, takes under a minute.

Sorry if you know this, or if that's not what you mean by "results not
going anywhere".

Nathan

On Thu, Aug 13, 2009 at 12:53 PM, cino hilliard<hillcino368@...> wrote:
>
>
> Thanks Norman and Nathan to all for verifying it.
>
> I downloaded it and will use it. I have to confess, I used it before too but
>
> the results did not go anywhere.
>
> Cino
>
>
> To: nluhn@...
> From: windrunner@...
> Date: Thu, 13 Aug 2009 12:43:13 -0400
> Subject: Re: [PrimeNumbers] Re: x^y - y^x
>
> It looks from the homepage like it can be used in the US, just you are
> at your own risk for patents (and I think the chance of someone going
> after me is approximately zero). Marcel also told me years ago that
> as a paid user of the early versions, I had his permission to do so
> even before the license change.
>
> Nathan
>
> On Thu, Aug 13, 2009 at 12:31 PM, Norman Luhn<nluhn@...> wrote:
>>
>>
>> Hello, I think you can use PRIMO.
>>
>> Look here :
>>
>> http://www.sourcecodeonline.com/details/primo.html
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> best
>>
>> Norman
>>
>> [Non-text portions of this message have been removed]
>>
>>
>
> [Non-text portions of this message have been removed]
>
>
• As a trivial observation, where x is not a power of 10, x^y-y^x has, with high probability, floor(y log x) digits. This is useful as a rule of thumb for how
Message 18 of 29 , Aug 13, 2009
As a trivial observation, where x is not a power of 10, x^y-y^x has,
with high probability, floor(y log x) digits. This is useful as a
rule of thumb for how long proving the numbers will take.

Nathan
• ... The 101^462 - 462^101 passes pari s isprime() test. I don t know if that is foolproof however. What is curious to me is this: if the above is prime, it is
Message 19 of 29 , Aug 14, 2009
--- In primenumbers@yahoogroups.com, Nathan Russell <windrunner@...> wrote:
> 101^462 - 462^101
> 172^471 - 471^172
> 24^481 - 481^24
>
> I am working on the above 3 now. Should probably just go ahead and > do
> the last - it should take under a minute.
>

The 101^462 - 462^101 passes pari's isprime() test. I don't know if that is foolproof however.

What is curious to me is this: if the above is prime, it is the first occurrence when an even multiple of 11 (462) has been noted.

To my knowledge the numbers 22, 44, 66, etc. have not yet appeared to generated primes of the form x^y - y^x.

Maybe numbers with factors of 11 have an almost complete covering set or something. Haven't checked.

But I know why even squares > 4 (16,36,64,100,...) can never generate primes. :)

Mark
• On Fri, Aug 14, 2009 at 3:08 PM, Mark ... It indeed is prime, one of about a dozen of this form I ve tested in the past day (all from the email I quoted).
Message 20 of 29 , Aug 14, 2009
On Fri, Aug 14, 2009 at 3:08 PM, Mark
Underwood<mark.underwood@...> wrote:
>
>
> --- In primenumbers@yahoogroups.com, Nathan Russell <windrunner@...> wrote:
>> 101^462 - 462^101
>> 172^471 - 471^172
>> 24^481 - 481^24
>>
>> I am working on the above 3 now. Should probably just go ahead and > do
>> the last - it should take under a minute.
>>
>
> The 101^462 - 462^101 passes pari's isprime() test. I don't know if that is
> foolproof however.
>
> What is curious to me is this: if the above is prime, it is the first
> occurrence when an even multiple of 11 (462) has been noted.

It indeed is prime, one of about a dozen of this form I've tested in
the past day (all from the email I quoted).

Nathan
• ... As it turns out I was seaching the wrong (and very incomplete) list! Lots of other even numbers with factors of 11 were on it. 44,66,88,110... Sorry about
Message 21 of 29 , Aug 14, 2009
--- In primenumbers@yahoogroups.com, Nathan Russell <windrunner@...> wrote:
>
> On Fri, Aug 14, 2009 at 3:08 PM, Mark
> Underwood<mark.underwood@...> wrote:
> >
> > The 101^462 - 462^101 passes pari's isprime() test. I don't know if that is
> > foolproof however.
> >
> > What is curious to me is this: if the above is prime, it is the first
> > occurrence when an even multiple of 11 (462) has been noted.
>
> It indeed is prime, one of about a dozen of this form I've tested in
> the past day (all from the email I quoted).
>

As it turns out I was seaching the wrong (and very incomplete) list! Lots of other even numbers with factors of 11 were on it. 44,66,88,110...
Mark
• ... http://xyyxf.at.tut.by/primes.html ... Best regards, Andrey [Non-text portions of this message have been removed]
Message 22 of 29 , Aug 15, 2009
> (or for that matter X^Y+Y^X)

http://xyyxf.at.tut.by/primes.html

:-)

Best regards,

Andrey

[Non-text portions of this message have been removed]
• ... Awesome, thank you - somehow my google search missed that site. I may be masochistic, but would it be possible to reserve 1588^721+721^1588? Assuming
Message 23 of 29 , Aug 15, 2009
On Sun, Aug 16, 2009 at 12:50 AM, Andrey Kulsha<Andrey_601@...> wrote:
>
>
>> (or for that matter X^Y+Y^X)
>
> http://xyyxf.at.tut.by/primes.html
>
> :-)
>
> Best regards,
>
> Andrey

Awesome, thank you - somehow my google search missed that site.

I may be masochistic, but would it be possible to reserve
1588^721+721^1588? Assuming Primo is O(log^4.5 n), which is my old
rule of thumb, I should be able to do this in about a month on my
machine.

Thanks,
Nathan
• ... Where n is magnitude - somehow it slipped my mind that s the standard when talking about factoring algorithms, but not so much primality testing. Nathan
Message 24 of 29 , Aug 15, 2009
On Sun, Aug 16, 2009 at 1:32 AM, Nathan Russell<windrunner@...> wrote:

> I may be masochistic, but would it be possible to reserve
> 1588^721+721^1588?  Assuming Primo is O(log^4.5 n), which is my old
> rule of thumb, I should be able to do this in about a month on my
> machine.

Where n is magnitude - somehow it slipped my mind that's the standard
when talking about factoring algorithms, but not so much primality
testing.

Nathan
• ... OK :-) I ll update the pages next week. Thanks a lot, Andrey [Non-text portions of this message have been removed]
Message 25 of 29 , Aug 15, 2009
> I may be masochistic, but would it be possible to reserve
> 1588^721+721^1588? Assuming Primo is O(log^4.5 n), which is my old
> rule of thumb, I should be able to do this in about a month on my
> machine.

OK :-)

I'll update the pages next week.

Thanks a lot,

Andrey

[Non-text portions of this message have been removed]
• ... And done.  Andrey or anyone else want a copy of the certificate? Nathan
Message 26 of 29 , Sep 29, 2009
On Sun, Aug 16, 2009 at 1:52 AM, Andrey Kulsha <Andrey_601@...> wrote:
>
>
> > I may be masochistic, but would it be possible to reserve
> > 1588^721+721^1588? Assuming Primo is O(log^4.5 n), which is my old
> > rule of thumb, I should be able to do this in about a month on my
> > machine.
>
> OK :-)
>
> I'll update the pages next week.
>
> Thanks a lot,
>
> Andrey
>

And done.  Andrey or anyone else want a copy of the certificate?

Nathan
• Hi all I don t remember how to open Pari (.tar.-file) can somebody help? gr. Rob Binnekamp ... From: Nathan Russell To: Andrey Kulsha Cc:
Message 27 of 29 , Sep 30, 2009
Hi all

I don"t remember how to open Pari (.tar.-file)
can somebody help?
gr. Rob Binnekamp

----- Original Message -----
From: Nathan Russell
To: Andrey Kulsha
Sent: Wednesday, September 30, 2009 7:15 AM
Subject: Re: [PrimeNumbers] Re: x^y - y^x

On Sun, Aug 16, 2009 at 1:52 AM, Andrey Kulsha <Andrey_601@...> wrote:
>
>
> > I may be masochistic, but would it be possible to reserve
> > 1588^721+721^1588? Assuming Primo is O(log^4.5 n), which is my old
> > rule of thumb, I should be able to do this in about a month on my
> > machine.
>
> OK :-)
>
> I'll update the pages next week.
>
> Thanks a lot,
>
> Andrey
>

And done. Andrey or anyone else want a copy of the certificate?

Nathan

[Non-text portions of this message have been removed]
• ... on linux you decompress and extract using (replace PARI with the actual file name): tar xvfz PARI.tar.gz (or pari.tgz) (omit the v if you don t want to
Message 28 of 29 , Sep 30, 2009
--- In primenumbers@yahoogroups.com, "Robdine" <robdine@...> wrote:
>
> Hi all
>
> I don"t remember how to open Pari (.tar.-file)
> can somebody help?
> gr. Rob Binnekamp

on linux you decompress and extract using
(replace PARI with the actual file name):

tar xvfz PARI.tar.gz (or pari.tgz)

(omit the "v" if you don't want to see the list of files) or

tar xvfj PARI.tar.bz2

If it's already decompressed, use simply

tar xvf PARI.tar

(That said you should be able to click on the file if you see it in some file manager window.)
On Windows, WinRAR and WinZIP should be able to open these,
on recent versions of the Win "OS" it works "automagically" I think.

Maximilian
• ... The form x^y-y^x was recently completely factorized for 0
Message 29 of 29 , Mar 13, 2012