fork download
copy 
  1. from time import perf_counter as clock
  2.  
  3. def eureka4(ndigits):
  4.     """ Calculate eureka numbers with ndigits digits"""
  5.     # b is a table with ndigits rows for every position in the number
  6.     #    and 10 columns for the digits
  7.     #    b[pos][d] is the difference between d^(pos+1) and d*10^(ndigits-(pos+1))
  8.     # for a solution the cumulative difference should be zero.
  9.     # As the decimal magnitudes for digits are largest at the left of a number and the 
  10.     # power contributions the largest at the right of the number, the differences are 
  11.     # very negative at the left and very positive at the right. Moreover the ranges of
  12.     # the differences are the highest at the left and the right and the lowest in the 
  13.     # middle. For a branch and bound strategy is works well to process the numbers 
  14.     # in the order of the range of the differences per position.
  15.     b = [[x ** (j+1) - x * 10 ** (ndigits - (j+1)) for x in range(10)]
  16.          for j in range(ndigits)]
  17.     smin = [min(bi) for bi in b]  # min value for every row of b
  18.     smax = [max(bi) for bi in b]  # max value for every row of b
  19.     # pers is a permutation of [0, ndigits) with key: the range of the numbers of row b
  20.     perm = sorted(range(ndigits), key=lambda j: smax[j]-smin[j], reverse=True)
  21.     # scmin and scmax are the min and max contributions possible for the remaining digits
  22.     # in the permuted order
  23.     scmin = [sum(smin[perm[i]] for i in range(j+1, ndigits)) for j in range(ndigits)]
  24.     scmax = [sum(smax[perm[i]] for i in range(j+1, ndigits)) for j in range(ndigits)]
  25.     # now permute b, so that it is not necessary every time in branch
  26.     b = [b[j] for j in perm]
  27.  
  28.     def branch():
  29.         # search for solutions. Add positions in the order of the permutation,
  30.         # so that the (permuted) positions with the largest ranges come first
  31.         # the lower bound for the current state: current + scmin[pos] should be <= 0
  32.         # the upper bound for the current state: current + scmax[pos] should be >= 0
  33.         Q = [(0, 0, [])]
  34.         while Q:
  35.             pos, sofar, num = Q.pop()
  36.             x0 = 1 if perm[pos] == 0 else 0
  37.             for x in range(x0, 10):
  38.                 current = sofar + b[pos][x]
  39.                 if scmin[pos] <= -current <= scmax[pos]:
  40.                     if pos == ndigits-1:
  41.                         yield num + [x]
  42.                     else:
  43.                         Q.append((pos+1, current, num + [x]))
  44.  
  45.     for num in branch():
  46.         decimal = sum(d*10**(ndigits-perm[i]-1) for i, d in enumerate(num))
  47.         print(decimal)
  48.  
  49. t0 = clock()
  50. # solutions are only possible for a number of digits up to 22
  51. # it turns out that the highest solution has 20 digits
  52. for ndigits in range(1, 10):
  53.     eureka4(ndigits)
  54.  
  55. """
  56. PyPy
  57. trying 1 digits
  58. 1 1.22 msec
  59. 2 1.45 msec
  60. 3 1.64 msec
  61. 4 1.82 msec
  62. 5 1.96 msec
  63. 6 2.15 msec
  64. 7 2.34 msec
  65. 8 2.49 msec
  66. 9 2.62 msec
  67. elapsed time: 2.72 msec
  68. trying 2 digits
  69. 89 3.17 msec
  70. elapsed time: 535 usec
  71. trying 3 digits
  72. 518 3.9 msec
  73. 598 4.05 msec
  74. 135 4.25 msec
  75. 175 4.4 msec
  76. elapsed time: 1 msec
  77. trying 4 digits
  78. 2427 5.5 msec
  79. 1676 5.74 msec
  80. 1306 5.97 msec
  81. elapsed time: 1.7 msec
  82. trying 5 digits
  83. elapsed time: 6.57 msec
  84. trying 6 digits
  85. elapsed time: 14.4 msec
  86. trying 7 digits
  87. 2646798 38.7 msec
  88. elapsed time: 11.1 msec
  89. trying 8 digits
  90. elapsed time: 4.4 msec
  91. trying 9 digits
  92. elapsed time: 1.77 msec
  93. trying 10 digits
  94. elapsed time: 39 msec
  95. trying 11 digits
  96. elapsed time: 39.1 msec
  97. trying 12 digits
  98. elapsed time: 72.9 msec
  99. trying 13 digits
  100. elapsed time: 130 msec
  101. trying 14 digits
  102. elapsed time: 491 msec
  103. trying 15 digits
  104. elapsed time: 994 msec
  105. trying 16 digits
  106. elapsed time: 4.27 sec
  107. trying 17 digits
  108. elapsed time: 10.6 sec
  109. trying 18 digits
  110. elapsed time: 50.7 sec
  111. trying 19 digits
  112. elapsed time: 138 sec
  113. trying 20 digits
  114. 12157692622039623539 531 sec
  115. elapsed time: 505 sec
  116. trying 21 digits
  117. elapsed time: 1.41 ksec
  118. trying 22 digits
  119. elapsed time: 516 sec
  120. trying 23 digits
  121. elapsed time: 3 msec
  122. trying 24 digits
  123. elapsed time: 14.5 msec
  124. Total time 2636 secs
  125. """
Success #stdin #stdout 0.02s 9428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
2
3
4
5
6
7
8
9
89
518
598
135
175
2427
1676
1306
2646798
https://ideone.com/EduRd9
Eureka numbers
language:
Python 3 nbc (python 3.7.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!