All geek questions in one place

Optimizing Brute Force process in python / pypy to find single child numbers

The Brute Force method is not intended to solve the problem, but helps in its research. I am working on a Project Euler problem that made me find all numbers from X to units less than Y that have exactly one "substring" divided by the number of digits in the number.

They are called one-child numbers. 104 is the number of one child. Of its substrings [1, 0, 4, 10, 04, 104], only 0 is divided by 3. The question asks the number of one-child numbers that occur less than 10 * 17. The brute force method is not the right approach; however, I have a theory that requires me to know the number of one number of children that occurred before 10 * 11.

I could not find this number even after I left my laptop for half a day. I tried Cython, made me a novice programmer who knows nothing about C. The result was very poor. I even tried cloud computing, but my ssh pipe always breaks until the process is complete.

If someone can help me identify some different approaches or optimize the preliminary preparation of the BRUTE FORCE method for this task to 10 ** 11, it would be very helpful.

PLEASE DO NOT ...

give me advice on number theory or your answers to this problem, as I have been working on this for a long time, and I really want to come to a conclusion myself.

## 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)
+4
source share
1 answer

This is my fastest brute force code. It uses cython to speed up the calculation. Instead of checking all the numbers, he finds all the "one child" numbers by recursion.

 %%cython cdef int _one_child_number(int s, int child_count, int digits_count): cdef int start, count, c, child_count2, s2, part, i if s >= 10**(digits_count-1): return child_count else: if s == 0: start = 1 else: start = 0 count = 0 for c in range(start, 10): s2 = s*10 + c child_count2 = child_count i = 10 while True: part = s2 % i if part % digits_count == 0: child_count2 += 1 if child_count2 > 1: break if part == s2: break i *= 10 if child_count2 <= 1: count += _one_child_number(s2, child_count2, digits_count) return count def one_child_number(int digits_count): return _one_child_number(0, 0, digits_count)

To find the number F (10 ** 7), it takes about 100 ms to get the result 277674.

 print sum(one_child_number(i) for i in xrange(8))

Computing large results requires a 64-bit integer.

EDIT: I added a few comments, but my English is not very good, so I convert the code to pure python code and add some fingerprint to help you figure out how it works.

_one_child_number adds the number on the left to s recursively, child_count is the count of children in s , digits_count is the final digits of s .

 def _one_child_number(s, child_count, digits_count): print s, child_count if s >= 10**(digits_count-1): # if the length of s is digits_count return child_count # child_count is 0 or 1 here, 1 means we found one one-child-number. else: if s == 0: start = 1 #if the length of s is 0, we choose from 123456789 for the most left digit. else: start = 0 #otherwise we choose from 0123456789 count = 0 # init the one-child-number count for c in range(start, 10): # loop for every digit s2 = s*10 + c # add digit c to the right of s # following code calculates the child count of s2 child_count2 = child_count i = 10 while True: part = s2 % i if part % digits_count == 0: child_count2 += 1 if child_count2 > 1: # when child count > 1, it not a one-child-number, break break if part == s2: break i *= 10 # if the child count by far is less than or equal 1, # call _one_child_number recursively to add next digit. if child_count2 <= 1: count += _one_child_number(s2, child_count2, digits_count) return count

Here it is from _one_child_number(0, 0, 3) , and the number of single-digit numbers of three digits is the sum of the second column, in which the first column is 3 digits.

 0 0 1 0 10 1 101 1 104 1 107 1 11 0 110 1 111 1 112 1 113 1 114 1 115 1 116 1 117 1 118 1 119 1 12 1 122 1 125 1 128 1 13 1 131 1 134 1 137 1 14 0 140 1 141 1 142 1 143 1 144 1 145 1 146 1 147 1 148 1 149 1 15 1 152 1 155 1 158 1 16 1 161 1 164 1 167 1 17 0 170 1 171 1 172 1 173 1 174 1 175 1 176 1 177 1 178 1 179 1 18 1 182 1 185 1 188 1 19 1 191 1 194 1 197 1 2 0 20 1 202 1 205 1 208 1 21 1 211 1 214 1 217 1 22 0 220 1 221 1 222 1 223 1 224 1 225 1 226 1 227 1 228 1 229 1 23 1 232 1 235 1 238 1 24 1 241 1 244 1 247 1 25 0 250 1 251 1 252 1 253 1 254 1 255 1 256 1 257 1 258 1 259 1 26 1 262 1 265 1 268 1 27 1 271 1 274 1 277 1 28 0 280 1 281 1 282 1 283 1 284 1 285 1 286 1 287 1 288 1 289 1 29 1 292 1 295 1 298 1 3 1 31 1 311 1 314 1 317 1 32 1 322 1 325 1 328 1 34 1 341 1 344 1 347 1 35 1 352 1 355 1 358 1 37 1 371 1 374 1 377 1 38 1 382 1 385 1 388 1 4 0 40 1 401 1 404 1 407 1 41 0 410 1 411 1 412 1 413 1 414 1 415 1 416 1 417 1 418 1 419 1 42 1 422 1 425 1 428 1 43 1 431 1 434 1 437 1 44 0 440 1 441 1 442 1 443 1 444 1 445 1 446 1 447 1 448 1 449 1 45 1 452 1 455 1 458 1 46 1 461 1 464 1 467 1 47 0 470 1 471 1 472 1 473 1 474 1 475 1 476 1 477 1 478 1 479 1 48 1 482 1 485 1 488 1 49 1 491 1 494 1 497 1 5 0 50 1 502 1 505 1 508 1 51 1 511 1 514 1 517 1 52 0 520 1 521 1 522 1 523 1 524 1 525 1 526 1 527 1 528 1 529 1 53 1 532 1 535 1 538 1 54 1 541 1 544 1 547 1 55 0 550 1 551 1 552 1 553 1 554 1 555 1 556 1 557 1 558 1 559 1 56 1 562 1 565 1 568 1 57 1 571 1 574 1 577 1 58 0 580 1 581 1 582 1 583 1 584 1 585 1 586 1 587 1 588 1 589 1 59 1 592 1 595 1 598 1 6 1 61 1 611 1 614 1 617 1 62 1 622 1 625 1 628 1 64 1 641 1 644 1 647 1 65 1 652 1 655 1 658 1 67 1 671 1 674 1 677 1 68 1 682 1 685 1 688 1 7 0 70 1 701 1 704 1 707 1 71 0 710 1 711 1 712 1 713 1 714 1 715 1 716 1 717 1 718 1 719 1 72 1 722 1 725 1 728 1 73 1 731 1 734 1 737 1 74 0 740 1 741 1 742 1 743 1 744 1 745 1 746 1 747 1 748 1 749 1 75 1 752 1 755 1 758 1 76 1 761 1 764 1 767 1 77 0 770 1 771 1 772 1 773 1 774 1 775 1 776 1 777 1 778 1 779 1 78 1 782 1 785 1 788 1 79 1 791 1 794 1 797 1 8 0 80 1 802 1 805 1 808 1 81 1 811 1 814 1 817 1 82 0 820 1 821 1 822 1 823 1 824 1 825 1 826 1 827 1 828 1 829 1 83 1 832 1 835 1 838 1 84 1 841 1 844 1 847 1 85 0 850 1 851 1 852 1 853 1 854 1 855 1 856 1 857 1 858 1 859 1 86 1 862 1 865 1 868 1 87 1 871 1 874 1 877 1 88 0 880 1 881 1 882 1 883 1 884 1 885 1 886 1 887 1 888 1 889 1 89 1 892 1 895 1 898 1 9 1 91 1 911 1 914 1 917 1 92 1 922 1 925 1 928 1 94 1 941 1 944 1 947 1 95 1 952 1 955 1 958 1 97 1 971 1 974 1 977 1 98 1 982 1 985 1 988 1
+1
source

Source: https://habr.com/ru/post/1468899/

More articles:


All Articles