Problem of the Month (November 2007)

Start with the number 1. Pick two positive integers 1<a<b. In each iteration, you can either replace some substring s of your number with a*s, or if s is divisible by b, you can replace s with s/b. What is the length of the smallest cycle that gets you back to 1?

Dave Langers pointed out that we get different results depending on whether leading 0's are allowed when forming a substring, and when leaving a substring. The results below allow leading zeroes in both directions. What are the shortest that don't allow leading zeroes?

Trevor Green, Dave Langers, and Claudio Baiocchi sent several solutions, many of which were the shortest known.

Joe DeVincentis and Dave Langers pointed out that in order to have a solution, a and b must have the same parity. Joe DeVincentis also noticed that both or neither of a and b must be divisible by 5.

Dave Langers also wondered how the results of this problem behave in other bases. Claudio Baiocchi noted that if x is a factor of the base X, both or neither of a and b must be divisible by x. But he notes this is not a sufficient condition for a solution: in base 10 there is no solution for a=10 and b=20.

Claudio Baiocchi and Trevor Green observed that the shortest solutions often aren't unique. Claudio Baiocchi noted that even when cycles that contain 1 don't exist, other cycles can exist.

Bryce Herdt also sent some solutions.

Here are the shortest known cycles.

abShortest Known CycleAuthor
241  2  4
261  2  4  8  16  11  12  14  18  3  6
281  2  4  8
2121  2  4  8  16  112  11  12
2141  2  4  8  16  26  52  102  14
2161  2  4  8  16
2181  2  4  8  16  26  52  104  18
2221  2  4  8  16  112  122  11  22TG
2241  2  4  8  16  112  124  11  22  24TG
2261  2  4  8  16  26TG
2281  2  4  8  16  26  52  104  18  28CB
2321  2  4  8  16  32JD
2341  2  4  8  16  32  34JD
2361  2  4  8  16  26  52  104  18  36JD
2381  2  4  8  16  32  34  38JD

 3 7 1  3  9  27  2021  2023  289  49  7 DL 3 9 1  3  9 3 11 1  3  9  27  67  187  17  121  11 3 13 1  3  9  27  221  17  37  111  133  13 3 17 1  3  9  27  221  13  33  3009  177  17 CB 3 19 1  3  9  27  67  187  1261  3781  199  19 3 21 1  3  9  27  221  21 JD 3 23 1  3  9  27  67  201  23 JD 3 27 1  3  9  27 3 29 1  3  9  27  67  201  23  29 JD 3 31 1  3  9  27  67  187  10261  331  31 CB 3 33 1  3  9  27  221  663  6189  6567  199  399  33 JD 3 37 1  3  9  27  67  621  623  629  17  37 JD

 4 6 1  4  16  124  24  216  36  6 4 8 1  4  16  64  8 4 12 1  4  16  124  12 4 14 1  4  16  124  196  14 4 16 1  4  16 4 18 1  4  16  64  244  844  3364  324  18 4 22 1  4  16  64  244  22 JD 4 24 1  4  16  124  484  24 JD 4 26 1  4  16  124  484  1936  136  526  26 JD 4 28 1  4  16  64  256  2224  28 JD 4 32 1  4  16  1024  32 CB 4 34 1  4  16  1024  34 CB

 5 15 1  5  25  225  15 5 25 1  5  25 5 35 1  5  25  125  1225  35 TG 5 45 1  5  25  2025  45 JD 5 55 1  5  25  125  605  3025  55 JD

 6 8 1  6  36  186  1116  112  14  64  8 6 12 1  6  36  336  28  248  24  2  12 6 14 1  6  36  336  24  144  14 6 16 1  6  36  186  1116  1616  101  16 6 18 1  6  36  2  12  62  372  34  324  18 6 22 1  6  36  186  1516  13016  118096  5368  244  22 CB 6 24 1  6  36  216  296  24 JD 6 26 1  6  36  216  296  1776  17426  676  26 JD 6 28 1  6  36  216  1296  6296  61776  614556  21952  784  28 CB

 7 9 1  7  49  289  1969  1169  1161  129  729  81  9 7 11 1  7  49  289  1489  13423  1223  12221  1111  111  11 7 13 1  7  49  343  2401  247  19  133  13 7 17 1  7  49  289  17 7 19 1  7  49  463  3223  322021  31159  361  19 CB 7 21 1  7  49  463  4441  421  21 JD 7 23 1  7  49  463  23 JD 7 27 1  7  49  289  1489  14863  1183  7783  729  27 JD 7 29 1  7  49  289  2623  24361  841  29 CB

 8 12 1  8  64  484  3284  25684  2144  16844  1444  124  12 8 14 1  8  64  484  3284  24284  20384  1456  156  14 CB 8 16 1  8  64  4  32  2  16 8 18 1  8  64  484  4644  36844  3384  188  18 8 22 1  8  6  4  484  22 JD 8 24 1  8  64  484  24 JD 8 26 1  8  64  512  582  5642  217  2156  26 JD 8 28 1  8  64  484  3284  26272  2224  28 CB

 9 11 1  9  81  721  6321  54321  454321  3654321  27654321  187654321  17654321  1654321  154321  14321  1321  121  11 CB 9 13 1  9  81  729  7281  66521  589521  4589521  353041  25157  2089  169  13 CB 9 17 1  9  81  729  72081  4241  38169  3489  289  17 DL 9 19 1  9  81  89  801  7201  379  3781  199  19 9 21 1  9  81  721  6321  321  2889  26001  269  2421  221  21 CB 9 23 1  9  81  729  6329  62961  566161  5667  529  23 CB 9 27 1  9  81  3  27 9 29 1  9  81  729  6561  65541  2261  29 CB

 11 13 1  11  111  1221  13221  1317  13117  139  13 11 17 1  11  111  1221  113  1213  12343  12023  1119  17 DL 11 19 1  11  121  1231  13231  1171  19 11 21 1  11  111  1111  101221  4821  48821  4421  421  21 DL 11 23 1  11  121  1331  130341  5667  529  23 CB 11 27 1  11  111  1121  11331  114641  126104  1261441  19683  729  27 CB 11 29 1  11  121  1331  14331  147641  1624041  16829  589  29 CB

 12 14 1  12  144  14 12 16 1  12  144  9  108  196  16 12 18 1  12  122  1222  102664  5764  324  18 CB 12 22 1  12  1024  12288  1188  118096  5368  244  22 DL 12 24 1  12  10024  100248  4177  41924  484  24 DL 12 26 1  12  124  1488  16888  202656  20156  26 CB 12 28 1  12  144  1484  16884  202564  20224  28 CB 12 36 1  12  144  1728  128  1296  36 BH 12 38 1  12  124  1444  38 BH

 13 17 1  13  10039  599  7679  77879  1001879  1119  17 DL 13 19 1  13  133  7  91  1171  19 13 21 1  13  169  100897  4897  481261  4861  441  21 DL 13 23 1  13  139  1399  18187  138187  6187  269  23 CB 13 27 1  13  133  1429  15469  154789  2002789  200189  27 CB 13 29 1  13  169  1789  171049  171529  2229769  221769  2261  29 CB

 14 16 1  14  196  16 14 18 1  14  196  1984  114  1144  18 14 22 1  14  144  10564  484  22 CB 14 24 1  14  144  1564  17896  250466  22166  296  24 CB 14 26 1  14  156  1784  134  1476  15676  676  26 CB 14 28 1  14  144  2016  20224  28 CB

 15 25 1  15  225  2305  23005  2125  25 DL 15 35 1  15  175  5  75  1055  35 DL 15 45 1  15  175  11125  125  1805  45 DL 15 55 1  15  225  3025  55 DL

 16 18 1  16  196  11446  114736  11472  1144  18 CB 16 22 1  16  166  13  148  10648  484  22 DL 16 24 1  16  196  11536  115576  11524  484  24 CB 16 26 1  16  196  11446  114736  1147576  15676  676  26 CB 16 28 1  16  166  1966  191056  13252  139  2224  28 CB

 17 19 1  17  1119  11719  199  19 17 21 1  17  1119  11323  163  13  221  21 CB 17 23 1  17  1119  11879  201799  230583  463  23 CB 17 27 1  17  1119  11179  190043  19683  729  27 CB 17 29 1  17  289  3489  341369  5802169  202169  2021769  20261  29 DL

 18 22 1  18  1144  19844  944  9724  442  22 CB 18 24 1  18  1144  11724  210624  2126  22166  296  24 CB 18 26 1  18  1144  44  792  14256  1420906  54656  2156  26 DL 18 28 1  18  1144  12524  145364  1725364  61624  2224  28 CB

 19 21 1  19  361  6841  615241  11685241  185241  8821  421  21 CB 19 23 1  19  1171  11971  1118449  11849  189  11529  529  23 CB 19 27 1  19  10171  193249  19320769  1911889  19449  729  27 DL 19 29 1  19  1171  111331  1125289  14329  1431  14589  589  29 CB

 21 23 1  21  441  4841  101641  134441  2814441  122367  12167  529  23 CB 21 27 1  21  421  4421  44221  488641  10261441  19683  729  27 CB 21 29 1  21  421  8841  829  8429  841  29 CB

 22 24 1  22  484  24 CB 22 26 1  22  244  5284  56248  56005456  2154056  215156  2156  26 DL 22 28 1  22  484  10564  220564  2224  28 CB

 23 27 1  23  463  10649  106929  3969  391587  14587  547  27 CB 23 29 1  23  529  5469  510589  5230589  52329  589  29 CB

 24 26 1  24  296  29144  2218444  208444  8444  202656  2156  26 DL 24 28 1  24  576  51824  1243224  15836824  565624  20224  28 CB

 25 35 1  25  505  12505  312625  3175  35 DL 25 45 1  25  2125  21625  240505  2905  2025  45 DL 25 55 1  25  625  6625  165025  3025  55 DL

 26 28 1  26  2156  2102  22652  588952  21952  784  28 DL

 27 29 1  27  729  7549  203589  294589  14589  589  29 CB

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 11/13/07.