-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathp145.mathematica
More file actions
125 lines (123 loc) · 6.47 KB
/
p145.mathematica
File metadata and controls
125 lines (123 loc) · 6.47 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
(*
* Solution to Project Euler problem 145
* Copyright (c) Project Nayuki. All rights reserved.
*
* https://www.nayuki.io/page/project-euler-solutions
* https://github.com/nayuki/Project-Euler-solutions
*)
(*
* First we define an n-digit number as a number beginning with the digit 1 to 9 (i.e. not 0) and having (n-1)
* of any digit thereafter. For example, 10652 is a 5-digit number, but 08913 = 8913 is a 4-digit number.
*
* Lucky for us, the problem bound of 10^9 means that we examine all 1-to-9-digit numbers and not need
* to exclude some subrange. Note that we need to exclude all numbers ending in 0, so that the
* reversed number does not have leading zeros.
*
* Consider different cases for the number of digits n (from 1 to 9, but the arguments apply generally):
* - n = 1:
* Clearly there are no solutions because the last digit is always even.
*
* - n = 0 mod 2:
* We begin by proving that when a number is "reversible", the process of adding
* the number to the reverse of itself will involve no carries in the arithmetic.
* Normally a rigorous proof would require the use of mathematical induction,
* but instead we will do illustratively with the specific case of n = 6.
* A 6-digit number looks like abcdef, where each of 0 <= {a,b,c,d,e,f} <= 9, except a != 0.
* When we add the number to its reverse, we get a structure like this:
* abcdef
* + fedcba
* --------
* tuvwxyz
* For the number to be considered reversible, every digit in
* the sum tuvwxyz needs to be odd, i.e. in the set {1,3,5,7,9}.
*
* First look at the middle two columns. If the 4th column d + c = x generates a carry-out, then
* the 3rd column c + d + 1 = w receives a carry-in. But this would in turn require the 4th column to
* have a carry-in, because otherwise x and w would have opposite evenness/oddness. Conversely if the
* 4th column has no carry-out, then the 3rd column has no carry-in and also must have no carry-out.
* We can extend this argument outward from the middle. If the 5th column has a carry-out, then by
* the above argument it would cause the 4th and 3rd columns to have a carry-out, which implies
* the 2nd column has a carry-in, which would require the 5th column to have a carry-in.
* But once we get to the rightmost column, we know by definition that it has no carry-in.
* Hence the leftmost column has no carry-in, which implies the 2nd column has no carry-out.
* Therefore the whole sum has no carries at all. This lemma is good news because
* it means we can treat each column separately without worrying about their interactions.
*
* 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 * 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:
* 0101010
* abcdefg
* + gfedcba
* ---------
* stuvwxyz
* 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 * 20^((n + 1)/4) * 25^((n - 3)/4) = 100 * 500^((n - 3)/4)
* reversible n-digit numbers when n = 3 mod 4.
*)
CountReversibles[d_] := Piecewise[{
{20 * 30^(d / 2 - 1), Mod[d, 2] == 0},
{100 * 500^((d - 3) / 4), Mod[d, 4] == 3},
{0, Mod[d, 4] == 1}}]
Sum[CountReversibles[d], {d, 1, 9}]