コラッツ問題を簡単にといてみた。

コラッツの問題 - Wikipedia

#!/usr/bin/env python2.7
# -*- coding: utf-8 -*-

def Collatz(x):
    result = [x]
    while not x == 1:
        if x % 2 == 0:
            x = x/2
        else:
            x = x*3+1
        result.append(x)
    return result

max_num = 1
max_times = 0
for item in range(1,100000):
    res = Collatz(item)
    if max_times < len(res):
        max_num = item
        max_times = len(res)
        print item, len(res)

print "MAX : ", max_num, max_times

% python2.7  collatz.py
1 1
2 2
3 8
6 9
7 17
9 20
18 21
25 24
27 112
54 113
73 116
97 119
129 122
171 125
231 128
313 131
327 144
649 145
703 171
871 179
1161 182
2223 183
2463 209
2919 217
3711 238
6171 262
10971 268
13255 276
17647 279
23529 282
26623 308
34239 311
35655 324
52527 340
77031 351
MAX :  77031 351

Googleの入社試験(非公式)にチャレンジしてみた。

[非公認] Googleの入社試験

問題1
整数nが与えられたとき、0からnまでのすべての数を書くのに必要とされる｢1｣の数を
返す関数がある。例えば、f(13)=6になる。また、f(1)=1に注意。
f(n)=nとなるような、2番目に大きいnを求めなさい。

ソースコード。

#!/usr/bin/env python
# -*- coding:utf-8 -*-

def count_one(x):
    """ x を記述するのに必要な１の数をカウントする
    """
    num = 0 #val of 1
    for c in str(x):
        if(c=="1"): #文字列扱いのための2重引用符
            num +=1
    return num

def check_num2(x):
    counts = 1
    i = 1
    while(i <= x):
        i+=1
        counts += count_one(i)
        if counts == i:
            print "matchng:",i
    return counts

if __name__=="__main__":
    print check_num2(1000000) #8桁までで一致する場合

計算実行。

% python2.7 google.py           
matchng: 199981
matchng: 199982
matchng: 199983
matchng: 199984
matchng: 199985
matchng: 199986
matchng: 199987
matchng: 199988
matchng: 199989
matchng: 199990
matchng: 200000
matchng: 200001
600003

@see:
@see: Googleの入社試験(非公式)にチャレンジしてみた | Yasigani-ni Blog