当前位置:首页 » Project Euler » 详细页

How many reversible numbers are there below one-billion? 题号:145 难度: 20 中英对照

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (109)?

Solution

首先定义$n$-位数,其首尾均不能为$0$,其他$n-2$位可为 $(0\sim 9)$. 题中边界为 $10^9$, 所以$n$ 最多可取 $9$. 根据n的位数不同,分下列情况讨论: - **n = 1**: 显然不符合要求,因为 $n+ reverse(n) = odd$ - **n = 0 mod 2**: 即当n取偶数时,我们来证明下列性质, 特别地,取 $n = 6$ 时, 一个形式如"abcdef"的6-位数,满足 $ 0 <= \{a,b,c,d,e,f \} <= 9 $且 $ a \neq 0, f \neq 0 $. 我们计算该数和它的逆的和: ![add](https://ooo.0o0.ooo/2017/05/28/592a9bb0da8e9.png) 为了保证结果符合题意,两者和"tuvwxyz" 需要保证每位数字都是奇数,即 $ \in \{1,3,5,7,9\}$. 首先看中间两列(最左边为第1列),假设第4列 $ d + c = x$ 产生进位,那么第3列为 $c + d + 1 = w $. 但是这必须要求第4列也有一个进位,否则$x$ 和$w$ 将有不同奇偶性. 反之,如果第4列没有进位,那么第3列也没有进位,并且第3列也不会产生进位. 扩展这个性质,如果第5列有进位,那么必须要求第3和4列也有进位,应为暗含了第2列有进位. 即如果最右边的列没有进位,那么所以列都不会有进位. 这就告诉我们 ,**可以独立的处理每一列而不用考虑他们的进位问题**. Let's look at the first column with a + f = u (with u < 10 because there is no carry-out). When we choose a digit value for 'a', there is a set of values we can choose for 'f' so that their sum is odd. 'a' cannot be 0. When 'a' is 1, 'f' can be {2, 4, 6, 8} (not 0) and not produce a carry. When 'a' is 2, 'f' can be {1, 3, 5, 7} (not 9) and not produce a carry. We can list all the possibilities for (a, f): (1,2), (1,4), (1,6), (1,8), (2,1), (2,3), (2,5), (2,7), (3,2), (3,4), (3,6), (4,1), (4,3), (4,5), (5,2), (5,4), (6,1), (6,3), (7,2), (8,1). We see above that there are 20 choices for (a,f). For the middle digits (not first or last digit), we can use 0 so there are 30 choices: (0,1), (0,3), (0,5), (0,7), (0,9), (1,0), (1,2), (1,4), (1,6), (1,8), (2,1), (2,3), (2,5), (2,7), (3,0), (3,2), (3,4), (3,6), (4,1), (4,3), (4,5), (5,0), (5,2), (5,4), (6,1), (6,3), (7,0), (7,2), (8,1), (9,0). Therefore by combinatorics, there are $20 \times 30^{(n/2 - 1)} $ reversible n-digit numbers when n is even. - **n = 1 mod 2**: Let's illustrate what happens with a 7-digit number abcdefg: ![add2](https://ooo.0o0.ooo/2017/05/28/592a9e8bd9b4a.png) The middle column d + d = w will be even unless it has a carry-in from its right neighbor, so this carry is required. Hence the 4th column has a carry-in, which means the 5th column has a carry-out. By symmetry since 5th column carries out, then the 3rd column c + e = v must carry out as well. (This is true even in the worst case if 5th column has a carry-in but the 3rd column has no carry-in, because the sum must be odd and at least 11 so even if it drops to 10 there will still be a carry-out.) Because the 2nd column receives a carry-in, the 6th column must receive a carry-in to maintain parity. What this shows is that when the number of digits is odd, the middle column must have a carry-in, and columns that are an even distance away from it must have a carry-in. This means it is impossible to have a reversible number of length n = 1 mod 4, because that would force the rightmost column to have a carry-in, which is impossible by definition. Thus we require n = 3 mod 4. Let's analyze a bit further. The rightmost (7th) column has no carry-in by definition. So the leftmost (1st) column must have no carry-in to ensure that both t and z are odd. Then the 2nd column must have no carry-out, which implies the 6th column has no carry-out. This is why we get the alternating pattern of carries in the adding process. The rest of the work is to enumerate the possibilities for each type of digit(s) in the number: Pairs of digits which take no carry and must generate a carry (20 choices): (9,8), (9,6), (9,4), (9,2), (8,9), (8,7), (8,5), (8,3), (7,8), (7,6), (7,4), (6,9), (6,7), (6,5), (5,8), (5,6), (4,9), (4,7), (3,8), (2,9). Note that the first and last digits fall into this category, and there are no 0s at all. Non-middle pairs of digits which take a carry and generate no carry (25 choices): (0,0), (0,2), (0,4), (0,6), (0,8), (1,1), (1,3), (1,5), (1,7), (2,0), (2,2), (2,4), (2,6), (3,1), (3,3), (3,5), (4,0), (4,2), (4,4), (5,1), (5,3), (6,0), (6,2), (7,1), (8,0). Middle single digit, which takes a carry and generates no carry (5 choices): 0, 1, 2, 3, 4. All in all, there are $ 5 \times 20^{((n + 1)/4)} \times 25^{((n - 3)/4)} = 100 \times 500^{((n - 3)/4) }$ reversible n-digit numbers when n = 3 mod 4. **所以,所有的数字的和为:** $$ Sum = 20 \times 30^{(n/2 - 1)} + 100 \times 500^{((n - 3)/4) } $$

Code

public  class p145  {

    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }

    public static String run() {
        int sum = 0;
        for (int digits = 1; digits <= 9; digits++) {
            if (digits % 2 == 0)
                sum += 20 * pow(30, digits / 2 - 1);
            else if (digits % 4 == 3)
                sum += 100 * pow(500, (digits - 3) / 4);
            else if (digits % 4 == 1)
                sum += 0;
            else
                throw new AssertionError();
        }
        return Integer.toString(sum);
    }

    // Returns x to the power of y, throwing an exception if the result overflows an int.
    public static int pow(int x, int y) {
        if (x < 0)
            throw new IllegalArgumentException("Negative base not supported");
        if (y < 0)
            throw new IllegalArgumentException("Negative exponent");
        int z = 1;
        for (int i = 0; i < y; i++) {
            if (Integer.MAX_VALUE / z < x)
                throw new ArithmeticException("Overflow");
            z *= x;
        }
        return z;
    }
}
608720
1ms