第17回オフラインリアルタイムどう書くの参考問題をPythonで実装

問題内容等についてはこちら。
http://nabetani.sakura.ne.jp/hena/ord17scheherazade/
http://qiita.com/Nabetani/items/dabe8ec57e0313229552

#!/usr/bin/env python
# -*- coding:utf8 -*-

def is_palindrome(data, base):
    digits = []
    while data > 0:
        digits.append(data % base)
        data /= base
    return digits == digits[::-1]

def solve(data):
    bases = [base for base in xrange(2, data) if is_palindrome(data, base)]
    return ','.join(map(str, bases)) if bases else '-'

def test(data, correct):
    answer = solve(int(data))
    print 'xo'[answer == correct], data, correct, answer

0, test( "17301", "5,38,100,218,236,5766,17300" );
1, test( "2", "-" );
2, test( "1", "-" );
3, test( "3", "2" );
4, test( "4", "3" );
5, test( "5", "2,4" );
6, test( "6", "5" );
7, test( "10", "3,4,9" );
8, test( "101", "10,100" );
9, test( "1001", "10,25,76,90,142,1000" );
10, test( "10001", "10,24,30,42,80,100,136,10000" );
11, test( "1212", "22,100,201,302,403,605,1211" );
12, test( "123412", "62,100,205,215,30852,61705,123411" );
13, test( "5179", "5178" );
14, test( "4919", "4918" );
15, test( "5791", "5790" );
16, test( "5498", "2748,5497" );
17, test( "453", "150,452" );
18, test( "134", "66,133" );
19, test( "8489", "27,652,8488" );
20, test( "1234", "22,616,1233" );
21, test( "5497", "41,238,5496" );
22, test( "4763", "19,35,432,4762" );
23, test( "3974", "17,27,1986,3973" );
24, test( "3521", "44,55,502,3520" );
25, test( "5513", "20,38,53,148,5512" );
26, test( "8042", "23,29,60,4020,8041" );
27, test( "7442", "37,60,121,3720,7441" );
28, test( "4857", "25,1618,4856" );
29, test( "22843", "49,69,91,141,430,22842" );
30, test( "194823", "84,121,21646,64940,194822" );
31, test( "435697", "160,169,235,626,1822,435696" );
32, test( "142", "3,7,70,141" );
33, test( "886", "5,14,442,885" );
34, test( "3102", "7,65,93,140,281,516,1033,1550,3101" );
35, test( "17326", "11,28,99,105,8662,17325" );
36, test( "32982", "13,72,238,477,716,1433,5496,10993,16490,32981" );
37, test( "36", "5,8,11,17,35" );
38, test( "37", "6,36" );
39, test( "251", "8,250" );
40, test( "252", "5,10,17,20,27,35,41,62,83,125,251" );
41, test( "253", "12,14,22,252" );
42, test( "6643", "2,3,9,81,90,510,948,6642" );
43, test( "5040", "71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039" );

出力結果からなんとなく法則性を見つけて、処理を高速化してみました。

def reverse(number, base):
    r = 0
    while number > 0:
        r = r * base + (number % base)
        number /= base
    return r

def solve(number):
    if number < 3: return '-'
    bases = []
    prev = 0
    for div in xrange(1, number):
        base = (number - 1) / div
        if base == 1 or base == prev: break
        if number == reverse(number, base): bases.append(base)
        prev = base
    for base in xrange(base - 1, 1, -1):
        if number == reverse(number, base): bases.append(base)
    return ','.join(map(str, bases[::-1]))

	実行時間
高速化前	2.122s
高速化後	0.255s

cielavenirさんのおかげで境目が √(number - 1) だと判明しましたので、高速化処理を整理してみました。
http://qiita.com/cielavenir/items/3d2bea62d301a2309884

def palindrome(number, base):
    forward, reverse = number, 0
    while number > 0:
        reverse = (reverse * base) + (number % base)
        number /= base
    return forward == reverse

def solve(number):
    if number < 3: return '-'
    pre = number - 1
    root = int(pre ** 0.5)
    bases = [base for base in xrange(2, pre / root) if palindrome(number, base)]
    bases += [pre / div for div in xrange(root, 0, -1) if palindrome(number, pre / div)]
    return ','.join(map(str, bases))