Talk:Minimum multiple of m where digital sum equals m

Observation for bigger m

I am trying to find a way to minimize the range for the search.
The start n is easy to construct

  m   Start/End n       multiples 1..9 of 100/m
                      x1       x2       x3       x4       x5       x6       x7       x8       x9
  41       1463--  2.43902  4.87805  7.31707  9.75610 12.19512 14.63415 17.07317 19.51220 21.95122
           4339
1463*41 = 59,983. 6*10,000-1 = 59,999 has sum of digits = 41 
The factor number is 6 one step therefor 1463/6 = 243.833
But the result n = 4339 / 243.833 ~ 17,8 not integer like  

  42       1666--  2.38095  4.76190  7.14286  9.52381 11.90476 14.28571 16.66667 19.04762 21.42857
           2119
much better to see n start = 8xk and n final is 10xk 
  43       1860-- >2.32558< 4.65116  6.97674  9.30233 11.62791 13.95349 16.27907 !18.60465! 20.93023
           2323
but much better for bigger m here x1000/m
                           x1       x2       x3       x4       x5       x6       x7       x8       x9
 140 428571428571420--  7.14286 14.28571 21.42857 28.57143 35.71429 42.85714 50.00000 57.14286 64.28571
     571427857142857   n start = x6 n final = x8
 141 49645390070921--  7.09220 14.18440 21.27660 28.36879 35.46099 42.55319 49.64539 56.73759 63.82979
     63822694964539    n start = x7 n final = x9
 142 56338028169014--  7.04225 14.08451 21.12676 28.16901 35.21127 42.25352 49.29577 56.33803 63.38028
    140140838028169    n start = x8 n final = x12
 143 62937062937062--  6.99301 13.98601 20.97902 27.97203 34.96503 41.95804 48.95105 55.94406 62.93706
    391606993006993    n start = x9 n final = x 56
 144 69444444444444--  6.94444 13.88889 20.83333 27.77778 34.72222 41.66667 48.61111 55.55556 62.50000
    277777777777777    n start = x1 n final = x4
 145 137931034482758--  6.89655 13.79310 20.68966 27.58621 34.48276 41.37931 48.27586 55.17241 62.06897
     482751724137931    n start = x2 n final = x7
 146 205479452054794--  6.84932 13.69863 20.54795 27.39726 34.24658 41.09589 47.94521 54.79452 61.64384
     471917801369863    n start = x3 n final = x6.89
 147 272108843537414--  6.80272 13.60544 20.40816 27.21088 34.01361 40.81633 47.61905 54.42177 61.22449
     401360544217687    n start = x4 n final = x5.9
 148 337837837837837--  6.75676 13.51351 20.27027 27.02703 33.78378 40.54054 47.29730 54.05405 60.81081
    1081081081081081    n start = x5 n final = x16
 149 402684563758389--  6.71141 13.42282 20.13423 26.84564 33.55705 40.26846 46.97987 53.69128 60.40268
     536912751677851    n start = x6 n final = x8

--Horst.h (talk) 14:50, 2 February 2022 (UTC)

I think for bigger values turning the task into a problem in combinatorics will be better. Taking 140 simplistically the minimum is 5999999999999999, which obviously is not divisible by 140. The solution is 79999899999999980. So I could try 6+15 digits which sum to 134 then 7+15 digits which sum to 133 until I find a number divisible by 140. Let me call this 15 digit number set N. Note that 6+N will have the same N as 15+N, 24+N, 33+N, 42+N, 51+N, and 60+N. If I optimize this for a particular number the prime factors of 140 are 2,2,5 and 7 from which it follows that the final digit must be 0 and the last but 1 must be even. Which makes the search space very small.--Nigel Galloway (talk) 16:21, 2 February 2022 (UTC)

Very good. That trailing zero optimisation is just amazing. I used a custom counting method instead of combinatorics but it's pretty much the same idea really. 165 appears to be quite knarly, or at least around 100s which is 99 more than the total time taken for all of 1..164. 275 is even worse. --Pete Lomax (talk) 23:22, 5 February 2022 (UTC)