Question related to sequence A071267

[David Wilson]

Let f(n) be the sum of all permutes of n.

Let

    s(n) = sum of digits of n.
    d(n) = number of digits of n.
    c_n(k) = number of occurences of digit k in n.
    p(n) = PROD(k = 0..9; c_n(k)!).
    r(n) = n-digit rep-1 number = (10^n-1)/n.
    t(n) = ((s(n)(d(n)-1)!)/p(n)).

Then f(n) = t(n) r(d(n)).


For example, if n = 314159, we get

    s(n) = 23
    d(n) = 6
    c_n = (0, 2, 0, 1, 1, 1, 0, 0, 0, 1)
    p(n) = PROD(k = 0..9; c_n(k)!) = 2
    r(d(n)) = r(6) = 111111
    t(n) = (23*120)/2 = 1380

and

    f(314159) = 1380*11111 = 153333180


A combinatorial argument shows that when we add the permutes of n, the same number of each digit will appear in each column of the sum. This means that

    f(n) = (sum of each column) * (d(n)-digit rep-1 number)
         = (sum of each column) * r(d(n))

from which we conclude

    t(n) = sum of each column

implying that t(n) is integer and r(d(n)) | f(n).


Using this knowledge, we can explore why f(n) = 29997 is insoluble while f(n) = 2997 is not.

Let n have d(n) digits. Then n <= 9 r(d(n)) and has at most d(n)! permutes. This means that

    [1] f(n) <= 9 r(d(n)) d(n)!

Suppose f(n) = 29997. We know that r(d(n)) | f(n), and the only rep-1 numbers that divide 29997 are r(1) = 1, r(2) = 11 and r(4) = 1111, implying d(n) = 1, 2 or 4. From [1],

    d(n) = 1  =>  f(n) <= 9
    d(n) = 2  =>  f(n) <= 198
    d(n) = 4  =>  f(n) <= 239976

Given f(n) = 29997, we must have d(n) = 4 and r(d(n)) = 1111.

This means that

    t(n) = f(n)/r(d(n)) = 29997/1111 = 27.

so that

    ((s(n)(d(n)-1)!)/p(n)) = 27.

Since d(n) = 4, we have

    6 s(n)/p(n) = 27
    => s(n) = 9(p(n)/2).

Since p(n) and s(n) are both integer, p(n) must be even to make the right side integer. This means 9 | s(n) <= 9 d(n) = 36. This means that s(n) = 9, 18, 27 or 36.

Suppose s(n) = 9. Then p(n) = 2. By the definition of p(n), p(n) = 2 iff exactly one digit appears twice in n and all others once (or not at all). So we are looking for a 4-digit n with a single repeated digit and digit sum 9. Many such numbers exist, 1008 being the smallest, and indeed f(1008) = 29997.


But now look at f(n) = 2997.  Following similar logic to the above, we find that d(n) = 3 and t(n) = 27 giving

    ((s(n)(d(n)-1)!)/p(n)) = 27
    => 2 s(n)/p(n) = 27
    => s(n) = 27(p(n)/2).

Again, p(n) must be even, so 27 | s(n). But s(n) <= 9 d(n) = 27, so s(n) = 27 forcing n = 999 and f(n) = 999. Hence f(n) = 2997 is insoluble.




-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20070712/a72e8853/attachment-0001.htm>