Talk:Minimum multiple of m where digital sum equals m

From Rosetta Code

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)
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 = n19+n1+No where No = sum of n3 .. 2 .. n17
let Ʃe = sum of even digits = n20+Ne where Ne = sum of n2 .. 2 .. n18

n1 = 5

Now consider the table:

n20 n19  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

n20+n19 must be at least 7. Each time n20+n19 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)
I'm insanely impressed. Chapeau! Kudos to Pete :-) --Horst.h (talk) 16:14, 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)