99 lines
1.9 KiB
Python
99 lines
1.9 KiB
Python
from math import log
|
|
from sys import argv
|
|
|
|
|
|
fib = [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903]
|
|
|
|
|
|
def sqrs(x):
|
|
out = ''
|
|
while x > 0:
|
|
out += chr(ord('0') + x % 2)
|
|
x /= 2
|
|
if len(out) <= 1: return 1
|
|
outnum = 1
|
|
for i in xrange(1, len(out)):
|
|
if out[i] == out[i - 1] == '1':
|
|
outnum *= -1
|
|
return outnum
|
|
|
|
'''
|
|
def trace(x, n):
|
|
bale = 0
|
|
print '%12s' % bin(x)[2:],
|
|
for i in xrange(1, n + 1):
|
|
bale += sqrs(x + i)
|
|
if bale == 0:
|
|
print '%4d' % i,
|
|
break
|
|
|
|
|
|
for kk in xrange(10):
|
|
trace(2 ** kk + int(argv[1]), 1000)
|
|
print
|
|
'''
|
|
'''
|
|
a = 0
|
|
for i in xrange(10000):
|
|
a += sqrs(i)
|
|
print a,
|
|
'''
|
|
|
|
def listsr(x):
|
|
out = [1]
|
|
for i in xrange(x):
|
|
out.append(out[i] + sqrs(i + 1))
|
|
return out
|
|
|
|
|
|
def sqs(lis):
|
|
dic = {}
|
|
for i in xrange(len(lis)):
|
|
tmp = lis[i]
|
|
if dic.keys().count(tmp) == 0:
|
|
dic.update({tmp: [i]})
|
|
else:
|
|
dic.get(tmp).append(i)
|
|
return dic
|
|
|
|
|
|
|
|
|
|
|
|
def log2(x):
|
|
return int(log(x)/log(2))
|
|
|
|
|
|
def first(x):
|
|
if x == 0:
|
|
return 0
|
|
minus = 0
|
|
if x & 1 == 0:
|
|
tmp = 1
|
|
while x & tmp == 0:
|
|
tmp *= 2
|
|
else:
|
|
minus = ((4 ** log2(tmp) - 1) / 3 + 1) / 2
|
|
x += 1
|
|
length = log2(x)
|
|
value = 4 ** length / 2
|
|
can = 2 ** length + 1 # 1000...0001
|
|
for i in xrange(1, length):
|
|
bar = 2 ** i
|
|
if (bar & can) != (bar & x):
|
|
value += 4 ** i / 2
|
|
return value - minus
|
|
|
|
|
|
lis = listsr(50000)
|
|
#print lis
|
|
a = sqs(lis)
|
|
a.pop(1)
|
|
for item in a.keys():
|
|
tmp = a.get(item)[0]
|
|
for i in xrange(len(a.get(item))):
|
|
a.get(item)[i] -= tmp
|
|
#print item, '\t', '%8s' % bin(tmp)[2:], '\t', a.get(item)
|
|
print '%10s' % bin(item)[2:], '%6d' % first(item), '%7d' % a.get(item)[-1], '%8d' % ((first(item) + a.get(item)[-1]) / 2), a.get(item)[(item + 1) / 2]
|
|
|