Is $\sum_{k=1}^{n} k^k / \sum_{k=1}^{n} k \in \mathbb{N}$ for some $n > 1$?

Let $ A = \sum_{k=1}^{n} k^k $ and $ B = \sum_{k=1}^{n} k$, where $n >1 $ is a positive integer.

Is $A/B$ ever an integer?

Solution 1:

Write $\sum n = \frac 1 2 n(n+1)$, and note that $n \mid n^n$ but $n+1 \nmid n^n$. For coprime $a$ and $b$ (nb. $n$ and $n+1$ are coprime):

$ab \mid n \iff a \mid n \wedge b\mid n$

and

$a\mid q\times a+r \iff a \mid r$

we can write:

$\frac {n(n+1)}{2} \mid \sum_{i=1}^n i^i \iff \{k_{n+1} \mid \sum_{i=1}^n i^i\} \wedge \{k_n \mid \sum_{i=1}^{n-1} i^i\}$

Where $k_n = \begin{cases} \frac n 2 & n \text{ is even} \\ n & \text{ otherwise} \end{cases}$

This reduces the problem to working out:

$\text{When does } k_n \text{ divide } \sum_{i=1}^{n-1} i^i \text{ ?} \quad*$

I tested every number up to 132,000 (using a script I've appended at the bottom) and the numbers satisfying $n\mid \sum_{i=0}^n i^i$ are:

1 
3     =3
7     =7
16    =2*2*2*2
18    =2*3*3
33    =3*11
49    =7*7
147   =3*7*7
161   =7*23
183   =3*61
487   =487
647   =647
1549  =1549
1576  =2*2*2*197
3563  =7*509
4049  =4049
4387  =41*107
5872  =2*2*2*2*367
6638  =2*3319
8578  =2*4289
8805  =3*5*587
9549  =3*3*1061
59453 =59453   
62499 =3*83*251

I am interested that these numbers have very few prime factors and I think that it might might be possible to prove that:

• there are infinitely many such numbers
• there are no pairs of such numbers

using a combination of interesting modular arithmetic and some fun prime number manipulation.