2 shunfurh shunfurh 于 2017.09.10 22:20 提问

Persistent Numbers

The multiplicative persistence of a number is defined by Neil Sloane (Neil J.A. Sloane in The Persistence of a Number published in Journal of Recreational Mathematics 6, 1973, pp. 97-98., 1973) as the number of steps to reach a one-digit number when repeatedly multiplying the digits. Example:

679 -> 378 -> 168 -> 48 -> 32 -> 6.
That is, the persistence of 679 is 5. The persistence of a single digit number is 0. At the time of this writing it is known that there are numbers with the persistence of 11. It is not known whether there are numbers with the persistence of 12 but it is known that if they exists then the smallest of them would have more than 3000 digits.

The problem that you are to solve here is: what is the smallest number such that the first step of computing its persistence results in the given number?

Input

For each test case there is a single line of input containing a decimal number with up to 1000 digits. A line containing -1 follows the last test case.

Output

For each test case you are to output one line containing one integer number satisfying the condition stated above or a statement saying that there is no such number in the format shown below.

Sample Input

0
1
4
7
18
49
51
768
-1

Sample Output

10
11
14
17
29
77
There is no such number.
2688

2个回答

caozhy
caozhy   Ds   Rxr 2017.09.27 22:11
已采纳
weixin_39195527
weixin_39195527   2017.09.11 12:28

简易的python版,欢迎讨论

import re
import sys
import os

def get_divisor(num, base=[]):
    """
    """
    if len(str(num)) == 1:
        if len(base) == 0:
            return [1, num]
        else:
            return sorted(base + [num])

    for i in range(2, 9):
        if num % i == 0: 
            return get_divisor(num / i, base + [i])

    return "There is no such number."

def merge_num(base):
    """
    """
    label = True
    while(label):
        _var = []
        if len(base) <= 2: break

        index = len(base) - 1
        while(index > 0):
            temp = base[0] * base[index]
            if temp >= 10:
                index -= 1
            if temp < 10:
                del base[index], base[0]
                base.append(temp)
                base = sorted(base)
                break

            if index <= 0:
                label = False
    return base

def get_least_num(num, base=[]):
    """
    """
    base = get_divisor(num, base)
    if type(base) is str:
        return base
    if len(base) == 2:
        return base[0] * 10 + base[1]

    _var = merge_num(base)
    temp = 0
    L = len(_var)
    for i in range(L):
        temp += _var[i] * (10 ** (L - i - 1))
    return temp


def main():
    """
    """
    # print get_least_num(0, [])
    # print get_least_num(1, [])
    # print get_least_num(4, [])
    # print get_least_num(7, [])
    # print get_least_num(18, [])
    # print get_least_num(49, [])
    # print get_least_num(51, [])
    # print get_least_num(768, [])
    for line in sys.stdin:
        if int(line) == -1: break
        _var = int(line)
        print get_least_num(_var)


if __name__ == "__main__":
    reload(sys)
    sys.setdefaultencoding("utf-8")

    main()


Csdn user default icon
上传中...
上传图片
插入图片