StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h3>Edit: This approach misses the eleven-non-free number 1011 for example. I know what's wrong and will fix it, but can't do it now.</h3> <p>Let's take a principled approach that builds up to the solution rather than trying to handle it all at once.</p> <p>Let S be the sequence of powers of 11:</p> <p>11, 121, 1331, 14641, 161051, ...</p> <p>Let E(n) be the set of numbers that contain the string representation of n as a substring. The set you are looking for is the union of E(n) over n in S.</p> <p>How do we generate the elements of E(n) for some n? (Let's take n = 121 for example.)</p> <p>Make a directed acyclic graph where n is the root node. Make n point to all 19 of the following numbers:</p> <p>Append 0-9: n0 n1 n2 n3 n4 n5 n6 n7 n8 n9<br> Prepend 1-9: 1n 2n 3n 4n 5n 6n 7n 8n 9n</p> <p>Repeat the process for each of these new nodes. Notice that certain nodes may end up with more than one parent, so you'll want to maintain a hashmap from number to node pointer. (You can get to 71217 by 121 -> 1217 -> 71217 or 121 -> 7121 -> 71217.)</p> <p>This graph has the property that, for any edge from u to v, we have u < v. This is important because it means we can generate the elements of E(n) in increasing order by doing a breadth-first generation of the graph, always expanding the unexpanded node with smallest number.</p> <p>Now merge these graphs for all n in S.</p> <p>You have one large directed acyclic graph (that is infinite) that you can generate in a breadth-first manner, always expanding the unexpanded node with smallest number, emitting the next (kth) eleven-non-free number.</p> <h1>Pseudocode</h1> <p><em>It works, I tested it. Here's a C# gist: <a href="https://gist.github.com/timothy-shields/8026924" rel="nofollow">https://gist.github.com/timothy-shields/8026924</a></em></p> <pre><code>procedure generate_eleven_non_free i = 1 n = 11^i //frontier nodes; F.insert(x) does nothing if x already in F F = empty-min-heap-set while (true) { if (F.empty() or F.min() > n) { F.insert(n) i = i + 1 n = 11^i } else { m = F.extractmin() yield m for j = 0:9 F.insert(append(m,j)) for j = 1:9 F.insert(append(j,m)) } } </code></pre> <p>To get the kth eleven-non-free number, simply do something like generate_eleven_non_free().element_at(k), where this is supposed to pick out the kth yielded number.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload