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

[chanusa.livejournal.com]

You should add this to the OEIS! They love new interesting sequences
http://www.research.att.com/~njas/sequences/

[pmb.livejournal.com]

I thought that a sequence had to be published in a research result. How would I go about adding this sequence?

[(Anonymous)]

Your sequence doesn't need to be published; it just has to be a sequence of interest.
From the homepage, choose submit a sequence; it takes you to the following page:
http://www.research.att.com/~njas/sequences/Submit.html
After that, it's fairly self-explanatory.
Just make sure your explanation is clear so that others could replicate your work.
Be sure to check the "hard" box at the bottom since it is a hard sequence to calculate (computationally).
Then you'll have your own A number!
Good luck. If you'd like to run your submission past me first, feel free.

[mycrust.livejournal.com]

Hmm, can't you do it in O(n!)? Not that that's fast, exactly...

[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!

[coldtortuga.livejournal.com]

Cool! That's a neat generalization :-)

(I'm just now catching up on lj after 2 weeks at my parents' home in Alaska. They only have internet connectivity via the phone line, e.g., "[ring ring ring] Hey Jen, are you near your mom's computer? Could you look up the World Cup groups and read them off to me, pretty pretty please??")

My code spat out the base-eleven answer in a few minutes (A98762413₁₁ = 2334364200₁₀) but it's been cranking for a couple hours now on base-twelve. The numbers are big enough to require Python "long" integers, which are waaaaay slower than native-hardware integers; I probably need a thorough re-writing of my generators to avoid so many multiplications and function-calls.

[coldtortuga.livejournal.com]

Somewhat disturbingly, my code reports B9352176₁₂ = 421877610₁₀ for base-twelve. Hmmmm... [taps teeth]

[pmb.livejournal.com]

Makes sense - you can't have a 0 as the final digit, which means that you can't have a multiple of 4 *and* a multiple of 3 in there, so either 4 and 8 are out or 3,6, and 9 are. Which means that you can have at most 9 digits. Why you can't have an A in there, I'm less sure, particularly since it is definitely divisible by A, as it is divisible by both 2 and 5.

[pmb.livejournal.com]

(note that the intuition I gave for 12 means that 13 will most likely be some friggin huge number, due to its primeness)

[coldtortuga.livejournal.com]

For base thirteen: CBA95847213₁₃ = 1779700673520₁₀. Good intuitin' :)

[conform.livejournal.com]

so josh and paul started on this today in haskell, hoping to take advantage of lazy evaluation in generating the descending seqence of possible answers. it's got a ways to go, but n=13 runs in 23 minutes on josh's 3GHz P4. n=12 is under a second! we're going to apply the beer optimization now and see where it gets us.