Re: More x^y y^x fun. Message #14 Posted by Egan Ford on 18 Jan 2009, 10:07 p.m., in response to message #1 by Egan Ford
Quote:
How many integer values of x and y can you find that satisfy xy + yx = p, where p is prime and x > 1 and y > 1, can you find with your favorite calculator? I'll give you the first pair: 2 and 3.
As explained above each pair must have opposite parity (odd/even) and be co-prime. This can reduce the number of tests by more than half.
All the programs below use the same basic algorithm:
Loop from 3 to n (largest base)
Loop from 2 or 3 depending on if outer loop is odd/even and skip every other number (i.e. opposite parity), end at outer loop - 1
If GCD = 1 (i.e. co-prime) then check for prime and print if prime
50g version. The 49g+/50g are the only calculators that I have with multiple precision integers.
%%HP: T(3)A(R)F(.);
\<< \-> n
\<<
3 n FOR i
3 i 2 MOD - i 1 - FOR j
i j GCD 1 == IF THEN
i j ^ j i ^ + DUP ISPRIME? IF THEN
i j ROT 3 \->LIST
ELSE
DROP
END
END
2 STEP
NEXT
\>>
\>>
Using 100 for n and timing it I got the following output:
17: { 3 2 17 }
16: { 9 2 593 }
15: { 15 2 32993 }
14: { 21 2 2097593 }
13: { 24 5 59604644783353249 }
12: { 32 15 43143988327398957279342419750374600193 }
11: { 33 2 8589935681 }
10: { 38 33 5052785737795758503064406447721934417290878968063369478337 }
9: { 54 7 4318114567396436564035293097707729426477458833 }
8: { 56 3 523347633027360537213687137 }
7: { 68 21 814539297859635326656252304265822609649892589675472598580095801187688932052096060144958129 }
6: { 69 8 205688069665150755269371147819668813122841983204711281293004769 }
5: { 75 34 7259701736680389461922586102342375953169154793471358981661239413987142371528493467259545421437269088935158394128249 }
4: { 76 9 3329896365316142756322307042065269797678257903507506764421250291562312417 }
3: { 81 80 14612087592038378751152858509524512533536096028044190178822935218486730194880516808459166772134240378240755073828170296740373082348622309614668344831750401 }
2: { 87 56 123696767198741648186287940563721003128015158572134981161748692560225922426827257262789498753729852662122870454448694253249972402126255218031127222474177 }
1: 23276.5845947
That last value is the number of seconds. Most of the time was spend checking for primarlity (checking the last number took over 1500 seconds).
My 2nd program was for the 42S. Without an MP library only 5 possible solutions can be found.
01 LBL "XYYX" 19 RCL "X" 37 GTO 03 55 GTO 01
02 FIX 00 20 IP 38 Rv 56 LBL 03
03 1E3 21 2 39 XEQ "?PRI" 57 ISG "X"
04 / 22 MOD 40 1 58 GTO 00
05 3 23 - 41 X!=Y? 59 LBL 04
06 + 24 STO+ "Y" 42 GTO 02 60 RCL "X"
07 STO "X" 25 LBL 01 43 "(" 61 IP
08 LBL 00 26 RCL "X" 44 RCL "X" 62 ENTER
09 RCL "X" 27 IP 45 AIP 63 ENTER
10 1 28 RCL "Y" 46 |-"," 64 RCL "Y"
11 - 29 IP 47 RCL "Y" 65 IP
12 IP 30 XEQ "GCF" 48 AIP 66 Y^X
13 1E3 31 1 49 |-") = " 67 X<>Y
14 / 32 X!=Y? 50 XEQ 04 68 LASTX
15 2E-5 33 GTO 02 51 AIP 69 X<>Y
16 + 34 XEQ 04 52 PRA 70 Y^X
17 STO "Y" 35 1E12 53 LBL 02 71 +
18 3 36 X<=Y? 54 ISG "Y" 72 RTN
You'll need to provide your own GCF and ?PRI for computing and checking for GCD and primality. Versions that I used can be found here:
http://www.hpmuseum.org/software/42snumth.htm and here: http://www.hp42s.com/programs/prm/prm.html. Unfortunately, both primality testing programs failed to find 332 + 233 = 8589935681, which is prime. Both return 8589935681 as composite.
Since bases larger than 40 would exceed the largest integers on the 42S, an n of 40 was used with the following output sent to the printer:
(3,2) = 17
(9,2) = 593
(15,2) = 32993
(21,2) = 2097593
I did not have the time or desire to input this into my 42S and time it. All testing was done with Free42 and EMU42. Both run in about a second. EMU42 with Authentic Calculator Speed checked ran in about 5 minutes. Not bad at all. Again 332 + 233 = 8589935681, which is prime, was not identified.
Lastly, I wrote a 50g C program. Output (n = 250):
xyyx
----
max base = 250
1:(3,2) st:0 tt:0 p=17
2:(9,2) st:0 tt:0 p=593
3:(15,2) st:0 tt:0 p=32993
4:(21,2) st:0 tt:0 p=2097593
5:(24,5) st:0 tt:0 p=59604644783353249
6:(32,15) st:0 tt:0 p=43143988327398957279342419750374600193
7:(33,2) st:0 tt:0 p=8589935681
8:(38,33) st:0 tt:0 p=5052785737795758503064406447721934417290878968063369478337
9:(54,7) st:1 tt:1 p=4318114567396436564035293097707729426477458833
10:(56,3) st:0 tt:1 p=523347633027360537213687137
11:(68,21) st:1 tt:2 p=814539297859635326656252304265822609649892589675472598580095801187688932052096060144958129
12:(69,8) st:0 tt:2 p=205688069665150755269371147819668813122841983204711281293004769
13:(75,34) st:0 tt:2 p=7259701736680389461922586102342375953169154793471358981661239413987142371528493467259545421437269088935158394128249
14:(76,9) st:1 tt:3 p=3329896365316142756322307042065269797678257903507506764421250291562312417
15:(81,80) st:3 tt:6 p=14612087592038378751152858509524512533536096028044190178822935218486730194880516808459166772134240378240755073828170296740373082348622309614668344831750401
16:(87,56) st:1 tt:7 p=123696767198741648186287940563721003128015158572134981161748692560225922426827257262789498753729852662122870454448694253249972402126255218031127222474177
17:(114,67) st:17 tt:24 p=14877416035581437625382418693025659213718389161995860818124841388673684963203665153674781821433446993366770573625979847557897428218464508224911011186563057321746523584348117445155146293741592207500868288335433
18:(114,97) st:2 tt:26 p=31044002257937938068829512069328418720442849714746044259262070211475909156430718104897916371346903019988299736264997845256331029880527467485588680290321008690638402969435837489232709464321634204160348150282351066675254883643073
19:(122,9) st:14 tt:40 p=261568927457882874608733211757582315090892217214195250256575658313972901281170319830426649720495055337775965208077073
20:(135,32) st:34 tt:74 p=156764265941034957982331212844852467344711417043899710759469297619722251722129607859661177881884230709880082871203965476543290384119266534864181746784056675684904885421941056286488906715343079485633768193
21:(144,65) st:38 tt:112 p=1146894200299040723795729560557432803945230313807638769578093982012136321215160297940927699948343520671556845736219442653998944625369329903193883106139926361443140667237807076206116279779808347609272466625004356934372143216248343316093884886514556058622237058049
22:(158,45) st:44 tt:156 p=1612787603050274562069903478238630968344365069682295284380830826698222889674680197987083262414275400043686513974598153012882088977642138200701969570555398418510708201351413523014544364196803446185300014434337842494330504602516368646842185185091035058849770379993
23:(160,133) st:33 tt:189 p=6550320570424736017975912906823227230795756706291794704108177489835078496769415238689514208202469044620324030607457783482205821651727093725227403397073694702896425225342185751848441751740036285422160020451093004818459243817193874978308895037403004230124437546048120534386189574836751659857634392400828235697956677388632599317401261314620801
24:(171,98) st:59 tt:248 p=31597952610481735406184417800290574875942553425307879180826388419529262723040048711068602071994548107999174044084577517699846942953913418228435183384942999925853097569116224722566930758007858250860318446140839471731747637849343767087120159917109898890189838206328093476501956660894289333508728745376522299995609109005181880977444726036361913
25:(185,36) st:78 tt:326 p=824067225624450724350185185776877304119442769678571343023989650001883754551070680307504347916864451372704776163119070934582841099887572070617259829434205627038583354453077452767660757445997902514308790481190497037477812241451095936591256345061049919894048836391873825201358795351447541601
26:(206,51) st:299 tt:625 p=5747199543760759616874233229888257422940157808956554894989528303876688063774886847508851734925031076478824589152166195877212975767050907832290325148805207959265061065974594521872318497656340905582188769534415194253694453761740437565393308530950568782990088412137769599069158309021988800952585164712968388821327706584784875619399795456912191697392743257
27:(214,157) st:229 tt:854 p=83661493955934721940093572212231383493946119658337358148614804736256324921471160972435870342060927623728152367517269822843884194359726682507710240594072584001564534040253478907766066569333018912502014344554426181798194999272481888123729683855997762382503244058294295978132489987218780748626118191917375910685828051555739477358215225955442752598788025402065384853015539995876967147994467068334686232696554600733521322102525300704289117626991526368429784833137841843604953
28:(215,76) st:39 tt:893 p=237094969949224442749902986380791020043168977628753310230413588887866019807206687260728586774883158972331245704593379062623514507537767351876807280227464301767774824002902112830817761681285007322413139576110910042445342936924413085089951612853750811126254043830282762406659735949091917233649175898134000967364940467954696619147066269814574920691123415395618086403122820151726350048959757440141854187388001
29:(235,214) st:493 tt:1386 p=44385052412762688318951055173380319843487748708306634619440889745835408830738494165959460186649795039935869857701360175697514476212887207864294549983864003450722679260729153842868970919466290674158790879651861662496290527238948143838921484616959315821844518426079457762372930928602345374576342716989247843757891309322658042817360942693414966600088738885411412998933675452974393371268704164198882524739941965846960794214860883824710910263573766169516089092742362941226839480712862783430499156602698187227452508958045052406028997664027096899107636649
30:(237,200) st:66 tt:1452 p=220855883097298041197912187592864814478435487109452369765200775161577480905723392388044682757315234654167670063250350243744077256350845446337761180825366337002635606656007341132320168032281392575017521703513771018927360713671517013624864566435547143474670149962861625252760480437528208244008235645089927121069906768913003579993568524493534133751800322779056517412042477855290593538630256881723755480024801815845773154160553997782832989236043893126868182761752694180134718301605006478125705120066279786312075737518812303625846500724858615981588001
31:(248,87) st:308 tt:1760 p=10017852879331048206259365643153524162288395290235824439008838292948861954561026577732490631710064187459350801885314214526661356445274819838307275428757174304254585208499586166194622979711174028594438075409019427281714941478505682983882454321763489168841963884963368611530325032984768592374068808877912054221465743402174420737098853301865336967778491146415153029254969741768852576657071243601202773439328674914074447937954978745826356707638975566131088882293333821065981432759008193
Total time: 1902
The first 16 values also identivied by my 50g UserRPL program took 7 seconds with C @ 192MHz, vs. 23277 seconds with UserRPL @ 75MHz.
Universal HPGCC2, HPGCC3, and HPAPINE code. Put a real (not an integer on the stack--HPAPINE limitation). Press any key to interrupt and get intermediate results.
#include <hpgcc49.h>
#include <tommath.h>
#define OUTPUT printf("%s",buf); fprintf(fp,"%s",buf)
int gcd(int, int);
int main()
{
mp_int a, b;
mp_err ret;
int n, x, y, c=0, start, split, end, t;
FILE *fp;
char *filename="xyyx.txt", buf[5000];
if((fp = fopen(filename,"w")) == NULL) {
char errormsg[30];
sprintf(errormsg,"Cannot open: %s",filename);
#ifdef HPGCC2
sat_stack_push_string(errormsg);
sat_push_real(1);
#else
sat3_push_string(errormsg);
sat3_push_int_real(1);
#endif
return(0);
}
#ifdef HPGCC2
n = sat_pop_real();
sys_slowOff();
#else
n = sat3_pop_dbl(100);
cpu_setspeed(192*1000000);
#endif
clear_screen();
mp_init(&a);
mp_init(&b);
sprintf(buf,"xyyx\n----\nmax base = %d\n\n",n); OUTPUT;
start = split = sys_RTC_seconds();
for (x = 3; x <= n; x++) {
for (y = 3 - x % 2; y < x; y+=2) {
if(gcd(x,y) == 1) {
mp_set_int(&a, x);
mp_expt_d(&a, y, &a);
mp_set_int(&b, y);
mp_expt_d(&b, x, &b);
mp_add(&a, &b, &a);
mp_prime_is_prime(&a, 1, &ret);
if (ret) {
end = sys_RTC_seconds();
t = (end - split >= 0) ? end - split : end - split + 86400;
sprintf(buf,"%d:(%d,%d) st:%d ",++c,x,y,t); OUTPUT;
t = (end - start >= 0) ? end - start : end - start + 86400;
sprintf(buf,"tt:%d",t); OUTPUT;
fprintf(fp," p=");
mp_toradix(&a, buf, 10);
fprintf(fp,"%s",buf);
sprintf(buf,"\n"); OUTPUT;
split = end;
}
}
#ifndef HPAPINE
if(keyb_isAnyKeyPressed())
break;
#endif
}
#ifndef HPAPINE
if(keyb_isAnyKeyPressed())
break;
#endif
}
end = sys_RTC_seconds();
t = (end - start >= 0) ? end - start : end - start + 86400;
sprintf(buf,"\nTotal time: %d\n",t); OUTPUT;
fclose(fp);
#ifdef HPGCC2
WAIT_CANCEL;
#else
SLOW_WAIT_CANCEL;
#endif
return (0);
}
int gcd(int x, int y)
{
int t;
while (y) {
t = x;
x = y;
y = t % y;
}
return(x);
}
References:
http://www.leyland.vispa.com/numth/primes/xyyx.htm#results
|