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.

a b Shortest Known Cycle Author
2 4 1 2 4
2 6 1 2 4 8 16 11 12 14 18 3 6
2 8 1 2 4 8
2 12 1 2 4 8 16 112 11 12
2 14 1 2 4 8 16 26 52 102 14
2 16 1 2 4 8 16
2 18 1 2 4 8 16 26 52 104 18
2 22 1 2 4 8 16 112 122 11 22 TG
2 24 1 2 4 8 16 112 124 11 22 24 TG
2 26 1 2 4 8 16 26 TG
2 28 1 2 4 8 16 26 52 104 18 28 CB
2 32 1 2 4 8 16 32 JD
2 34 1 2 4 8 16 32 34 JD
2 36 1 2 4 8 16 26 52 104 18 36 JD
2 38 1 2 4 8 16 32 34 38 JD

a	b	Shortest Known Cycle	Author
2	4	1 2 4
2	6	1 2 4 8 16 11 12 14 18 3 6
2	8	1 2 4 8
2	12	1 2 4 8 16 112 11 12
2	14	1 2 4 8 16 26 52 102 14
2	16	1 2 4 8 16
2	18	1 2 4 8 16 26 52 104 18
2	22	1 2 4 8 16 112 122 11 22	TG
2	24	1 2 4 8 16 112 124 11 22 24	TG
2	26	1 2 4 8 16 26	TG
2	28	1 2 4 8 16 26 52 104 18 28	CB
2	32	1 2 4 8 16 32	JD
2	34	1 2 4 8 16 32 34	JD
2	36	1 2 4 8 16 26 52 104 18 36	JD
2	38	1 2 4 8 16 32 34 38	JD

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
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

a	b	Shortest Known Cycle	Author
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

a b Shortest Known Cycle Author
26 28 1 26 2156 2102 22652 588952 21952 784 28 DL

a	b	Shortest Known Cycle	Author
26	28	1 26 2156 2102 22652 588952 21952 784 28	DL

a b Shortest Known Cycle Author
27 29 1 27 729 7549 203589 294589 14589 589 29 CB

a	b	Shortest Known Cycle	Author
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.