"What is the exponent of the largest power of two whose base seven representation doesn't contain three zeros in a row?"

 

import timeit

 

def ConvDecToBaseSevenInt(num):

    ans = 0

    pow = 0

    if num == 0:

        return 0

    else:

        while num != 0:

            num, rem = divmod(num, 7)

            ans = rem*10**pow+ans

            pow += 1

    return ans

 

def ConvDecToBaseSeven(num):

    ans = ''

    if num == 0:

        return '0'

    else:

        while num != 0:

            num, rem = divmod(num, 7)

            ans = str(rem)+ans

    return ans

 

def ConvDecToBaseVar(num, base):

    if base > 10 or base < 2:

        raise ValueError, 'The base number must be between 2 and 10.'

    if num < 2: return str(num)

    ans = ''

    while num != 0:

        num, rem = divmod(num, base)

        ans = str(rem)+ans

    return ans

 

def ConvDecToBaseVar1(num, base):

    if base > 10 or base < 2:

        raise ValueError, 'The base number must be between 2 and 10.'

    if num == 0: return ''

    num, rem = divmod(num, base)

    return ConvDecToBaseVar1(num, base)+str(rem)

 

def ConvDecToBaseVar2(num, base):

    if base > 16 or base < 2:

        raise ValueError, 'The base number must be between 2 and 16.'

    dd = dict(zip(range(16), [str(i) for i in range(10)]+['A', 'B', 'C', 'D', 'E', 'F']))

    if num == 0: return ''

    num, rem = divmod(num, base)

    return ConvDecToBaseVar2(num, base)+dd[rem]

 

def ConvDecToBaseVar3(num, base, dd=False):

    if base > 16 or base < 2:

        raise ValueError, 'The base number must be between 2 and 16.'

    if not dd:

        dd = dict(zip(range(16), [hex(i).split('x')[1] for i in range(16)]))

    if num == 0: return ''

    num, rem = divmod(num, base)

    return ConvDecToBaseVar3(num, base, dd)+dd[rem]

 

def ConvDecToBaseVar4(num, base):

    if num < 2: return str(num)

    if base > 16 or base < 2:

        raise ValueError, 'The base number must be between 2 and 16.'

    dd = dict(zip(range(16), [hex(i).split('x')[1] for i in range(16)]))

    ans = ''

    while num != 0:

        num, rem = divmod(num, base)

        ans =  dd[rem]+ans

    return ans

'''

>>> ConvDecToBaseVar3(99887766554433221100,11)

'16a69378811311206610'

>>> ConvDecToBaseVar4(99887766554433221100,11)

'16a69378811311206610'

>>>

'''

 

if __name__ == '__main__':

    # recursion

    t = timeit.Timer("ConvDecToBaseVar3(2**2750,12)", "from __main__ import ConvDecToBaseVar3")

    print t.timeit(100)

    # no recursion

    t = timeit.Timer("ConvDecToBaseVar4(2**2750,12)", "from __main__ import ConvDecToBaseVar4")

    print t.timeit(100)

 

def print_binary1(decimal_string):

    if decimal_string == 0:

        return ''

    bStr = str(decimal_string % 2)

    decimal_string = decimal_string >> 1

    return print_binary1(decimal_string)+bStr

 

       

'''

# recursion

t = timeit.Timer("ConvDecToBaseVar3(2**2750,12)", "from __main__ import ConvDecToBaseVar3")

print t.timeit(100)

# no recursion

t = timeit.Timer("ConvDecToBaseVar4(2**2750,12)", "from __main__ import ConvDecToBaseVar4")

print t.timeit(100)

>>> 0.537926747673

0.37232804728

>>>

'''

 

'''

>>> ConvDecToBaseVar(3000,2)

'101110111000'

>>>

'''

 

def solve_test1(max):

    for i in xrange(max, 0, -1):

        if '000' not in ConvDecToBaseVar3(2**i, 7):

            return i

        else:

            print 'Checked power %s, FAILED TEST' % (i)

 

def solve_test2(maxFail):

    fail = 0

    i = 1

    while fail < maxFail:

        if '000' not in ConvDecToBaseVar(2**i, 7):

            fail = 0

            max_exp = i

            print max_exp

        else:

            fail += 1

        i += 1

    return max_exp

       

'''

>>> powers_of_two(10000)

Checked power 10000, FAILED TEST

Checked power 9999, FAILED TEST

Checked power 9998, FAILED TEST

...............................

8833

>>>

'''

 

'''

>>> powers_of_two(20000)

Checked power 20000, FAILED TEST

Checked power 19999, FAILED TEST

Checked power 19998, FAILED TEST

...............................

Checked power 8837, FAILED TEST

Checked power 8836, FAILED TEST

Checked power 8835, FAILED TEST

Checked power 8834, FAILED TEST

8833

>>>

'''

 

'''

>>> base_seven(2**58)

'3420001503236101664320'

>>> solve_test(100)

1

2

3

4

5

6

7

8

9

10

11

12

...........

4865

4899

4900

5048

5258

5617

5667

6140

6160

6592

7458

8191

8833

>>>

'''