Multiplicative Persistance

March 26, 2019

Our per function is a little bit different than Matt’s; it returns the sequence in reverse order:

(define (per n)
  (let loop ((n n) (xs (list)))
    (if (< n 10)
        (cons n xs)
        (loop (apply * (digits n))
              (cons n xs)))))

Here’s a quick check:

> (per 327)
(8 42 327)

Now we can play. The most common ending number, appearing about 90% of the time, is 0:

> (sort (lambda (x y) (< (cdr y) (cdr x)))
         (uniq-c = (sort  <
           (map car (map per (range 1 1000001))))))
((0 . 902609) (6 . 43538) (8 . 32658) (2 . 16673) (4 . 2345)
  (5 . 2073) (9 . 56) (3 . 21) (7 . 21) (1 . 6))

The most common number of steps is 1, though 2 is not far behind:

> (sort (lambda (x y) ( < (cdr y) (cdr x)))
         (uniq-c = (sort <
           (map (lambda (xs) (- (length xs) 1))
             (map per (range 1 1000001))))))
((1 . 402540) (2 . 375227) (3 . 123860) (4 . 66772)
  (5 . 24654) (6 . 4488) (7 . 2450) (0 . 9))

And here are the records that occur each time a sequence is longer than any previous sequence:

> (let loop ((n 1) (record -1))
    (let* ((p (per n)) (len (- (length p) 1)))
      (when (< record len)
        (display len) (display " ") (display p) (newline))
      (loop (+ n 1) (max record len))))
0 (1)
1 (0 10)
2 (0 10 25)
3 (4 14 27 39)
4 (8 18 36 49 77)
5 (6 32 48 168 378 679)
6 (0 20 54 336 768 2688 6788)
7 (0 20 54 336 768 2688 27648 68889)
8 (0 20 54 336 768 2688 27648 338688 2677889)
9 (0 20 54 336 768 2688 27648 338688 4478976 26888999)
10 (0 20 54 336 768 2688 27648 338688 4478976 438939648 3778888999)
11 (0 20 54 336 768 2688 27648 338688 4478976 438939648 4996238671872 277777788888899)

I cheated. I let my computer run for a few hours to compute the records up to 10, then stopped the computation and use the known record for 11. You can run the program at https://ideone.com/Vho12W.

Advertisements

Pages: 1 2

9 Responses to “Multiplicative Persistance”

  1. Paul said

    In Python. As suggested in the video only certain patterns of numbers is searched. The results come in a few seconds. After that no more numbers are found up to 50 digits.

    from functools import reduce
    from operator import mul
    from itertools import combinations_with_replacement
    
    def mult(n):
        pr = [n]
        while n > 9:
            n =  reduce(mul, (int(c) for c in str(n)))
            pr.append(n)
        return pr
    
    def search():
        """ all solutions start with 2, 3, or 6
            rest of the numbers are 6, 7 ,8 ,9
        """
        first = "23 "
        rest = "6789"
        ms = 0
        for N in range(2, 50):
            for f in first:
                for m in combinations_with_replacement(rest, N + (1 if f == " " else 0)):
                    n = int(f + "".join(m))
                    steps = mult(n)
                    if len(steps) > ms:
                        ms = len(steps)
                        print("-".join(str(s) for s in steps))
                    
    search()
    
  2. Paul said

    Strange. My comment ended up in page 2.??

  3. matthew said

    I also went for a Python solution, this one just enumerates multisets of 2..9 (in appropriate order) and uses the number with those digits in ascending order. A few seconds to get up to 277777788888899 (after looking at 435968 multisets), then nothing. https://oeis.org/A003001 has more details.

    from operator import mul
    from functools import reduce
    
    # The smallest number with a given number of steps must have digits
    # in ascending order and not contain 0 or 1.
    
    # Represent candidate numbers by multisets of 0..7:
    
    # Convert a multiset to an integer, nth multiset element is number of times
    # digit n+2 occurs, so eg. [1,2,0,2,0,0,0,1] => 233559
    
    def mset2int(s): return int(''.join([str(i+2)*d for (i,d) in enumerate(s)]) or '0')
    
    # Find the next multiset - when converted to integers as above, the
    # sequence of integers is in ascending order.
    def nextmultiset(s):
        # [..,n,0,..,0,m] -> [..,n-1,m+1,..,0,0]
        # [0,0,..,n] => [n+1,0,..,0]
        n = s[-1]; s[-1] = 0
        for i in range(len(s)-1,0,-1):
            if s[i-1] > 0:
                s[i-1] -= 1
                s[i] = n+1
                return
        s[0] = n+1
    
    # Count the number of reduction steps for an integer
    def countsteps(n):
        count = 0
        while n >= 10:
            n = reduce(mul,(int(d) for d in str(n)))
            count += 1
        return count
    
    s = [0]*8
    max = -1
    while True:
        n = mset2int(s)
        steps = countsteps(n)
        if steps > max:
            print(n,steps)
            max = steps
        nextmultiset(s)
    
  4. Ernie said

    I noticed an interesting pattern when I calculated the frequency of the final step in the range 1…10^n
    1 occurs n times
    3 and 7 occur n(n+1)/2 times
    9 occurs n(n+1)(n+2)/6 times

  5. Ernie said

    I noticed an interesting pattern when I calculated the frequency of the final step in the range 1…10^n
    1 occurs n times
    3 and 7 occur n(n+1)/2 times
    9 occurs n(n+1)(n+2)/6 times

  6. matthew said

    @Ernie: nice observation, looks like the only numbers going to 1 are 100.., going to 3 are 311.. & permutations, going to 7 are 711.. & permutations and going to 9 are 3311… and 911…, with permutations which gives the result you see. For other numbers to end up here, we would need eg. 311111 to have only 2,3,5 and 7 as prime factors which is (presumably) unlikely, though I don’t see why it should be ruled out.

  7. matthew said

    Investigating further, there seems to only a finite number of fundamentally different numbers that end up at something other than 0. The product of digits can only have 2,3,5 and 7 as prime factors so generating multisets of 0..3 gives us all numbers of that form. We quickly get up to 239 * 33 * 7**2, but after that everything seems to end up at 0:

    from operator import mul
    from functools import reduce
    
    def nextmultiset(s):
        n = s[-1]; s[-1] = 0
        for i in range(len(s)-1,0,-1):
            if s[i-1] > 0:
                s[i-1] -= 1
                s[i] = n+1
                return
        s[0] = n+1
    
    def seq(n):
        s = [n]
        while n >= 10:
            n = reduce(mul,(int(d) for d in str(n)))
            s += [n]
        return s
    
    def test():
        s = [0]*4
        while True:
            n = 2**s[0] * 3**s[1] * 5**s[2] * 7**s[3]
            a = seq(n)
            if a[-1] != 0: print(n,s,a)
            nextmultiset(s)
    
    test()
    
    """
    (1, [0, 0, 0, 0], [1])
    (2, [1, 0, 0, 0], [2])
    (3, [0, 1, 0, 0], [3])
    (5, [0, 0, 1, 0], [5])
    (7, [0, 0, 0, 1], [7])
    (4, [2, 0, 0, 0], [4])
    (6, [1, 1, 0, 0], [6])
    (14, [1, 0, 0, 1], [14, 4])
    (9, [0, 2, 0, 0], [9])
    (15, [0, 1, 1, 0], [15, 5])
    ...
    (3416267673274176, [6, 27, 0, 1], [3416267673274176, 1792336896, 2939328, 23328, 288, 128, 16, 6])
    (913217421312, [29, 5, 0, 1], [913217421312, 18144, 128, 16, 6])
    (1438916737499136, [24, 6, 0, 6], [1438916737499136, 4444263936, 1492992, 11664, 144, 16, 6])
    (112717121716224, [34, 8, 0, 0], [112717121716224, 131712, 42, 8])
    (727326941773824, [39, 3, 0, 2], [727326941773824, 1194891264, 124416, 192, 18, 8])
    """
    
  8. Daniel said

    Here’s a solution in C.

    #include <inttypes.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(int argc, char* argv[]) {
      if (argc != 2) return EXIT_FAILURE;
      if (*argv[1] == '-') ++argv[1];
      intmax_t x = strtoimax(argv[1], NULL, 10);
      for (int i = 0;; ++i) {
        printf("%d %jd\n", i, x);
        if (x < 9) break;
        intmax_t y = 1;
        while (x) {
          y *= x % 10;
          x /= 10;
        }
        x = y;
      }
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./a.out 277777788888899
    0 277777788888899
    1 4996238671872
    2 438939648
    3 4478976
    4 338688
    5 27648
    6 2688
    7 768
    8 336
    9 54
    10 20
    11 0
    
  9. 
    Mumps version
    
    EN ; ENTER
     N I,J,N,NS,OLDNS,QTY,VAL
     K TMP
     W !,"PER(327) = ",$$PER(327)
     F I=0:1:9 S TMP(2,I)=0
     S OLDNS=-1
     F I=1:1:1000001 D
     . S L=$$PER(I)
     . S N=$P(L," "),NS=$L(L," ")-1
     . S TMP(2,N)=TMP(2,N)+1
     . S TMP(3,NS)=$G(TMP(3,NS))+1
     . I NS>OLDNS D
     . . S TMP(4,NS)=L
     . . S OLDNS=NS
     F I=2,3 S J=I+.5,N="" F  S N=$O(TMP(I,N)) Q:N=""  D
     . S QTY=TMP(I,N)
     . S TMP(J,-QTY)=$S('$D(TMP(J,-QTY)):N,1:TMP(J,-QTY)_" "_N)
     F I=2.5,3.5 D
     . W !!,$P("Common ending #;Common # of steps",";",I-1.5)
     . S N="" F  S N=$O(TMP(I,N)) Q:N=""  W !,TMP(I,N),": ",-N
     W !!,"Longer sequences:"
     S NS="" F  S NS=$O(TMP(4,NS)) Q:NS=""  S J=NS W !,$J(NS,2),": ",TMP(4,NS)
     F I=1000002:1 Q:NS=11  D
     . S L=$$PER(I),NS=$L(L," ")-1
     . I NS>J D
     . . W:$I(J) !,$J(NS,2),": ",L," ($H = ",$H,")"
     Q
     ;
    PER(N) ; Multiplicative Persistence
     N I,L,S
     S L=N
     F  Q:N<10  D
     . S S=1
     . F I=1:1:$L(N) S S=S*$E(N,I)
     . S N=S,L=N_" "_L
     Q L
     ;
    
    ---
    
    YDB>d ^multpers
    
    PER(327) = 8 42 327
    
    Common ending #
    0: 902610
    6: 43538
    8: 32658
    2: 16673
    4: 2345
    5: 2073
    9: 56
    3 7: 21
    1: 6
    
    Common # of steps
    1: 402541
    2: 375227
    3: 123860
    4: 66772
    5: 24654
    6: 4488
    7: 2450
    0: 9
    
    Longer sequences:
     0: 1
     1: 0 10
     2: 0 10 25
     3: 4 14 27 39
     4: 8 18 36 49 77
     5: 6 32 48 168 378 679
     6: 0 20 54 336 768 2688 6788
     7: 0 20 54 336 768 2688 27648 68889
     8: 0 20 54 336 768 2688 27648 338688 2677889 ($H = 65102,31491)
     9: 0 20 54 336 768 2688 27648 338688 4478976 26888999 ($H = 65102,31564)
    10: 0 20 54 336 768 2688 27648 338688 4478976 438939648 3778888999 ($H = 65102,43213)^C
    %YDB-I-CTRLC, CTRL_C encountered
    
    YDB>h
    
    sdfsdf
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: