Inspired by this question on Math.SE.
Starting with 1
you can repeatedly perform one of the following two operations:
Double the number.
or
Rearrange its digits in any way you want, except that there must not be any leading zeroes.
Taking an example from the linked Math.SE post, we can reach 1000
via the following steps:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 125, 250, 500, 1000
Which numbers can you reach with this process and what is the shortest solution?
The Challenge
Given a positive integer N
, determine the shortest possible sequence of integers to reach N
with the above process, if possible. If there are several optimal solutions, output any one of them. If no such sequence exists, you should output an empty list.
The sequence may be in any convenient, unambiguous string or list format.
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.
This is code golf, so the shortest answer (in bytes) wins.
Test Cases
Here is a list of all reachable numbers up to and including 256. The first column is the number (your input), the second column is the optimal number of steps (which you can use to check the validity of your solution) and the third column is one optimal sequence to get there:
1 1 {1}
2 2 {1,2}
4 3 {1,2,4}
8 4 {1,2,4,8}
16 5 {1,2,4,8,16}
23 7 {1,2,4,8,16,32,23}
29 10 {1,2,4,8,16,32,23,46,92,29}
32 6 {1,2,4,8,16,32}
46 8 {1,2,4,8,16,32,23,46}
58 11 {1,2,4,8,16,32,23,46,92,29,58}
61 6 {1,2,4,8,16,61}
64 7 {1,2,4,8,16,32,64}
85 12 {1,2,4,8,16,32,23,46,92,29,58,85}
92 9 {1,2,4,8,16,32,23,46,92}
104 15 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104}
106 14 {1,2,4,8,16,32,64,128,256,265,530,305,610,106}
107 14 {1,2,4,8,16,32,23,46,92,29,58,85,170,107}
109 18 {1,2,4,8,16,32,23,46,92,184,368,386,772,277,554,455,910,109}
116 12 {1,2,4,8,16,32,23,46,92,29,58,116}
122 7 {1,2,4,8,16,61,122}
124 16 {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,124}
125 11 {1,2,4,8,16,32,64,128,256,512,125}
128 8 {1,2,4,8,16,32,64,128}
136 18 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,136}
140 15 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,140}
142 16 {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,142}
145 17 {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,145}
146 18 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,146}
148 11 {1,2,4,8,16,32,23,46,92,184,148}
149 16 {1,2,4,8,16,32,64,128,182,364,728,287,574,457,914,149}
152 11 {1,2,4,8,16,32,64,128,256,512,152}
154 17 {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154}
158 16 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158}
160 14 {1,2,4,8,16,32,64,128,256,265,530,305,610,160}
161 13 {1,2,4,8,16,32,23,46,92,29,58,116,161}
163 18 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,163}
164 18 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,164}
166 20 {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166}
167 17 {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,167}
169 23 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229,458,916,169}
170 13 {1,2,4,8,16,32,23,46,92,29,58,85,170}
176 17 {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176}
182 9 {1,2,4,8,16,32,64,128,182}
184 10 {1,2,4,8,16,32,23,46,92,184}
185 16 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,185}
188 23 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,185,370,740,470,940,409,818,188}
190 18 {1,2,4,8,16,32,23,46,92,184,368,386,772,277,554,455,910,190}
194 16 {1,2,4,8,16,32,64,128,182,364,728,287,574,457,914,194}
196 23 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229,458,916,196}
203 16 {1,2,4,8,16,32,64,128,256,265,530,305,610,160,320,203}
205 13 {1,2,4,8,16,32,64,128,256,512,125,250,205}
208 16 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208}
209 19 {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,145,290,209}
212 8 {1,2,4,8,16,61,122,212}
214 15 {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214}
215 11 {1,2,4,8,16,32,64,128,256,512,215}
218 9 {1,2,4,8,16,32,64,128,218}
221 8 {1,2,4,8,16,61,122,221}
223 14 {1,2,4,8,16,32,23,46,92,29,58,116,232,223}
227 20 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,361,722,227}
229 20 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,461,922,229}
230 16 {1,2,4,8,16,32,64,128,256,265,530,305,610,160,320,230}
232 13 {1,2,4,8,16,32,23,46,92,29,58,116,232}
233 22 {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166,332,233}
235 19 {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176,352,235}
236 19 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,632,236}
238 19 {1,2,4,8,16,32,64,128,256,512,125,250,205,410,104,208,416,832,238}
239 25 {1,2,4,8,16,32,23,46,92,184,368,736,376,752,257,514,154,308,616,166,332,233,466,932,239}
241 16 {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,241}
244 8 {1,2,4,8,16,61,122,244}
247 21 {1,2,4,8,16,32,23,46,92,184,148,296,592,259,518,158,316,632,362,724,247}
248 17 {1,2,4,8,16,32,23,46,92,29,58,85,170,107,214,124,248}
250 12 {1,2,4,8,16,32,64,128,256,512,125,250}
251 11 {1,2,4,8,16,32,64,128,256,512,251}
253 19 {1,2,4,8,16,32,23,46,92,184,148,296,269,538,358,716,176,352,253}
256 9 {1,2,4,8,16,32,64,128,256}
If you want even more test data, here is the same table up to and including 1,000.
Any number not appearing on these tables should yield an empty list (provided the number is in the range of the table).