Enjoying 2018 while it lasts, Part 2

It is a pretty well-known fact that the number of ways a positive integer $n$ can be expressed as a sum of consecutive positive integers is equal to the number of odd divisors of $n$ . As a reminder, we will outline a proof, establishing a bijection between the odd divisors of $n$ and the ways of writing $n$ as a sum of consecutive positive integers: If $d|n$ , we can write $n$ as the sum of $d$ consecutive integers with middle term $\frac{n}{d}$ . Lets illustrate this process by means of the example $n=15$ : For $d=1$ we have $15=15$ ; for $d=3$ we have $15=4+5+6$ , for $d=5$ we have $15=1+2+3+4+5$ , and for $d=15$ we have $15= (-6)+(-5)+...+6+7+8$ . If the representation contains negative integers or 0, we cancel them out. For example, in the last case, $15= 7+8$ . It is not hard to see that all representations of $n$ as a sum of consecutive positive integers can be obtained in this way.

Lets introduce some terminology; $n$ will denote a positive integer throughout. Let $a(n)$ be the number of odd divisors of $n$ , let $S$ be the set of all $n$ with $a(n)>2018$ and let $N$ be the smallest element of $S$ . Note that we need at least 2019 odd divisors since we are not counting the trivial representation $n=n$ corresponding to the divisor $d=1$ .

Our goal is to show that $N$ is odd and divisible by 5; this will imply that the last digit is $\boxed{5}$ .

If the prime factorization of $n$ is $n=2^{n_0}p_1^{n_1}...p_m^{n_m}$ , then it is not hard to see that $a(n)=\prod_{j=1}^{m}(n_j+1)$ . Note that $a(n)=a(2n)$ , so that $N$ is odd as claimed.

We claim that $N$ fails to be a power of 3. Indeed, the smallest power of 3 in $S$ is $3^{2018}$ , but $3^{1009}5$ is a much smaller member of $S$ . Let $p$ be the smallest prime factor of $N$ larger than 3. We can write $N=p^q m$ , where $q\geq 1$ and $p$ fails to be a factor of $m$ . Then $a(N)=(q+1)a(m)=a(5^qm)$ , showing that $5^q m \in S$ and $N=5^q m$ , concluding our proof.

(It is worth mentioning that the answer remains the same if 2018 is replaced by any integer greater than 2.)

I took me a long time to realize this, but as Otto Bretscher said: "It is a pretty well-known fact that the number of ways a positive integer $n$ can be expressed as a sum of consecutive positive integers is equal to the number of odd divisors of $n$ ."

Assume that the solution $N$ is even, so $N=2 \cdot k, k \in \mathbb{N}$ . The divisors of $N$ are either a divisor of $k$ or $2\cdot($ a divisor of $k)$ . So $k$ and $N$ have the same number of odd divisors, but $N > k$ , hence $N$ cannot be the solution. We showed by contradiction that $N$ is odd.

So $N$ can be factorized as $N = 3^{p_3} \cdot 5^{p_5} \cdot 7^{p_7} \cdot 11^{p_{11}} \cdot ...$

The number of odd divisors for a certain solution is $Q = (p_3 + 1) \cdot (p_5 + 1) \cdot (p_7 + 1) \cdot (p_{11} + 1) \cdot ...$

When choosing the primes to compose $N$ , it's always better to take a certain prime once before taking any larger one, because it makes $N$ less large for the same impact on $Q$ . So either the solution is $3^{2017}$ or $p_5 > 0$ . The first one is obviously false (counter-example: $5 \cdot 3^{1008} < 3^{2017}$ ), hence $p_5 > 0$ . This means that $N$ is the product of $5$ and an odd number, which implies that the last digit is $5$ .

I wrote a script that looks for the smallest $N$ with $Q \ge 2018$ and I found $N = 727'840'488'375 = 3^3 \cdot 5^3 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$ with $Q = 2048$ .

It is not very hard to figure out that the last digit is 5. But finding $N$ may not be that easy.

We may ignore a fact: $N$ must be written as the sum of two or more consecutive POSITIVE integers. A positive integer $N$ (prime factorization: $N = 3^{p_3} \times 5^{p_5} \times7 ^{p_7} \times ...$ ) can not written as $(p_3+1) \times (p_5+1) \times (p_7+1) \times ...$ ways, not that many.

For some simple samples:

$21 = 3^1 \times 7^1$ , so 21 can be written as the sum of 7 consecutive integers, but these 7 numbers are NOT ALL POSITIVE: 0 , 1, 2, 3, 4, 5, 6.

$45 = 3^2 \times 5^1$ , so 45 can be written as the sum of 15 consecutive integers, but these 15 numbers are NOT ALL POSITIVE: -4, -3, -2, -1, 0, ..., 9, 10.

The samples above mean, if $N = A \cdot B$ ( $A$ and $B$ are odd positive integers), and $B > 2A$ , then $N$ can be written as the sum of $A$ consecutive integers, but these $A$ numbers are NOT ALL POSITIVE.

Some solvers have attempt to find $N$ by solely using prime factorization ways, I am afraid that all those are not right answer.