Specifically for coldtortuga

[pmb]

A variation on a previous theme:

Base	Number	Number in Base 10
2	12	1
3	23	2
4	3124	54
5	4135	108
6	4126	152
7	651427	16200
8	76251348	2042460
9	82715369	4416720
10	986731210	9867312
Still churning - these O(nn) algorithms really soak up the CPU time... (I later hit Ctrl-C, so all numbers after this point are from coldtortuga)
11	A9876241311	2334364200
12	B935217612	421877610
13	CBA9584721313	1779700673520

Comments

[pmb.livejournal.com]

Totally could. (actually, $O(\sum_{i=0}^n {(n choose i) * i!})$ which I think is still O(n!), but I'm not entirely sure... That would make a good intro to algorithms and data structures question.)

Try all permutations of n letters, in reverse lexicographic order, then all permutations of all size n-1 subsets in some appropriate order. The only issue is coding all of that up. The reverse lexicographic order thing isn't too bad, but doing all of the subsets and pulling off the next candidate in the right order is a tricky bit of combinatorial coding that I would prefer to avoid. Using some heuristics, coldtortuga was able to get the base 10 case down to 10 seconds of searching, but I don't know if his techniques generalize to other bases.

I suppose one could make a heap of generators that would yield the front of the lowest generator on the heap. In the worst case there would be O(n!) generators, but that's only O(n lg n) to pull the top one off the heap, and the answer would probably be found before the heap got to be too large. That would be memory intensive, but not too bad otherwise. Heapification is pretty quick... I bet I could use this technique to find the sequence up to base 14, maybe!

But it sounds like a whole lot of work for just 4 more terms. I prefer to throw CPU at the problem and then walk away if that doesn't suffice. Optimizing non-polynomial algorithms just isn't very fun. Finding a polynomial algorithm is, and so is proving a problem impossible. But I don't see how this problem is NP complete (it seems over-specified, which makes reductions difficult), it doesn't seem like it has a polynomial solution, and number theory was always my most dicey section in discrete math.

[mycrust.livejournal.com]

Yeah, this problem has the flavor of something that someone clever could find a way to speed up dramatically by reducing the search space using some generalized facts about divisibility. I am not capable of doing that though. And the answer is kind of cooler than the method anyway.

[coldtortuga.livejournal.com]

My "heuristic" approach pretty much follows the algorithm described by pmb, which is (as ya'll surmise) O(n!).

In base n, start with the set of usable digits D={1, ..., n-1}. For each non-empty subset d of D (in Gray-code order, 'cause I already had a Gray-code subset generator), I find and test all the permutations of d (in the order given by Heaps' algorithm, 'cause I already had Heaps coded up). Gray-code + Heaps' algo does not the most efficient search-order make, but it's not too shabby.

The number of candidates to test in base n is given by A007526 which grows like e*n!