蛮力方法的目的不是解决问题,而是帮助其研究。我正在研究一个Project Euler问题,该问题让我找到从 X 到比 Y 小一的所有数字,这些数字恰好有一个“子字符串”可以被数字中的位数整除。
这些被称为独生子女号码。104是独生子女号码。在它的子串中,[1, 0, 4, 10, 04, 104] 只有 0 可以被 3 整除。问题要求找出出现小于 10* 17 的单子数的数量。蛮力方法不是正确的方法;但是,我有一个理论要求我知道在 10 *11 之前出现的一个子数字的数量。
即使在我的笔记本电脑开机半天后,我也没有成功找到这个号码。我尝试了 Cython,假设我是一个对 C 一无所知的新手程序员。结果真的很糟糕。我什至尝试过云计算,但我的 ssh 管道总是在进程完成之前中断。
如果有人可以帮助我确定一些不同的方法或优化来针对这个问题执行BRUTE FORCE 方法,直到 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)