Determine all possible value(s) of a 4-digit non leading zero base ten positive integer x such that the remainder obtained upon dividing 2^x by 10,000 is equal to x.

What are the possible value(s) of a 4-digit non leading zero base ten positive integer x such that the remainder obtained upon dividing 3^x by 10,000 is equal to x?

As the higher numbers will exceed even the precision of UBASIC, we might as well use QuickBasic, and keep all the numbers under its 15-decimal-digit accuracy. Every result is done mod 10000 and raising to a power is done by repeated multiplication mod 10000. Each of the four digits is done separately, so we don't have to do thousands of multiplications per value of x.

DEFDBL A-Z
DIM pow(4, 9)

FOR dig = 0 TO 9
 pow(4, dig) = INT(2 ^ dig + .5)
 FOR p = 3 TO 1 STEP -1
   pw = pow(p + 1, dig)
   FOR i = 2 TO 10
    pw = pw * pow(p + 1, dig) MOD 10000
   NEXT
   pow(p, dig) = pw
 NEXT
NEXT

CLS
'to verify correctness:
FOR p = 1 TO 4
  FOR d = 0 TO 9
    PRINT pow(p, d);
  NEXT
  PRINT
NEXT
PRINT

FOR x = 1000 TO 9999
 d(1) = x \ 1000
 d(2) = (x \ 100) MOD 10
 d(3) = (x \ 10) MOD 10
 d(4) = x MOD 10
 p = pow(1, d(1))
 FOR i = 2 TO 4
  p = p * pow(i, d(i)) MOD 10000
 NEXT
 IF p = x THEN PRINT p;
NEXT

PRINT : PRINT : PRINT

FOR dig = 0 TO 9
 pow(4, dig) = INT(3 ^ dig + .5)
 FOR p = 3 TO 1 STEP -1
   pw = pow(p + 1, dig)
   FOR i = 2 TO 10
    pw = pw * pow(p + 1, dig) MOD 10000
   NEXT
   pow(p, dig) = pw
 NEXT
NEXT

'to verify correctness:
FOR p = 1 TO 4
  FOR d = 0 TO 9
    PRINT pow(p, d);
  NEXT
  PRINT
NEXT
PRINT

FOR x = 1000 TO 9999
 d(1) = x \ 1000
 d(2) = (x \ 100) MOD 10
 d(3) = (x \ 10) MOD 10
 d(4) = x MOD 10
 p = pow(1, d(1))
 FOR i = 2 TO 4
  p = p * pow(i, d(i)) MOD 10000
 NEXT
 IF p = x THEN PRINT p;
NEXT

The results: for part 1, 8736; for part 2, 5387.

Since 3^5387 does happen to lie within the limitations of UBASIC, we might as well show:

OK
?3^5387
 1787307076283774669615933898534101430088393099093207251951860033118245616820561
54766605835769070613271148774495950816192365099136525850102700385030057181270028
89379615491141011054823933157926607463321112841809846960883058504760966227770719
91747008347991278652975354178084112689604689073944444574783726295320182106368481
04205871765759563243207781345472760180171699759974494686743978307541995717186297
10922732102376447882822999960634198678730490905548591005676126363128239672390525
50771272256300831601890874860288020488786478353761828907126180361096421969295704
44072197011266299928648866000312853559290449765896297984825318107198301815224657
95402671290429498381664804022842638722587145068838648160588728695304738730700390
84359079553273554711864780687842624153502157286028451269847638789385070450112043
54783098927707946909949794767361550890457744058213145101310094518519203430928436
73669480707954805020266117941249623452877246881648523212630374989810520892739746
25159699346792975716569229130638603696565616010123415726312189468255984906639328
80413474763523318399903496994161186367161414413282376145458167352697365839239468
31021377751270575729762294653383583957478455613329586297224279800466129632620636
08896841537621187524996413210690267488489972086258776559966026258992111709983540
38083353915606614051329024830739481971550026441149963623678607898650076028596627
30323731705189138459706379502683912562398716931253469524842883739006808270689553
91766996852598714797727252561195816929606395113535045437372978409869294460786527
87523051627537817484894943068933638540159349283366360858180154041948793778536950
88776052891809066148141587318845223791786901510330095660997533738017945303654928
93501521675327195105321417543417615046601039458092440684129280046221460246442731
71010324711231759179658209773281132628396919116518063604845524465896051027493974
25152913969539538838100473723623990330645451146553393426650146673450422884819136
41515795985198839942232888092210900540742460405650038796208053110967705780732379
26810818328890540050060885944801261117562764756129176502483404987272530776375598
66891794341864694780195438034005459352887368731440256796264890426049342395541363
67869998496427914785243737978535885794410724670448285388130970121205162123078496
67162669474012486691881194740539168758709232070727491222196834285130649411758366
22496688122876809640391101113634760207829584568114118558162093638396396174910754
56021370190095801544331900388620284150316930247199458265787290407958123886986653
26755311555285983535054307690978563383699281124889080726848810246967137648519242
758177595387

a 2571-digit number.

Since we know the answer for part 1, we can use MIRACLE CALC (MIRCALC.EXE), to evaluate 2^8736 (having set that program to allow for up to 4000-digit numbers):

62811927471493932814210000114959054894611221066450619168954188412932703712485870
58575782742413165203233877994609924661288797952800643340601772131129364077079719
81775612404905170935708518283336613810556843698068432864542858446266447056224827
15987485505068734293854037136804003376122678522425845032480626410500459893264493
97571055328300323934615379865596197566124697905756602529945585942405324695619071
13293466856509564415848643577781574084983877974321381832187473487691774164622755
01086428897215001986546044067824401937493861551092584238195040569053592069102288
31950497450934558057821943480922771447589384939014565626671620620879444279638294
31124427017852080942188601793671624074631864927334875171330489382310665528479222
78445093731488624425751606689018350062245932943947060210484587172816829054402470
96171978646926882537385018042819137465576091277929763668577899073100516336423935
84428087961750354475355196997123754931659927847542637806325780675198396976426681
46778126401954844669516505470461007917109504864269643049955897493010186639202609
01773979473437911144231665016897421353153770671765003769691270058297227166121749
93587133531270686366060696479936639936423573473676009390902634736554694889385588
43301768489932892183664410635216015321725394290112957006656395513827009760818202
90478705494272625965366626263406410514746068810117964392897595159535817567353834
88722071598639461200620862904727955089128804521422397391347116260299187247079426
95350221104643277499221381546470698719700054261287218027202207285566322171669023
52293761572873663389025523654255304623458155061140474153879085170416357864958219
69206761268604558468173558040982935168788115151666045335989107527891958587661589
11122797848085782446018548510062166200923394287279319483561692482880374721987789
71149171277683051364805274058159080370487366860426468963256368055481184407170280
11330583855305261855880360181745563509666111007878123093606646940350797882117648
20339375934758341692864079782497440199061932992945688803871544356573429402754275
68810895941612154871110867099711398181163128444401737047542591972227377922617014
03961074616857163226584870934593417384545626532738959562204112633409496204500818
14388518394171754946632748202693113886869346549543648579299079017936978295893566
30825571040489917285888958589206040418565487724151294230986925970523150826249605
52688340957276139005677372545533615174692390836382713351396381777862614396366376
61204202368276753149110771557031895272988337117600118554575396505157493410332445
63678156400311469137895082649496798000082697137410695158408442140519911331866099
9260677697215248546922097439257011449253564577649776629419592946548736

a 2630-digit number.

Posted by Charlie on 2009-08-20 11:40:14