1
$\begingroup$

Update: I provided an answer but I tried something out with Python and I am kind of surprised. Computer technology today is more advanced than I can wrap my head around.

Instead of taking any residues at all I set my python program to directly add up all the terms in $L$,

$$ \Biggl [\sum_{n=0}^{498}\, \left(2001+2002\, n \right) {(10^{6})}^{n}\Biggl] + 999 \,{(10^{6})}^{499}$$

and then print out $L$. I expected the program to have serious problems number crunching, but it ran in a flash, printing

999998997996995994993992991990989988987986985984983982981980979978977976975974973972971970969968967966965964963962961960959958957956955954953952951950949948947946945944943942941940939938937936935934933932931930929928927926925924923922921920919918917916915914913912911910909908907906905904903902901900899898897896895894893892891890889888887886885884883882881880879878877876875874873872871870869868867866865864863862861860859858857856855854853852851850849848847846845844843842841840839838837836835834833832831830829828827826825824823822821820819818817816815814813812811810809808807806805804803802801800799798797796795794793792791790789788787786785784783782781780779778777776775774773772771770769768767766765764763762761760759758757756755754753752751750749748747746745744743742741740739738737736735734733732731730729728727726725724723722721720719718717716715714713712711710709708707706705704703702701700699698697696695694693692691690689688687686685684683682681680679678677676675674673672671670669668667666665664663662661660659658657656655654653652651650649648647646645644643642641640639638637636635634633632631630629628627626625624623622621620619618617616615614613612611610609608607606605604603602601600599598597596595594593592591590589588587586585584583582581580579578577576575574573572571570569568567566565564563562561560559558557556555554553552551550549548547546545544543542541540539538537536535534533532531530529528527526525524523522521520519518517516515514513512511510509508507506505504503502501500499498497496495494493492491490489488487486485484483482481480479478477476475474473472471470469468467466465464463462461460459458457456455454453452451450449448447446445444443442441440439438437436435434433432431430429428427426425424423422421420419418417416415414413412411410409408407406405404403402401400399398397396395394393392391390389388387386385384383382381380379378377376375374373372371370369368367366365364363362361360359358357356355354353352351350349348347346345344343342341340339338337336335334333332331330329328327326325324323322321320319318317316315314313312311310309308307306305304303302301300299298297296295294293292291290289288287286285284283282281280279278277276275274273272271270269268267266265264263262261260259258257256255254253252251250249248247246245244243242241240239238237236235234233232231230229228227226225224223222221220219218217216215214213212211210209208207206205204203202201200199198197196195194193192191190189188187186185184183182181180179178177176175174173172171170169168167166165164163162161160159158157156155154153152151150149148147146145144143142141140139138137136135134133132131130129128127126125124123122121120119118117116115114113112111110109108107106105104103102101100099098097096095094093092091090089088087086085084083082081080079078077076075074073072071070069068067066065064063062061060059058057056055054053052051050049048047046045044043042041040039038037036035034033032031030029028027026025024023022021020019018017016015014013012011010009008007006005004003002001

(use the slider bar)

That was amazing - you can find the remainder by directly dividing $L$ itself and not worrying about inserting any extra residue steps!

I will be going to summer school now to catch up with current technology.


For any $n \ge 1$ with there is a corresponding remainder $r$ obtained by dividing $L$ by $n$.

Now consider only $n$ satisfying

$\tag 1 n \lt 1000000$ $\tag 2 n \notin \{200000, 250000, 333333, 500000, 999999\}$

Calculate an explicit solution $(n,r)$ with $n$ as large as possible.

My Work

I became intrigued examining $L$ after seeing this question and giving an answer.

I think I know the best possible answer $(n,r)$ but it would be interesting to see what mathematics this question sparks; a computer program can be used if necessary for 'mop-up' operations.

$\endgroup$
  • $\begingroup$ In the title, do you mean find $r \equiv L\pmod{n}$ for $n$ as large as possible? $\endgroup$ – user326210 Jun 23 at 22:20
  • $\begingroup$ @user326210 Yes - from the intent of the question, makes more sense, even though $\equiv$ is symmetric. Changed!. $\endgroup$ – CopyPasteIt Jun 23 at 22:36
  • 1
    $\begingroup$ If you think you know the best answer, but you're not going to tell us what it is, then you are inviting us to waste our time telling you something you already know. $\endgroup$ – Gerry Myerson Jun 23 at 22:57
  • 1
    $\begingroup$ What does "n as large as possible" mean? I would take it to mean $n =999998$. But if that were the case why didn't the question just ask the remainder of $L \mod 999998$? $\endgroup$ – fleablood Jun 24 at 0:08
  • 1
    $\begingroup$ Oh, I thought the challenge was to find a result without using computers to do any of the calculation. 3000-digit numbers are indeed trivial to manipulate with a bignum library (which Python uses spontaneously when results get big enough to need it). $\endgroup$ – Henning Makholm Jun 25 at 9:52
1
$\begingroup$

The largest $n$ that satisfies the conditions is $n=999998$, and it shouldn't be too difficult to do that. We're looking for $$ L = 1 + 1000 \sum_{n=0}^{498} (3002+2002n)1000000^n $$ which modulo 999998 is the same as $$ L = 1 + 1000 \sum_{n=0}^{498} ( 3002+2002n) 2^n $$ To calculate this sum, first set $$ X = \sum_{n=0}^{498} 2^n \qquad\qquad Y = \sum_{n=0}^{498}n2^n $$ By standard formulas we get $$ X = \frac{2^{499}-1}{2-1} = 2^{499}-1 $$ and we can find $Y$ by a routine shifting trick: $$ 2Y+2X = Y - 0\cdot 2^0 + 499\cdot 2^{499} $$ or in other words $$ Y = 499\cdot 2^{499} - 2X = 497\cdot 2^{499} + 2 $$ Then $$ L = 1 + 1000(3002X + 2002Y) = 4004001 + 1000\cdot 2^{499}(3002\cdot 499 + 2002\cdot 497) $$ The only real task that remains is to compute $2^{499}$ modulo $999998$. Even with pencil and paper it shouldn't take more than one sheet to compute this by $$ a = 2^{15} = 32768 \\ b = 2^{30} = a^2 \\ c = 2^{31} = 2b \\ d = 2^{62} = c^2 \\ e = 2^{124} = d^2 \\ f = 2^{248} = e^2 \\ g = 2^{249} = 2f \\ h = 2^{498} = g^2 \\ i = 2^{499} = 2h $$ so just eight six-digit squarings or doublings with subsequent reductions modulo $999998$ (which is easy because $1000000\equiv 2$; one doesn't even need to do long division), and then three or four similar arithmetic operations to compute $L$.

I will leave the actual arithmetic to any reader who finds it worth his time.

$\endgroup$
  • $\begingroup$ A more principled way to reach $2^{499}$ would be to use the Chinese Remainder Theorem, but the only factorization of $999998$ I can find in my head is $2\cdot 499999$, and it's actually easier to reduce modulo $999998$ than $499999$, so that is barely a saving. $\endgroup$ – Henning Makholm Jun 23 at 23:44
  • $\begingroup$ Somehow I thought that powers of $2$ would throw everything into the "I need a quantum computer" - impossible!!! How many atoms in the universe? I didn't check all your steps but accepting your answer and will study later. I never studied the Chinese Remainder Theorem, so I have some work to do! $\endgroup$ – CopyPasteIt Jun 23 at 23:48
0
$\begingroup$

Thanks to Henning Makholm and fleablood for helping me see the true power of modular arithmetic - and exponents be damned!

The key idea is you don't want to apply $\text{mod}(n)\text{-Residue}$ to get the remainder of an already big number like $10^{100}$. Instead you use recursion, defining $p_0 = 1$ and for $k \ge 0$,

$$ p_{k+1} = [10^6 \times p_k]\; \text{mod}(n)\text{-Residue}$$

and you can then fold-in $\;p_{100}$ for $10^{100}$ in the remainder calculation.

Here is a python program to calculate remainders for that, now not so scary, large number $L$.

CODE

M = 1000000

def bP(i):
    p = 1
    for j in range(0, i):
        p = (p * M) % n
    return p

def getTerm(i):
    return ((2001 + 2002 * i) * bP(i)) % n

while True:
    print()
    n = int(input('Please input divisor: '))
    if n == 0:
        raise SystemExit
    r = 0
    for i in range(0, 499):
        r = (r + getTerm(i)) % n
    r = (r + 999 * bP(499)) % n
    print('Divisor =', n, 'Remainder =', r)

OUTPUT

Please input divisor: 13
Divisor = 13 Remainder = 6

Please input divisor: 999998
Divisor = 999998 Remainder = 487763

Please input divisor: 59470
Divisor = 59470 Remainder = 42391
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.