给定一个整数 x
,我必须找到一个最小基数b
(b > 1) 使得 x
base b
是回文。
例如:5 base 2 是回文,即 5 in base 2 : 101 是回文。除了暴力破解之外,如何以更好的方式解决它?
最佳答案
公平警告:这不是一个完整的答案,而是一些可能有用的注释。希望到目前为止,鉴于问题和评论的非正统性质,没有人会对此感到不安。 :)
- 基地 2
- 11:3
- 101: 5 (+2) 天
- 111: 7 (+2) 2
- 1001: 9 (+2) 天
- 1111: 15 (+6) 2
- 10001: 17 (+2) 天
- 10101: 21 (+4)
- 11011: 27 (+6) 2
- 11111: 31 (+4)
- 100001: 33 (+2) 天
- 101101:45 (+12)
- 110011: 51 (+6) 2
- 111111:63 (+12)
- 基地 3
- 11:4
- 22: 8 (+4) 1
- 101: 10 (+2) 天
- 111: 13 (+3)
- 121: 16 (+3)
- 202: 20 (+4) 1
- 212: 23 (+3)
- 222: 26 (+3)
- 1001: 28 (+2) 天
- 1111: 40 (+12)
- 1221: 52 (+12)
- 2002 年:56 (+4) 1
- 2112: 68 (+12)
- 2222: 80 (+12)
- 基础 4
- 11:5
- 22: 10 (+5) 1
- 33: 15 (+5) 1
- 101: 17 (+2) 天
- 111: 21 (+4)
- 121: 25 (+4)
- 131: 29 (+4)
- 202: 34 (+5) 1
- 212: 38 (+4)
- 222: 42 (+4)
- 232: 46 (+4)
- 303: 51 (+5) 1
- 313: 55 (+4)
- 323: 59 (+4)
- 333: 63 (+4)
我把和之前的区别标记为(+n),最后加了一些注释:
- 1:这里递增的第一个数字
- 2:第二位数字在这里递增(我只将其标记为以 2 为基数;其他地方似乎无关紧要)
- d:这里递增的位数(第一位重置为1)
一些结构观察:
- 基数中的第一个(最小的)回文总是(基数+1)。我们不允许使用 1,也不允许使用任何前导零。
- (N < base) 的前 N 个回文是 N*(base+1)。
- 第(base)个回文总是比第(base-1)个多 2(并且总是表示为 101)。
- 2位回文的个数是(base-1)。
- 3位和4位回文的个数是(base-1)*base。
最后,一些不太成熟的想法:
- x的回文表示的位数为1+log_base(x)。
- 给定长度的第一个回文总是 10..01。
- 当末端没有标记时(即当第一个数字和数字的计数都不变时),您可以看到重复差异的模式。这可能让我们“快进”通过从 10..01 开始的候选回文。
关于c - 一个数字的最小底数,当以该底数表示时使其成为回文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25104122/