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?


ANSWERS

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

371  3  9  27  2021  2023  289  49  7DL
391  3  9
3111  3  9  27  67  187  17  121  11
3131  3  9  27  221  17  37  111  133  13
3171  3  9  27  221  13  33  3009  177  17CB
3191  3  9  27  67  187  1261  3781  199  19
3211  3  9  27  221  21JD
3231  3  9  27  67  201  23JD
3271  3  9  27
3291  3  9  27  67  201  23  29JD
3311  3  9  27  67  187  10261  331  31CB
3331  3  9  27  221  663  6189  6567  199  399  33JD
3371  3  9  27  67  621  623  629  17  37JD

461  4  16  124  24  216  36  6
481  4  16  64  8
4121  4  16  124  12
4141  4  16  124  196  14
4161  4  16
4181  4  16  64  244  844  3364  324  18
4221  4  16  64  244  22JD
4241  4  16  124  484  24JD
4261  4  16  124  484  1936  136  526  26JD
4281  4  16  64  256  2224  28JD
4321  4  16  1024  32CB
4341  4  16  1024  34CB

5151  5  25  225  15
5251  5  25
5351  5  25  125  1225  35TG
5451  5  25  2025  45JD
5551  5  25  125  605  3025  55JD

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

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

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

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

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

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

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

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

15251  15  225  2305  23005  2125  25DL
15351  15  175  5  75  1055  35DL
15451  15  175  11125  125  1805  45DL
15551  15  225  3025  55DL

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

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

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

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

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

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

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

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

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

26281  26  2156  2102  22652  588952  21952  784  28DL

27291  27  729  7549  203589  294589  14589  589  29CB


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.