19
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jonas Meyer Oct 7 '13 at 7:13
  • $\begingroup$ Since $B=\frac{1}{2}n(n+1)$. $\endgroup$ – copper.hat Oct 7 '13 at 7:15
  • $\begingroup$ @Jonas Meyer Thanks, I've guessed that $ (2n+1) \nmid \sum_{k=1}^{2n+1} k^k $, but it turns out wrong :( $\endgroup$ – easymath3 Oct 7 '13 at 7:17
  • $\begingroup$ @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 $\endgroup$ – easymath3 Oct 7 '13 at 8:17
  • 1
    $\begingroup$ The problem might be relatively tough. $A$ is discussed in an old AMM problem [4155] 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? $\endgroup$ – Benjamin Dickman Oct 7 '13 at 8:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Steve Kass Apr 21 '14 at 0:15
  • $\begingroup$ Exactly <padding> $\endgroup$ – alexander-brett Apr 21 '14 at 0:19
  • $\begingroup$ Thanks. It took me longer than it should have to realize that, so I thought it was worth mentioning for others! $\endgroup$ – Steve Kass Apr 21 '14 at 0:33
  • $\begingroup$ @ali0sha where did $k_n$ come into it? $\endgroup$ – snulty Apr 21 '14 at 11:20
  • $\begingroup$ 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 $\endgroup$ – alexander-brett Apr 21 '14 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.