Multiplicative Persistance

March 26, 2019

Over at NumberPhile, Matt and Brady are talking about multiplicative persistance:

Take a number. Multiply all its digits together. Repeat with the new number until it reaches a single digit. For instance, starting from 327, the product of the digits 3, 2 and 7 is 42, then recurring with 42 the product of the digits 4 and 2 is 8, which is the final answer; we say the sequence 327 → 42 → 8 finishes in 2 steps. What number leads to a sequence with the maximal number of steps?

The video includes some live-coding in Python by Matt.

Your task is to implement a function to compute the multiplicative persistance sequence starting from a given number, then “play with it” as Matt suggests. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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: