# 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)- I must find the time to code this! Until such time I need to add a new rule when 11 is a prime factor. For a number to be divisible by 11 the sum of the digits in the odd places - the sum of the digits in the even places must be a multiple of 11 including zero. Candidates should be constructed with this in mind. Note that the above rules can of course be extended to include 200, 100, 50, and 25--Nigel Galloway (talk) 12:01, 7 February 2022 (UTC)

- Never heard of that rule for numbers divisible by 11 before, certainly sounds like it might be be rather handy.
- Here are some preliminary results of a brute force attack (wading through as many billion numbers as it could in a few seconds or so)
- Actual results are marked with an asterisk, obviously I've carried on regardless looking for and/or proving any patterns.
- Constructing the first candidates might be a tad tricker than it first looks... --Pete Lomax (talk) 11:00, 8 February 2022 (UTC)

- Never heard of that rule for numbers divisible by 11 before, certainly sounds like it might be be rather handy.

For n=11: We can discount all 8 potential 2-digit candidates 29,38,47,56,65,74,83,92 as none are divisible by 11. There are only 8 potential 3-digit candidates: 209*,308,407,506,605,704,803,902, and there are only 8 potential 4-digit candidates: 2090,3080,4070,5060,6050,7040,8030,9020. There are only 61 potential 5-digit candidates: 10109,10208,10307,10406,10505,10604,10703,10802,10901,20009,..90200, again there are only 61 potential 6-digit candidates, the same set as 5-digits but with a trailing zero (but not so for n>11). there are only 279 potential 7-digit candidates: 1000109..9020000, "" for 8-digit candidates there are only 992 potential 9-digit candidates: 100000109..902000000, "" for 10-digit candidates The first potential 11 digit candidate is 10000000109 For n=22 (but including all the odd candidates for now): There are no potential 2 or 3 digit candidates at all. There are only 64 potential 4 digit candidates: 2299,2398*,..2992,3289,..9724,9823,9922. There are 509 potential 5 digit candidates: 12199,12298,12397,..12991,13189,..98230,99022,99121,99220. There are 4230 potential 6 digit candidates: 101299..992200 There are 19770 potential 7 digit candidates: 1002199..9922000 There are 97611 potential 8 digit candidates: 10001299..99220000 There are 350676 potential 9 digit candidates: 100002199..992200000 There are 1334740 potential 10 digit candidates: 1000001299..9922000000 The first potential 11 digit candidate is 10000002199 For n=33 (and dropping the limit by 1 digit as it is starting to crawl): There are no potential 2, 3, or 4 digit candidates at all. There are only 168 potential 5 digit candidates: 42999*,43989,44979,45969,..99726,99825,99924. There are 2730 potential 6 digit candidates: 141999..999240 There are 41690 potential 7 digit candidates: 1032999..9992400 There are 331292 potential 8 digit candidates: 10041999..99924000 There are 2437485 potential 9 digit candidates: 100032999..999240000 The first potential 10 digit candidate is 1000041999 for n=44: There are no potential 2..5 digit candidates at all. There are 441 potential 6 digit candidates: 449999..479996*..999944 There are 12279 potential 7 digit candidates: 1439999..9999440 There are 292800 potential 8 digit candidates: 10349999..99994400 There are 3568545 potential 9 digit candidates: 100439999..999944000 The first potential 10 digit candidate is 1000349999 for n=55: There are no potential 2..6 digit candidates at all. There are 420 potential 7 digit candidates: 6499999..9999946 There are 21180 potential 8 digit candidates: 16399999..60989995*..99999460 There are 1042440 potential 9 digit candidates: 105499999..999994600 The first potential 10 digit candidate is 1006399999 for n=66 (and we can just afford to increase the limit again): There are no potential 2..7 digit candidates at all. There are 400 potential 8 digit candidates: 66999999..67999998*..99999966 There are 37200 potential 9 digit candidates: 165999999..999999660 There are 3067425 potential 9 digit candidates: 1056999999..9999996600 The first potential 11 digit candidate is 10065999999 for n=77: There are no potential 2..8 digit candidates at all. There are 100 potential 9 digit candidates: 869999999..899897999*..999999968 There are 17350 potential 10 digit candidates: 1859999999..9999999680 The first potential 11 digit candidate is 10769999999 for n=88 (ditto): There are no potential 2..9 digit candidates at all. There are 25 potential 10 digit candidates: 8899999999..9999999988 There are 14960 potential 11 digit candidates: 18799999999..19999999888*..99999999880 The first potential 12 digit candidate is 107899999999 for n=99: There are no potential 2..12 digit candidates at all (is that right?). The first potential 13 digit candidate is 1098999999999* for n=110 (without the trailing zero optimisation): There are no potential 2..13 digit candidates at all. The first potential 14 digit candidate is 11999999999999 (119999999999990*, 15 digits)

## 165

I thought it might be useful to work 165. The minimal starting value is 7999999999999999995 as expressed below:

21111111111 09876543210987654321 -------------------- 7999999999999999995

let Ʃo = sum of odd digits = n_{19}+n_{1}+No where No = sum of n_{3} .. 2 .. n_{17}

let Ʃe = sum of even digits = n_{20}+Ne where Ne = sum of n_{2} .. 2 .. n_{18}

n_{1} = 5

Now consider the table:

n_{20}n_{19}No Ne Ʃo Ʃe (Ʃo-Ʃe % 11 = 0) 0 7 72 81 84 81 No 0 8 71 81 84 81 No 0 8 72 80 85 80 No 0 9 70 81 84 81 No 0 9 71 80 85 80 No 0 9 71 80 85 80 No 0 9 72 79 86 79 No 1 6 72 81 83 82 No 1 7 71 81 83 82 No 1 7 72 80 84 81 No 1 8 70 81 83 82 No 1 8 71 80 84 81 No 1 8 71 80 84 81 No 1 8 72 79 85 80 No 1 9 69 81 83 82 No 1 9 70 80 84 81 No 1 9 70 80 84 81 No 1 9 71 79 85 80 No 1 9 70 80 84 81 No 1 9 71 79 85 80 No 1 9 71 79 85 80 No 1 9 72 78 86 79 No 2 5 72 81 82 83 No . . . 7 0 72 81 77 88 Yes

n_{20}+n_{19} must be at least 7. Each time n_{20}+n_{19} is incremented 1 must be subtracted from either No or Ne. The table above depicts the possibilities and is in fact a perfectly balanced binary tree. When a candidate is identified No and Ne must be expanded to the set of 8 digits summing to No and the set of 9 digits summing to Ne, and all combinations considered. In this case it is easy as 72 can only be 8 nines and 81 can only be 9 nines. Thus it only remains to prove that 70999999999999999995 is divisible by 3.--Nigel Galloway (talk) 13:37, 8 February 2022 (UTC)

## I'm out

Gave up on 370. 275 still a little tardy/not done 25. Pretty pleased with 200 in 0.7s though. --Pete Lomax (talk) 12:21, 14 February 2022 (UTC)

- I'm trying to decide on an adjective to describe this. I might have to toss a coin to choose between insane and impressive.--Nigel Galloway (talk) 13:41, 14 February 2022 (UTC)

- FWIW, you may like to consider submitting this to OEIS for inclusion on the A131382 page. They only have a list of the first 90 terms at the moment. If you are so inclined. --Thundergnat (talk) 16:56, 14 February 2022 (UTC)
- Good idea, done. Update: that page links to A002998 which aleady had
**1000**terms (gulp) and a c++ program... --Pete Lomax (talk) 15:59, 15 February 2022 (UTC) - OK, now I really, really, really am out
*(please, pretty please!)*--Pete Lomax (talk) 17:19, 19 February 2022 (UTC)