[seqfan] Re: List the dividers, sum the digits

[hv at crypt.org]

Let's call this mapping f(). For any loop, we must include at least one
element k with f(k) >= k. For k <= 10000, that's true [1] only for:

  1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 14, 15, 16, 18, 24, 28, 36, 48

(and those starting points lead only to the known loops 1 and 15).

Here's an attempt at proof that f(k) < k for all k > 10000, and that the
list above is therefore finite and complete:

Any large factor of k has digit sum at most 9(log_10(k) + 1); any small
factor s has digit sum at most s. Taking the worst case when k is
divisible by all integers up to its square root, we then get:

  f(k) <= sum_{i=1}^{sqrt(k)}{ i + 9(log_10(k) + 1) }
       <= k/2 + sqrt(k)( 19/2 + 9 log_10(k) )

.. so for f(k) >= k we need g(k) >= 1 with:

  g(k) = ( 18 log_10(k) + 19 ) / sqrt(k)

When k=10^4 we have g(k) = (18 . 4 + 19) / 100 = 0.91, and g is clearly
a decreasing function of k in this range, so f(k) < k for all k >= 10^4.

Please check if I've made any errors: that seemed to fall out a bit too
neatly. :)

Hugo

[1] I used this Perl program:
  use Math::Prime::Util 'divisors';
  for my $k (1 .. 10000) {
    my $sum = 0;
    for (divisors($k)) {
      $sum += $_ for split //, $_;  # split to digits, and sum
    }
    print "$k -> $sum\n" if $k <= $sum;
  }

Frank Adams-Watters <franktaw at netscape.net> wrote:
:The digit sum of 1,13 is 5, not 14. I get
:
:10 -> 9 -> 13 -> 5 -> 6 -> 12 -> 19 -> 11 -> 3 -> 4 -> 7 -> 8 -> 15
:
:Any loops are going to contain only small numbers; the digit sum reduces large numbers by a lot. Everything up to 13 is covered by the example above (adding 2 -> 3).
:
:We have 14 -> 15; 16 -> 22 -> 9, 17 -> 9, 18 -> 30 -> 27 -> 22, and 20 -> 15, so everything 1 to 20 gets to 15.
:
:I suspect 1 and 15 are the only loops.
:
:Franklin T. Adams-Watters
:
:
:-----Original Message-----
:From: Eric Angelini <Eric.Angelini at kntv.be>
:To: Sequence Discussion list <seqfan at list.seqfan.eu>
:Sent: Sat, Nov 7, 2015 4:46 pm
:Subject: [seqfan] List the dividers, sum the digits
:
:
:
:Hello SeqFans,
:1) list all dividers of A (1 and A included) ;
:2) sum all
:digits of the above list ;
:3) iterate
:
:Example for A=10:
:10--> 1,10,2,5
:dig.sum=9
: 9--> 1,9,3      dig.sum=13
:13--> 1,13       dig.sum=14
:14-->
:1,14,2,7 dig.sum=15
:15--> 1,15,3,5 dig.sum=15 (fixed point)
:
:
:
:_______________________________________________
:
:Seqfan Mailing list - http://list.seqfan.eu/