# 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?

• When $n$ is odd, $n$ is a factor of $B$, and when $n$ is even, $n+1$ is a factor of $B$. Perhaps that could help. – Jonas Meyer Oct 7 '13 at 7:13
• Since $B=\frac{1}{2}n(n+1)$. – copper.hat Oct 7 '13 at 7:15
• @Jonas Meyer Thanks, I've guessed that $(2n+1) \nmid \sum_{k=1}^{2n+1} k^k$, but it turns out wrong :( – easymath3 Oct 7 '13 at 7:17
• @Benjamin Dickman I don't know, just found it in a Chinese BBS and no one solved it. I use Mathematica to try and it holds for n < 1000 – easymath3 Oct 7 '13 at 8:17
• The problem might be relatively tough. $A$ is discussed in an old AMM problem  and looks like a summation version of the hyperfactorial (mathworld.wolfram.com/Hyperfactorial.html) but is not something I otherwise recognize. Where is the Chinese site? – Benjamin Dickman Oct 7 '13 at 8:29

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.

• If I understand you correctly, you can go one step further and state that the original question is equivalent to this one: When does $n$ divide $\sum_{i=1}^{n-1} i^i$ for two consecutive values of $n$? (The smaller of the two values is a solution to the original question.) – Steve Kass Apr 21 '14 at 0:15
• Exactly <padding> – alexander-brett Apr 21 '14 at 0:19
• Thanks. It took me longer than it should have to realize that, so I thought it was worth mentioning for others! – Steve Kass Apr 21 '14 at 0:33
• @ali0sha where did $k_n$ come into it? – snulty Apr 21 '14 at 11:20
• Sorry I forgot to add it - I'm trying to emphasise that you can get rid of the factor of 2 by taking into account the parity of n – alexander-brett Apr 21 '14 at 12:35