暴力方法不是为了解决问题,而是为了帮助研究。我正在研究一个Project Euler问题,这个问题要求我找到从X到小于Y的所有数字,这些数字中只有一个“子串”可以被数字的位数整除。在
这些被称为独生子女号码。104是一个独生子女号码。在它的子串[1,0,4,10,04,104]中,只有0可以被3整除。这个问题要求找出出现在10以下的独生子女数的数量。暴力方法不是正确的方法;但是,我有一个理论,要求我知道在10*11之前发生的一个孩子的数量。在
即使我把笔记本电脑开了半天,我也没能找到这个号码。我试过Cython,说我是一个对C一无所知的程序员,结果很糟糕。我甚至尝试过云计算,但是我的ssh管道总是在这个过程完成之前中断。在
如果有人能帮我找出一些不同的方法或优化来实现暴力 对于这个问题的解决方法到10**11,我们将不胜感激。在
请不要。。。在
请给我一些关于数论的建议或者你对这个问题的答案,因为我已经研究了很长时间了,我真的希望自己能得出结论。在
## a one child number has only one "substring" divisable by the
## number of digits in the number. Example: 104 is a one child number as 0
## is the only substring which 3 may divide, of the set [1,0,4,10,04,104]
## FYI one-child numbers are positive, so the number 0 is not one-child
from multiprocessing import Pool
import os.path
def OneChild(numRange): # hopefully(10*11,1)
OneChild = []
start = numRange[0]
number = numRange[1]
## top loop handles one number at a time
## loop ends when start become larger then end
while number >= start:
## preparing to analayze one number
## for exactly one divisableSubstrings
numberString = str(start)
numDigits = len(numberString)
divisableSubstrings = 0
ticker1,ticker2 = 0, numDigits
## ticker1 starts at 0 and ends at number of digits - 1
## ticker2 starts at number of digits and ends +1 from ticker1
## an example for a three digit number: (0,3) (0,2) (0,1) (1,3) (1,2) (2,3)
while ticker1 <= numDigits+1:
while ticker2 > ticker1:
if int(numberString[ticker1:ticker2]) % numDigits == 0:
divisableSubstrings += 1
if divisableSubstrings == 2:
ticker1 = numDigits+1
ticker2 = ticker1
##Counters
ticker2 -= 1
ticker1 += 1
ticker2 = numDigits
if divisableSubstrings == 1: ## One-Child Bouncer
OneChild.append(start) ## inefficient but I want the specifics
start += 1
return (OneChild)
## Speed seems improve with more pool arguments, labeled here as cores
## Im guessing this is due to pypy preforming best when task is neither
## to large nor small
def MultiProcList(numRange,start = 1,cores = 100): # multiprocessing
print "Asked to use %i cores between %i numbers: From %s to %s" % (cores,numRange-start, start,numRange)
cores = adjustCores(numRange,start,cores)
print "Using %i cores" % (cores)
chunk = (numRange+1-start)/cores
end = chunk+start -1
total, argsList= 0, []
for i in range(cores):
# print start,end-1
argsList.append((start,end-1))
start, end = end , end + chunk
pool = Pool(processes=cores)
data = pool.map(OneChild,argsList)
for d in data:
total += len(d)
print total
## f = open("Result.txt", "w+")
## f.write(str(total))
## f.close()
def adjustCores(numRange,start,cores):
if start == 1:
start = 0
else:
pass
while (numRange-start)%cores != 0:
cores -= 1
return cores
#MultiProcList(10**7)
from timeit import Timer
t = Timer(lambda: MultiProcList(10**6))
print t.timeit(number=1)
这是我最快的暴力代码。它使用cython来加速计算。它不是检查所有的数字,而是通过递归找到所有的一个子编号。在
要求F(10**7)的个数,大约需要100毫秒才能得到277674。在
^{pr2}$需要64位整数来计算大结果。
编辑:我添加了一些注释,但是我的英语不好,所以我将代码转换为纯python代码,并添加一些打印来帮助您了解它是如何工作的。在
_one_child_number
从左到s
递归相加,child_count
是{digits_count
是{这是
_one_child_number(0, 0, 3)
的输出,一个子3位数的计数是第二列(第一列是3位数)的和。在相关问题 更多 >
编程相关推荐