Maximum remainder

Question

I got this programming challenge - and can solve it by brute force. But I would love to solve it using a more mathematical approach.

/* Square Remainder Challenge
     * 
     * Here's a challenge for the math lovers. Solving this challenge can be done in 4 lines of code (inside of the method) but getting to the right solution can be tricky!
     * 
     * Here we go:
     * 
     * Let r be the remainder when (a−1)^n + (a+1)^n is divided by a^2.
     * 
     * I.e.,    r = ((a−1)^n + (a+1)^n) % a^2
     * 
     * Example: If a = 7 and n = 3,
     *          then r = 42.
     *          Because:   ((7-1)^3 + (7+1)^3) % 7^2
     *                   = (6^3 + 8^3) % 49
     *                   = (216 + 512) % 49
     *                   = 728 % 49
     *                   = 42
     *          
     *          And as n varies, r will too, but for a = 7 it turns out that r_max = 42.
     *          
     * You will receive two inputs to your method: a lower limit (integer) and an upper limit (integer).
     * 
     * You need to make the Execute method return the SUM of r_max for:
     *          
     *          lowerLimit <= a <= upperLimit
     *          
     * You will have to iterate over all possible values of a from the lower limit to the upper limit (including both limits).
     * Then, you need to add the r_max of each iteration to a sum, which your method shall return (integer).
     * 
     * Good luck!
     */

score 0 · Answer 1 · answered Nov 29 '14 at 10:04

It is easy to check that when $a=1$, the maximum is $0$ and when $a=2$ the maximum is $2$. So we assumet hat $a>2$.

Apply the binomial theorem:

$$(a-1)^n+(a+1)^n\equiv (-1)^n(1-na)+1+na\pmod{a^2}$$

This is $2$ if $n$ is even and $2an$ if $n$ is odd. If $a>2$, the maximum is $a^2-a$ when $a$ is odd and $a^2-2a$ when $a$ is even.

Maximum remainder

1 Answers1