1 2 3 4 5 6 7 8 * * - - / / 9 * * = 2010

ちょっと まえに @hariguchi さんが Knuth せんせいの 誕生日ケーキの 写真を twitter に はっていた。

なるほど、こういう しきって、あと なんとおり くらい あるんだろう、あとで しらべておこう、って おもったんだけれど、そのことを、せんしゅう にほんに かえった ときに おもいだした。

じかんも あったので、さくっと コードを かいて じっこう。ruby で 100ぎょうくらい。とくに 工夫も せずに ぜんぶ しらべたので えらく じかんが かかった。3じかん じゃく。もし 来年 2011 に なる くみあわせを しらべる ことに なったら、そのときには 半分いかの じかんで うごくように 改良してから じっこう したい。

さて、1 + 2 + 3... という くみあわせを すべて つくって それを 順番に しらべていく のは さすがに むちゃ なので、しきは RPN (Reverse Polish Notation) で ためす。かっこが いらないので シンプル。

けっかは、しきの くみあわせは 93,716,480 とおりで、2010 に 一致 したのは そのうち 186 とおり あった。けっこう ある。

1. 1 2 3 4 5 - 6 7 * 8 * + 9 * / / *
2. 1 2 3 4 5 + - 6 7 8 * * * - 9 - +
3. 1 2 3 4 5 + - 6 * 7 8 * * 9 + - +
4. 1 2 + 3 4 - 5 - 6 * 7 * 8 * 9 + -
5. 1 2 + 3 4 5 + - 6 7 8 * * * - 9 -
6. 1 2 * 3 / 4 5 - 6 7 * 8 * + 9 * *
7. 1 2 3 4 5 + - 6 * 7 * 8 * - 9 - +
8. 1 2 * 3 / 4 5 + 6 7 * * 8 * 9 - *
9. 1 2 3 4 5 6 * 7 8 * + * 9 - * * *
10. 1 2 3 4 5 - 6 7 8 * * + / 9 / / *
11. 1 2 3 4 5 + - 6 * 7 8 * * - + 9 -
12. 1 2 - 3 4 5 6 / 7 8 * + * - - 9 *
13. 1 2 3 / 4 5 - 6 7 * 8 * + 9 * * *
14. 1 2 3 / * 4 5 + 6 * 7 * 8 * 9 - *
15. 1 2 * 3 / 4 5 - 6 7 8 * * + * 9 *
16. 1 2 + 3 4 5 + - 6 7 * * 8 * 9 + -
17. 1 2 3 / 4 5 6 7 * 8 * - - * 9 * *
18. 1 2 3 / 4 5 - 6 7 8 * * + 9 * * *
19. 1 2 * 3 / 4 5 6 7 * 8 * - - 9 * *
20. 1 2 3 * * 4 5 6 * 7 8 * + * 9 - *
21. 1 2 - 3 - 4 5 + 6 / 7 8 * 9 * - *
22. 1 2 3 4 5 6 + * * 7 - * 8 * + 9 +
23. 1 2 3 4 5 + 6 7 * * 8 * 9 - / / *
24. 1 2 3 4 5 + - 6 7 * 8 * * - 9 - +
25. 1 2 3 4 * + + 5 6 7 8 + 9 * - - *
26. 1 2 + 3 4 5 + - 6 * 7 8 * * - 9 -
27. 1 2 3 / 4 5 + 6 7 * * 8 * 9 - * *
28. 1 2 3 + - 4 5 + 6 / 7 8 9 * * - *
29. 1 2 3 4 5 6 7 8 * * - - / / 9 * *
30. 1 2 3 4 5 + 6 7 * 8 * * 9 - / / *
31. 1 2 * 3 4 5 6 7 8 * * - - 9 * / /
32. 1 2 * 3 4 5 + 6 * 7 8 * * 9 - / /
33. 1 2 3 / 4 5 - 6 7 * 8 * + * 9 * *
34. 1 2 3 4 5 6 7 * 8 + + * + 9 * + +
35. 1 2 3 4 5 - 6 7 8 * * + / / 9 * *
36. 1 2 3 4 5 + 6 * 7 8 * * 9 - / / *
37. 1 2 3 / * 4 5 + 6 7 * * 8 * 9 - *
38. 1 2 3 / 4 5 - 6 7 8 * * + * 9 * *
39. 1 2 + 3 4 5 6 7 * + 8 + * + 9 * +
40. 1 2 + 3 4 - 5 - 6 * 7 8 * * - 9 -
41. 1 2 3 + - 4 5 6 / 7 8 * + * + 9 *
42. 1 2 3 4 5 6 7 8 * * - - / 9 / / *
43. 1 2 + 3 4 - 5 - 6 7 8 * * * - 9 -
44. 1 2 3 4 - 5 - 6 * 7 8 * * - 9 - +
45. 1 2 3 4 5 + - 6 7 * * + 8 * 9 - -
46. 1 2 3 4 * 5 6 + * 7 - 8 * * + 9 +
47. 1 2 3 4 * 5 6 + * 7 - * 8 * 9 + +
48. 1 2 3 / * 4 5 - 6 7 8 * * + * 9 *
49. 1 2 3 4 5 + - 6 * 7 * 8 * 9 + - +
50. 1 2 3 4 - 5 - 6 7 * * + 8 * - 9 +
51. 1 2 + 3 4 * + 5 6 7 8 + 9 * - - *
52. 1 2 + 3 4 5 6 - 7 8 * + * + 9 * +
53. 1 2 * 3 4 5 6 7 8 * * - - / / 9 *
54. 1 2 3 / * 4 5 6 7 * 8 * - - 9 * *
55. 1 2 3 + 4 5 6 / 7 8 * + * - - 9 *
56. 1 2 + 3 4 5 + * 6 + 7 * 8 - 9 * +
57. 1 2 + 3 4 - 5 - 6 7 * * 8 * 9 + -
58. 1 2 + 3 4 5 6 + * 7 8 + * 9 + * +
59. 1 2 3 4 - 5 - 6 * 7 * + 8 * 9 - -
60. 1 2 3 + - 4 5 + 6 / 7 8 * 9 * - *
61. 1 2 3 / * 4 5 6 7 8 * * - - 9 * *
62. 1 2 3 4 5 6 / 7 - * - 8 * + 9 * *
63. 1 2 3 4 5 + - 6 * 7 * 8 * - + 9 -
64. 1 2 3 4 - 5 - 6 7 * * 8 * 9 + - +
65. 1 2 3 / * 4 5 - 6 7 * 8 * + 9 * *
66. 1 2 3 4 5 + 6 * 7 * 8 * 9 - / / *
67. 1 2 * 3 4 5 - 6 7 8 * * + / 9 / /
68. 1 2 * 3 / 4 5 6 7 8 * * - - * 9 *
69. 1 2 3 4 5 + - 6 * 7 * + 8 * - 9 +
70. 1 2 3 4 - 5 - 6 7 * * 8 * - + 9 -
71. 1 2 * 3 * 4 5 6 * 7 8 * + * 9 - *
72. 1 2 * 3 / 4 5 - 6 7 * 8 * + * 9 *
73. 1 2 3 4 5 - 6 7 8 * * + / / * 9 *
74. 1 2 3 4 5 + - 6 7 * 8 * * 9 + - +
75. 1 2 * 3 / 4 5 + 6 * 7 8 * * 9 - *
76. 1 2 * 3 4 5 6 7 * 8 * - - / 9 / /
77. 1 2 * 3 4 5 + 6 7 8 * * * 9 - / /
78. 1 2 3 4 5 + - 6 7 8 * * * 9 + - +
79. 1 2 3 4 5 + - 6 7 * * 8 * - 9 - +
80. 1 2 * 3 4 5 + 6 * 7 * 8 * 9 - / /
81. 1 2 + 3 4 5 6 7 8 * - - * + 9 * +
82. 1 2 * 3 / 4 5 + 6 7 8 * * * 9 - *
83. 1 2 3 4 5 + - 6 7 * 8 * * - + 9 -
84. 1 2 3 4 - 5 - 6 * 7 8 * * 9 + - +
85. 1 2 3 * 4 5 6 * 7 8 * + * 9 - * *
86. 1 2 + 3 4 5 + - 6 7 * 8 * * - 9 -
87. 1 2 + 3 + 4 5 6 * 7 8 * + * 9 - *
88. 1 2 3 / 4 5 6 7 8 * * - - 9 * * *
89. 1 2 + 3 4 5 + - 6 * 7 * 8 * - 9 -
90. 1 2 3 / 4 5 + 6 * 7 8 * * 9 - * *
91. 1 2 3 / 4 5 6 7 * 8 * - - * * 9 *
92. 1 2 3 4 5 6 7 8 * * - - 9 * / / *
93. 1 2 3 4 5 6 + * * 7 - 8 * * 9 + +
94. 1 2 3 4 5 + - 6 7 8 * * * - + 9 -
95. 1 2 3 4 - 5 - 6 * 7 * 8 * - 9 - +
96. 1 2 + 3 4 5 + - 6 7 8 * * * 9 + -
97. 1 2 * 3 / 4 5 6 7 * 8 * - - * 9 *
98. 1 2 + 3 4 5 6 7 * 8 + + * + 9 * +
99. 1 2 * 3 4 5 - 6 7 * 8 * + / 9 / /
100. 1 2 + 3 4 - 5 - 6 7 * 8 * * - 9 -
101. 1 2 3 4 5 - 6 7 8 * * + 9 * / / *
102. 1 2 3 4 5 - 6 7 * 8 * + / / 9 * *
103. 1 2 3 4 - 5 - 6 * 7 8 * * - + 9 -
104. 1 2 3 + + 4 5 6 * 7 8 * + * 9 - *
105. 1 2 + 3 4 - 5 - 6 7 8 * * * 9 + -
106. 1 2 3 4 5 6 7 8 * * - - / / * 9 *
107. 1 2 3 4 5 6 - 7 8 * + * + 9 * + +
108. 1 2 3 4 5 - 6 7 * 8 * + / 9 / / *
109. 1 2 3 / 4 5 - 6 7 * 8 * + * * 9 *
110. 1 2 3 / * 4 5 - 6 7 * 8 * + * 9 *
111. 1 2 3 4 5 6 7 * 8 * - - / / 9 * *
112. 1 2 3 4 * 5 6 + * 7 - * 8 * + 9 +
113. 1 2 3 / * 4 5 + 6 * 7 8 * * 9 - *
114. 1 2 3 / 4 5 - 6 7 8 * * + * * 9 *
115. 1 2 * 3 4 5 + 6 7 * 8 * * 9 - / /
116. 1 2 3 4 5 6 7 * 8 * - - / 9 / / *
117. 1 2 3 / * 4 5 + 6 7 8 * * * 9 - *
118. 1 2 * 3 4 5 - 6 7 8 * * + 9 * / /
119. 1 2 3 / 4 5 6 7 8 * * - - * 9 * *
120. 1 2 3 4 + * + 5 6 - 7 8 + 9 * + *
121. 1 2 3 4 - 5 - 6 7 * 8 * * - 9 - +
122. 1 2 + 3 4 5 + - 6 * 7 8 * * 9 + -
123. 1 2 3 4 - 5 - 6 7 8 * * * - 9 - +
124. 1 2 3 / * 4 5 6 7 * 8 * - - * 9 *
125. 1 2 * 3 4 5 6 7 * 8 * - - 9 * / /
126. 1 2 3 4 5 6 7 8 * - - * + 9 * + +
127. 1 2 3 4 5 6 / 7 8 * + * - + - 9 *
128. 1 2 3 4 5 6 + * 7 8 + * 9 + * + +
129. 1 2 3 4 5 + 6 7 8 * * * 9 - / / *
130. 1 2 3 4 5 + - 6 7 * * 8 * 9 + - +
131. 1 2 + 3 4 - 5 - 6 * 7 * 8 * - 9 -
132. 1 2 3 / * 4 5 6 7 8 * * - - * 9 *
133. 1 2 + 3 4 - 5 - 6 * 7 8 * * 9 + -
134. 1 2 * 3 4 5 6 / 7 - * - 8 * + 9 *
135. 1 2 3 4 5 6 / 7 - * - 8 * + * 9 *
136. 1 2 * 3 / 4 5 + 6 7 * 8 * * 9 - *
137. 1 2 * 3 4 5 - 6 7 8 * * + / / 9 *
138. 1 2 * 3 / 4 5 - 6 7 8 * * + 9 * *
139. 1 2 3 4 5 + * 6 + 7 * 8 - 9 * + +
140. 1 2 3 4 5 + - 6 7 * * 8 * - + 9 -
141. 1 2 3 4 5 + - 6 * 7 8 * * - 9 - +
142. 1 2 3 / 4 5 + 6 * 7 * 8 * 9 - * *
143. 1 2 * 3 / 4 5 + 6 * 7 * 8 * 9 - *
144. 1 2 * 3 4 5 6 * 7 8 * + * 9 - * *
145. 1 2 * 3 4 5 6 7 * 8 * - - / / 9 *
146. 1 2 + 3 4 5 6 + 7 8 + * * 9 + * +
147. 1 2 3 4 - 5 - 6 * 7 * 8 * 9 + - +
148. 1 2 + 3 4 5 + - 6 7 * 8 * * 9 + -
149. 1 2 * 3 4 5 - 6 7 * 8 * + 9 * / /
150. 1 2 3 4 5 6 7 * + 8 + * + 9 * + +
151. 1 2 3 4 5 + - 6 7 * * + 8 * - 9 +
152. 1 2 + 3 4 5 + - 6 7 * * 8 * - 9 -
153. 1 2 3 4 5 6 + * * 7 - 8 * * + 9 +
154. 1 2 3 4 5 6 + * * 7 - * 8 * 9 + +
155. 1 2 3 4 - 5 - 6 * 7 * 8 * - + 9 -
156. 1 2 + 3 4 - 5 - 6 7 * * 8 * - 9 -
157. 1 2 3 4 5 + - 6 * 7 * + 8 * 9 - -
158. 1 2 3 4 * + + 5 6 - 7 8 + 9 * + *
159. 1 2 * 3 4 5 + 6 7 * * 8 * 9 - / /
160. 1 2 3 4 5 6 7 * 8 * - - 9 * / / *
161. 1 2 3 4 5 6 + 7 8 + * * 9 + * + +
162. 1 2 3 4 - 5 - 6 7 * 8 * * 9 + - +
163. 1 2 3 / * 4 5 - 6 7 8 * * + 9 * *
164. 1 2 3 / 4 5 + 6 7 * 8 * * 9 - * *
165. 1 2 3 4 - 5 - 6 * 7 * + 8 * - 9 +
166. 1 2 3 / * 4 5 + 6 7 * 8 * * 9 - *
167. 1 2 * 3 4 5 - 6 7 * 8 * + / / 9 *
168. 1 2 3 4 5 - 6 7 * 8 * + / / * 9 *
169. 1 2 3 4 - 5 - 6 7 8 * * * 9 + - +
170. 1 2 3 4 - 5 - 6 7 * * 8 * - 9 - +
171. 1 2 3 4 - 5 - 6 7 * * + 8 * 9 - -
172. 1 2 3 4 + * + 5 6 7 8 + 9 * - - *
173. 1 2 3 / 4 5 + 6 7 8 * * * 9 - * *
174. 1 2 3 4 * 5 6 + * 7 - 8 * * 9 + +
175. 1 2 3 4 - 5 - 6 7 * 8 * * - + 9 -
176. 1 2 * 3 4 5 6 7 8 * * - - / 9 / /
177. 1 2 3 4 5 6 7 * 8 * - - / / * 9 *
178. 1 2 3 4 - 5 - 6 7 8 * * * - + 9 -
179. 1 2 3 / 4 5 6 7 * 8 * - - 9 * * *
180. 1 2 + 3 4 5 + - 6 * 7 * 8 * 9 + -
181. 1 2 - 3 - 4 5 + 6 / 7 8 9 * * - *
182. 1 2 - 3 - 4 5 6 / 7 8 * + * + 9 *
183. 1 2 3 / 4 5 6 7 8 * * - - * * 9 *
184. 1 2 * 3 / 4 5 6 7 8 * * - - 9 * *
185. 1 2 + 3 4 * + 5 6 - 7 8 + 9 * + *
186. 1 2 + 3 4 - 5 - 6 7 * 8 * * 9 + -

たくさん ある なかで とくに

1 2 3 4 5 6 7 8 * * - - / / 9 * *

は いんしょうてき。1 から 8 まで いっきに ならべられるのも すごいし、たしざんを つかってないのも いい。おぼえやすい。

つぎは これを infix notation に へんかん。うえの しき だと、RPN を しらない ひとには 自慢 できないし。

ちなみに、演算を 全部 かっこで くくる、みたいに して へんかん すると うまく いかない。

たとえば 1 2 + 3 + と 1 2 3 + + は、それぞれ infix notation に へんかん すると ((1 + 2) + 3) と (1 + (2 + 3)) に なって、かっこを てんかい すれば まったく おなじ しきに なる。

なので、たしざんには かっこを つけない、ひきざんは a - b の b に + か - が はいっていたら a - (b) に する、などの 処理を しながら へんかん していく。ちょっと 注意が 必要。

というわけで、へんかんの けっかは いかの 48 とおり。

1. 1 * 2 / (3 / ((4 + 5) * 6 * 7 * 8 - 9))
2. 1 * (2 / (3 / ((4 + 5) * 6 * 7 * 8 - 9)))
3. 1 + 2 + (3 + 4 * (5 - (6 - 7 * 8))) * 9
4. (1 - (2 + 3 - 4 * (5 / 6 + 7 * 8))) * 9
5. 1 * (2 / ((3 / (4 - (5 - 6 * 7 * 8))) / 9))
6. (1 - 2 - (3 - 4 * (5 / 6 + 7 * 8))) * 9
7. 1 * (2 / (3 / ((4 - 5 + 6 * 7 * 8) * 9)))
8. 1 + 2 + 3 * (4 * (5 + 6) * (7 + 8) + 9)
9. (1 - (2 + 3)) * ((4 + 5) / 6 - 7 * 8 * 9)
10. 1 * (2 / 3) * (4 - (5 - 6 * 7 * 8)) * 9
11. 1 * (2 / 3) * ((4 + 5) * 6 * 7 * 8 - 9)
12. 1 * 2 * 3 * (4 * (5 * 6 + 7 * 8) - 9)
13. (1 - (2 + 3) + 4 * (5 / 6 + 7 * 8)) * 9
14. 1 * (2 / (3 / (4 - (5 - 6 * 7 * 8)))) * 9
15. 1 + 2 * (3 * 4 * (5 + 6) - 7) * 8 + 9
16. (1 * 2 / (3 / (4 - 5 + 6 * 7 * 8))) * 9
17. (1 * 2 + (3 - 4 * (5 / 6 - 7)) * 8) * 9
18. 1 - ((2 + (3 - 4 - 5) * 6 * 7) * 8 - 9)
19. 1 * (2 / (3 / (4 - 5 + 6 * 7 * 8))) * 9
20. 1 + 2 + (3 + 4 * (5 + 6 * 7 + 8)) * 9
21. (1 + 2 + 3 * 4) * (5 - 6 + (7 + 8) * 9)
22. 1 * (2 / (3 / ((4 - (5 - 6 * 7 * 8)) * 9)))
23. 1 * (2 + (3 - 4 * (5 / 6 - 7)) * 8) * 9
24. 1 * 2 / (3 / ((4 - (5 - 6 * 7 * 8)) * 9))
25. (1 + 2 + 3 * 4) * (5 - (6 - (7 + 8) * 9))
26. (1 * 2 / 3) * ((4 + 5) * 6 * 7 * 8 - 9)
27. (1 + 2 * (3 + 4)) * (5 - 6 + (7 + 8) * 9)
28. 1 * 2 / ((3 / (4 - 5 + 6 * 7 * 8)) / 9)
29. 1 + 2 + ((3 * (4 + 5) + 6) * 7 - 8) * 9
30. 1 + 2 + (3 + 4 * (5 - 6 + 7 * 8)) * 9
31. 1 * (2 / 3) * (4 - 5 + 6 * 7 * 8) * 9
32. 1 + 2 - ((3 - (4 + 5)) * 6 * 7 * 8 + 9)
33. 1 + 2 - (3 - (4 + 5)) * 6 * 7 * 8 - 9
34. 1 - (2 + (3 - (4 + 5)) * 6 * 7) * 8 + 9
35. (1 * 2 / (3 / (4 - (5 - 6 * 7 * 8)))) * 9
36. (1 - 2 - 3 + 4 * (5 / 6 + 7 * 8)) * 9
37. (1 + 2 + 3) * (4 * (5 * 6 + 7 * 8) - 9)
38. 1 - ((2 + (3 - (4 + 5)) * 6 * 7) * 8 - 9)
39. 1 * (2 / ((3 / (4 - 5 + 6 * 7 * 8)) / 9))
40. (1 + 2 * (3 + 4)) * (5 - (6 - (7 + 8) * 9))
41. 1 * 2 / (3 / ((4 - 5 + 6 * 7 * 8) * 9))
42. 1 * 2 / ((3 / (4 - (5 - 6 * 7 * 8))) / 9)
43. 1 + 2 - (3 - 4 - 5) * 6 * 7 * 8 - 9
44. (1 * 2 / 3) * (4 - (5 - 6 * 7 * 8)) * 9
45. 1 - (2 + (3 - 4 - 5) * 6 * 7) * 8 + 9
46. (1 - 2 - 3) * ((4 + 5) / 6 - 7 * 8 * 9)
47. (1 * 2 / 3) * (4 - 5 + 6 * 7 * 8) * 9
48. 1 + 2 - ((3 - 4 - 5) * 6 * 7 * 8 + 9)

ふつうの しきは Google で かんたんに 確認 できるのが べんり。RPN も けいさんの けっかを 確認 できるように するべき だろうか。

この なかでは、やはり Knuth せんせいの ケーキに えらばれた

1 + 2 + 3 * (4 * (5 + 6) * (7 + 8) + 9)

が いちばん いんしょうてき。たしざんと かけざん しか つかってない。

たしざんと かけざん だけの しき は、もう ひとつ

1 + 2 + (3 + 4 * (5 + 6 * 7 + 8)) * 9

が あるけれど、こちらは 8の うしろに かっこが ふたつ 連続で ならぶ のが うつくしくない。

って、しゅんは とっくに すぎてる 話題 だけれど、今年は まだ なにも かいてなかったので、とりあえず、こんな かんじで スタートを きっておきます。文句が あったら "@n (cont)" あてに twitlonger けいゆで 連絡 ください。さくっと block します。わ