Find the value of n without using a calculator

Strategy:

Directly solve the equation modulo small primes and then use the Chinese Remainder Theorem / extended Euclidean algorithm to reconstruct the full solution.

The small primes we are going to use are 7,13 and 37.

Why those?

1. The residue class of the very large number given can be computed with relative ease because 7 and 13 are divisors of 1001, whereas 37 divides 999. Therefore the residue classes are the same as those of the alternating or straight digit sums in base 1000.

2. By Euler's totient theorem (or Fermat's little) modulo each of $7,13,37$ the 38th power is equal to the square. Obviously, this makes calculations much easier, we even have a closed formula for the sum $\sum_1^n i^2 = \frac {n(n+1)(2n+1)} 6$.

Let's carry out our plan:

To calculate the alternating and straight digit sums in base 1000 it is economical to first calculate the digit sum in base 1000000:

$23+103964+552947+537663+511830+783699+848235+835114+091576+114282+100411+910644+864693+207138+533340+427131+745931+484436+237548+793821+338133+952725=10975284$

$10+975284=975294$

From this we get the alternating and straight digit sums in base 1000:

$-975+294=-681 \equiv 320 \mod 1001$

$975+294=1269 \qquad 1+269=270$

Therefore:

$$ \begin{align} \sum_1^n i^2 \equiv 320 &\equiv 5 \mod 7 \\ \sum_1^n i^2 \equiv 320 &\equiv 8 \mod 13 \\ \sum_1^n i^2 \equiv 270 &\equiv 11 \mod 37 \end{align} $$

These three modular equations can be solved by brute force:

The partial sums $s_{n}\equiv \sum_1^n i^2 \mod m$ for $n=1,2,...$ are

$$ \begin{align} s_{1}&=1 & s_{2}&=5 & s_{3}&=0 \\ \end{align} $$ for modulus 7 (the remaining values can be filled in using $s_n \equiv -s_{m-1-n} \mod m$) $$ \begin{align} s_{1}&=1 & s_{2}&=5 & s_{3}&=1 & s_{4}&=4 & s_{5}&=3 & s_{6}&=0 \end{align}$$ for modulus 13 and $$ \begin{align} s_{1}&=1 & s_{2}&=5 & s_{3}&=14 & s_{4}&=30 & s_{5}&=18 & s_{6}&=17 \\ s_{7}&=29 & s_{8}&=19 & s_{9}&=26 & s_{10}&=15 & s_{11}&=25 & s_{12}&=21 \\ s_{13}&=5 & s_{14}&=16 & s_{15}&=19 & s_{16}&=16 & s_{17}&=9 & s_{18}&=0 \end{align}$$ for modulus 37.

Therefore $$ \begin{align} \sum_1^n i^2 \equiv 5 \mod 7 &\Rightarrow n \equiv 2 \mod 7 \\ \sum_1^n i^2 \equiv 8 \mod 13 &\Rightarrow n \equiv 10 \mod 13 \\ \sum_1^n i^2 \equiv 11 \mod 37 &\Rightarrow n \equiv 27 \equiv -10 \mod 37 \end{align} $$

To finish we must combine the moduli. Using the extended Euclidean algorithm we find modular inverses:

$$ \begin{align} 13^{-1} &\equiv 6 \equiv -1 \mod 7 \\ 37^{-1} &\equiv 4 \equiv -3 \mod 7 \\ 7^{-1} &\equiv 2 \mod 13 \\ 37^{-1} &\equiv 6 \mod 13 \\ 7^{-1} &\equiv 16 \mod 37 \\ 13^{-1} &\equiv 20 \mod 37 \end{align} $$

Using them we can find representatives of each of the three target congruences that are divisible by the other moduli:

$$ \begin{align} r_1 = 2 \times 13 \times -1 \times 37 \times -3 &\equiv \begin{cases} 2 \mod 7 \\ 0 \mod 13 \\ 0 \mod 37 \end{cases} \\ r_2 = 10 \times 7 \times 2 \times 37 \times 6 &\equiv \begin{cases} 0 \mod 7 \\ 10 \mod 13 \\ 0 \mod 37 \end{cases} \\ r_3 = -10 \times 7 \times 16 \times 13 \times 20 &\equiv \begin{cases} 0 \mod 7 \\ 0 \mod 13 \\ 27 \mod 37 \end{cases} \end{align} $$

Their sum satisfies all required congruences simultaneously: $$r_1+r_2+r_3 = 26 \times 111 + 70 \times (444 - 4160) = 2886 - 70 \times 3716 \equiv 2886 - 70 \times 349 = 2886 - 24430 \equiv 2025 \mod 3367$$

where $3367 = 7 \times 13 \times 37$.

The next congruent after $2025$ is $5392$ which is clearly too large ($5000^3>10^{11}$ and we see that $5000^{36}$ already has too many digits)

Therefore $2025$ must be the answer because it is the only solution in the right ballpark.

Answer:

n = 2025

(Not an) explanation:

Because it was asked in a math contest around the new year, and the year is 2025.

As a sanity check, the number of digits of the RHS is 128, which is between 117 = 39×3 and 152 = 38×4, so n is between 1000 and 10000, but closer to 1000. Since 128-117= 11, and 2³⁹ ≈ 10¹¹, we expect n to be around 2000. Also, the units digits of the terms in the sum are 1, 4, 9, 6, 5, 6, 9, 4, 1, 0, repeat, so any n for which the sum ends in 5 is of the form 20k+r where r = 2, 5, 9, 14, or 17. Clearly, n = 2025 is consistent with all these observations.

Answer:

$n=2025$

Explanation:

Trivially, $\sum_{i=1}^ni^{38}\approx n^{39}/39$, so $n^{39}\approx39\times\ 2.31\times10^{127}\approx9\times10^{128}$

Now we simply have to take the 39th root, which we do with a logarithm.

$\log(9\times10^{128})=128+2\log3\approx128.95424$since $\log3\approx0.47712$. I'll also include a rough estimate of 129 for a faster but less accurate calculation.

Therefore, taking the root with have $\log$ equal to

$128.98424/39\approx3.30729$. Alternatively, $129/39\approx3.3$

Now we need to find $10^{3.30729}$ (or $10^{3.3}$). Since

$2=10^{0.30103}$, the answer is $2000\times10^{0.00626}$. If we use rough estimates, $10^{3.3}\approx2000$ would do.

Therefore, we need

$2000\times e^{0.00626\times\ln10}$, where $\ln10\approx2.3$. Therefore, $0.00626\times2.3=0.0144$ should be raised.

It is common knowledge that the Taylor Expansion of $e^x$ is

$x^0/0!+x^1/1!+x^2/2!+\cdots$

so we can approximate with

$1+x+x^2/2=1+0.0144+0.0001=1.0145$.

Multiplying by $2000$ gives

$2029$, suspiciously close to the current year. Our very rough estimate is $2000$.

Now that we know the rough range,

$2029\pm10$ (our calculations are never off by over $0.1\%$, and they can only add up so much). (Or $2000\pm50$.)

we can use a modulo argument, since

$k^5\equiv k\mod10$ by Fermat's Little Theorem, $k^{38}\equiv k^2\mod10$, and this repeats in 1, 4, 9, 6, 5, 6, 9, 4, 1, 0,

so cumulative sums ends in

1, 5, 4, 0, 5, 1, 0, 4, 5, 5, 6, 0, 9, 5, 0, 6, 5, 9, 0, 0 for numbers equal to 1 through 20 mod 20.

The given number ends in 5, so the residue is

2, 5, 9, 10, 14, 17 mod 20

which leaves

2022, 2025, 2029, 2030, 2034, 2037.

To narrow it down further, we can provide a modulo 9 argument as well, with

$k^7=k$ since the euler totient of 9 is 6 and hence $k^{38}=k^2$ as well, which repeats, 1, 4, 0, 7, 7, 0, 4, 1, 0

so the cumulative sums (mod 9) are

1, 5, 5, 3, 1, 1, 5, 6, 6, 7, 2, 2, 0, 7, 7, 2, 3, 3, 4, 8, 8, 6, 4, 4, 8, 0, 0 which repeats with period 27

Since our given is a multiple of 9,

It is mod 27 equal to 13, 26, or 27.

This only leaves one choice:

2025. (Even if we round off a lot.)

If you want to completely skip residue shenanigans:

Recognize that $\sum_{i=1}^nn^{38}$ is a Riemann sum of the definite integral of $x^{38}$. $\int x^{38}dx$ is trivially $x^{39}/39 + C$. Since this is monotonic, we have the bound $\int_0^nx^{38}dx < \sum_{i=1}^nn^{38} < \int_1^{n+1}x^{38}dx$. Substituting, $n^{39}/39 < \sum_{i=1}^nn^{38} < (n+1)^{39}/39 - 1/39$.

Ignoring the final $1/39$ and simplifying, $n^{39} < 39\sum_{i=1}^nn^{38} < (n+1)^{39}$. We can simplify further to $n = \left\lfloor \sqrt[39]{ 39\sum_{i=1}^nn^{38} } \right\rfloor$, but this isn't helpful here. For the sake of brevity, we'll let the given value of $\sum_{i=1}^nn^{38}$ be $S$.

Multiplying $S$ by $39$ is easy enough to do with pencil and paper. The most efficient way would be to find $20S$, then $40S$, and finally $39S$.

We have:

01 x S : 023103964552947537663511830783699848235835114091576114282100411910644864693207138533340427131745931484436237548793821338133952725
10 x S : 231039645529475376635118307836998482358351140915761142821004119106448646932071385333404271317459314844362375487938213381339527250
20 x S : 462079291058950753270236615673996964716702281831522285642008238212897293864142770666808542634918629688724750975876426762679054500
40 x S : 924158582117901506540473231347993929433404563663044571284016476425794587728285541333617085269837259377449501951752853525358109000
01 x S : 023103964552947537663511830783699848235835114091576114282100411910644864693207138533340427131745931484436237548793821338133952725
39 x S : 901054618564953968876961400564294081197569449571468457001916064515149723035078402800276658138091327893013264402959032187224156275

Now, what remains to be done is to find the biggest $n$ such that $n^{39}$ is less than $39S$. This is hard. Our number is $129$ digits long. $129$ is slightly higher than $39\times3=117$. $39\times4=156$, which is much higher than $129$. Therefore, we know that the answer will be $4$ digits and on the small side. We can start with $3000$. (My first instinct would be to start with $2000$, but let's take a less smart approach just to show how this can end up.)

Therefore, we need to find $3^{39}$. This is done with fast exponentiation. Recall that $3^{10}=59049$ which is easy to memorize or verify. We can therefore square $59049$ twice. We can use chunking, which is essentially splitting $59049$ into $59|049$. To square $59|049$, we have $59^2=60^2-2\cdot60+1=3481$, $49^2=50^2-2\cdot50+1=2401$, and $2\cdot49\cdot59=(100-2)\cdot59=5900-118=5782$. $59049^2=(59000+49)^2=59000^2+2\cdot59000\cdot49+49^2=3481000000+5782000+2401=3486784401$.

We can now square $3486784401$. We can cross multiply and finally divide by $3$ to get $3^{40}/3=3^{39}$:

         1  3  7 11 17 22 26 29 26 24 19 14  9  4  3  0  0  0  0  0
         .  .  .  .  .  .  .  .  .  .  3  4  8  6  7  8  4  4  0  1
3 ^ 40 : 1  2  1  5  7  6  6  5  4  5  9  0  5  6  9  2  8  8  0  1
3 ^ 39 : 0  4  0  5  2  5  5  5  1  5  3  0  1  8  9  7  6  2  6  7

Therefore, $3000^{39}$ is that with another $3\times39=117$ zeros at the end.

  39 x S  :        901054618564953968876961400564294081197569449571468457001916064515149723035078402800276658138091327893013264402959032187224156275
3000 ^ 39 : 4052555153018976267000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Clearly, $3000^{39}>39S$ by a large margin. Now, let us try $2000$. Similarly, we need to first find $2^{39}$ by finding $2^{40}$. Luckily, $2^{20}=1048576$ is common knowledge. We just have to square that and divide by $2$. Following the same technique:

         0  0  0  1  3  9 13 15 20 17 11  8  3  0
         .  .  .  .  .  .  .  1  0  4  8  5  7  6
2 ^ 40 : 0  1  0  9  9  5  1  1  6  2  7  7  7  6
2 ^ 39 : 0  0  5  4  9  7  5  5  8  1  3  8  8  8

Therefore, we have this:

2000 ^ 39 :        549755813888000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  39 x S  :        901054618564953968876961400564294081197569449571468457001916064515149723035078402800276658138091327893013264402959032187224156275
3000 ^ 39 : 4052555153018976267000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

We can try to make an educated guess if we see that $(1+\epsilon)^{39}\approx1+39\epsilon$ for small $\epsilon$. This technique would not work for $3000^{39}$ since it is too far from $39S$, but it may work for $2000^{39}$. Notice that the ratio is $39S/2000^{39}\approx90/55=18/11=1.63636...$. We see that this will converge very slowly, so we ignore this (if we get a ratio of within $0.85$ to $1.15$, then we can try). Instead, we will need a closer result. Let us try $2020$. This is exactly the same method, but with larger numbers.

First, let us find $2020^{10}=2^{10}\cdot101^{10}$. $2^{10}=1024$ is trivial, and for $101^{10}$, we find the binomial coefficients $\binom{10}{k}$. $\binom{10}0=1$, $\binom{10}1=10$, and $\binom{10}2=45$ are trivial. $\binom{10}3=10\times9\times8\div3\div2\div1=120$, $\binom{10}4=10\times9\times8\times7\div4\div3\div2\div1=210$, and $\binom{10}5=10\times9\times8\times7\times6\div5\div4\div3\div2\div1=252$ are all easy as well. Therefore, $101^{10}=(100+1)^{10}=\sum_{i=0}^{10}100^i\binom{10}i$. This is equal to $110462212541120451001$. Now we find $110462212541120451001\times1024$ using the standard method:

0001 x 101 ^ 10 : 000110462212541120451001
0002 x 101 ^ 10 : 000220924425082240902002
0004 x 101 ^ 10 : 000441848850164481804004
0020 x 101 ^ 10 : 002209244250822409020020
1000 x 101 ^ 10 : 110462212541120451001000
1024 x 101 ^ 10 : 113113305642107341825024

What remains is to square this twice. We still use the same cross product approach here. I’ll jump to the result, since there’s nothing new here, just a couple more added digits.

2020 ^ 40 : 1637022987254237539539478159371760153964637764064741282935507415394314985409168992135555317760000000000000000000000000000000000000000

But what we want is $2020^{39}$. Obviously, we don’t want to do division, which is going to be messy. Instead, we multiply $39S$ by $2020$.

0001 x 39 x S : 0000901054618564953968876961400564294081197569449571468457001916064515149723035078402800276658138091327893013264402959032187224156275
0020 x 39 x S : 0018021092371299079377539228011285881623951388991429369140038321290302994460701568056005533162761826557860265288059180643744483125500
2000 x 39 x S : 1802109237129907937753922801128588162395138899142936914003832129030299446070156805600553316276182655786026528805918064374448312550000
2020 x 39 x S : 1820130329501207017131462029139874044019090288134366283143870450320602440530858373656558849438944482343886794093977245018192795675500
    2020 ^ 40 : 1637022987254237539539478159371760153964637764064741282935507415394314985409168992135555317760000000000000000000000000000000000000000

So now, we can get an educated guess.

$(1+\epsilon)^{39}\approx1+39\epsilon$ for small $\epsilon$. Notice that the ratio is $39S/2020^{39}=2020\times39S/2020^{40}\approx90/55=18/11=1.63636...$. We see that this will converge very slowly, so we ignore this (if we get a ratio of within $0.85$ to $1.15$, then we can try). Instead, we will need a closer result. Let us try $2020$. This is exactly the same method, but with larger numbers. The ratio is around $18/16=9/8=1.125$. That is decent. The ratio would be more accurately around $1820/1637$. To get nicer numbers, we multiply the numerator and the denominator with $611$. Now we get $1112020/1000207\approx1.112$. Recall that $(1+\epsilon)^{39}\approx1+39\epsilon$ for small $\epsilon$. Now we have $\epsilon\approx0.111/39=0.037/13$. Again, since our final result will be $2020+2020\epsilon$, we plug it in before simplification and get $2020+74.74/13$. This comes down to between $2025$ and $2026$. Here, our relative error term will be relatively small, at below $1\%$.

Hopefully, we don’t have to go through everything again with $2025$ and $2026$. Therefore, we want to establish bounds. We now know that the answer $N$ we need, which is likely $2025$, has $N^{39}<39S<(N+1)^{39}$. Therefore, we just need to prove that $2025^{39}<39S$ and $2026^{39}>39S$.

First, let us prove that $2026^{39}>39S$. We have $39S/2020^{39}<1821/1637$. We can prove that $1821/1637<1.113$ by multiplying the numerator and the denominator with $611$ and getting $1112631/1000207$, so we just need to prove that $(2026/2020)^{39}>1.112$. This is proven by $(1+\epsilon)^{39}>1+39\epsilon$. Since $1+\epsilon=2026/2020$, solving for $\epsilon$ gives $3/1010=0.3/101$. Multiplying both the numerator and the denominator by $99$ gives $29.7/9999=0.002970297...>0.00297$. Therefore, $39\epsilon>0.11583$, so $(1+\epsilon)^{39}>1+39\epsilon>1.11583>1.113>1821/1637>39S/2020^{39}$, and therefore multiplying both sides by $2020^{39}$ gives $2026^{39}>39S$. What remains to be proven is that $2025^{39}<39S$.

To prove that $2025^{39}<39S$, observe that $(1+\epsilon)^{39}=\sum_{i=0}^{39}\binom{39}i\epsilon^i$. Clearly, $\binom{39}i<39^i$. Therefore, $(1+\epsilon)^{39}=\sum_{i=0}^{39}\binom{39}i\epsilon^i<\sum_{i=0}^{39}39^i\epsilon^i=\sum_{i=0}^{39}(39\epsilon)^i=(1-(39\epsilon)^{40})/(1-39\epsilon)<1/(1-39\epsilon)$. $39S/2020^{39}>1820/1638=10/9$. Therefore, we just need $1-39\epsilon>9/10\iff39\epsilon<1/10\iff\epsilon<1/390$, but $\epsilon=2025/2020-1=5/2020=1/404<1/390$. Therefore, $(1+\epsilon)^{39}<1/(1-39\epsilon)=1/(1-39/404)=404/365<10/9<39S/2020^{39}$, and therefore multiplying both sides by $2020^{39}$ gives $2025^{39}<39S$.

Finally, since $n^{39} < 39\sum_{i=1}^nn^{38} < (n+1)^{39}$ and $n$ is an integer, $n\ge2025$ and $n\le2025$, so $n$ must be $2025$.

Sny's method is actually brilliant, here are some improvements, still respecting no-computers:

This sum S is Faulhaber's Formula for the power p=38, and for some unknown n : S = S_38 = $\sum_{i=1}^{n} i^{38}$

We combine getting a power-series based approximation to n +/-20%, then combine that with noting the divisibility of the Faulhaber polynomial form of S_n for even n by n(n+1)(2n+1)

A) I tried getting an approximation using the generalized-difference-of-powers identity...

$x^{39} - 1^{39}$ = $\left(x-1\right) \left( \sum_{i=1}^{n} x^{i}1^{38-i} \right) = \left(x-1\right) \left( \sum_{i=1}^{n} x^{38} \right)$

Actually that's a so-so approximation for: $S \approx \left(a^{39} - 1\right) / \left(a-1\right) \approx a^{39} / \left(a-1\right)$ It's actually no better than @Sny's approximation: $\sum_{i=1}^ni^{38}\approx n^{39}/39$

B) My alternative to get an approximation to $S^{1/38}$. We need some near-identity to 1/38 in a convenient power of 10 or 2. Noting 27*38 = 1026, then 1/38 = 27/1026 ≃ (27/1024), only off by a factor of (1024/1026) or 0.2%.

Then use a Binomial Expansion: $S^{1/38} \approx S^{27/1024}$

As @Sny noted, 3.33.. < log10(S) < 3.375 < 3.4, so pick suitable $\alpha$ so we can use the expansion for 3.4

Now 129.2 = 38*3.4, so 127 = (38*3.4 - 2.2) = (38*3.375 - 1.25)

Pick suitable $\alpha$ and use the binomial expansion for 3.4

... Anyway either way, by computing approximate $S_n^{1/38}$ we get to the ballpark estimate 2000 < n < 2400.

The next part is slightly nonrigorous trickery by noting the divisibility property of the Faulhaber polynomial form of S_n for even n by n(n+1)(2n+1)...(and other polynomial factors, although their coefficients in general are fractions, so this doesn't prove S mightn't have smaller numerical factors than n)

We're guided by the intuition that 2025 is one of the LHS factors, and waving a hand at the RHS algebra, we think it might be one of (n)(n+1)(2n+1). We can exclude (2n+1) since we know 2000 < n < 2400.

Note $2025 = 3^{4} \times 5^{2}$. Note that S is divisible by 25 (ends in 25) and by 9 (mod 9 congruence). Divisiblity by 81 is tested by two passes of computing the sum-of-digits and testing they're divisible by 9. Unfortunately for this approach, turns out S is only divisible by 27, not 81. That sucks. (It actually means the coefficients of the more complicated polynomial factor must have a common factor 1/3).

Anyway that approach would have at least strongly suggested that one of the factors n,(n+1) is 2025. The Chinese Remainder Theorem approach by Albert Lang is the rigorous approach.