Подход грубой силы предназначен не для решения вопроса, а для помощи в его исследовании. Я работаю над задачей Project Euler, в которой мне нужно найти все числа от X до единицы меньше Y, которые имеют ровно одна «подстрока», кратная количеству цифр в числе.
Это так называемые однодетные номера. 104 — однодетное число. Из его подстрок [1, 0, 4, 10, 04, 104] только 0 делится на 3. Задача состоит в том, чтобы найти количество однодочерних чисел, которые встречаются меньше 10*17. Метод грубой силы не является правильным подходом; однако у меня есть теория, которая требует, чтобы я знал количество дочерних чисел, встречающихся до 10*11.
Мне не удалось найти этот номер даже после того, как я оставил свой ноутбук включенным на полдня. Я попробовал Cython, поставил я начинающий программист, который ничего не знает о C. Результат был очень плохим. Я даже пробовал облачные вычисления, но мой ssh-канал всегда ломается до завершения процесса.
Если бы кто-то мог помочь мне определить некоторые другие подходы или оптимизацию для предварительного формирования метода BRUT 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)
divisableSubstrings == 2. - person HYRY schedule 13.03.2013