如何高效找到满足“反转数为原数2倍”的最小正整数?
如何高效找到满足“反转数为原数2倍”的最小正整数?
嘿,我来给你理清楚这个问题——其实你不用再让代码死循环跑了,因为十进制下根本不存在这样的正整数N!下面我给你一步步讲清楚为什么,以及怎么用数学推导来验证,而不是靠暴力枚举。
首先,我们先从数论和数位推导的角度来分析:
第一步:模运算的矛盾推导
首先,一个正整数和它的反转数在模9下是相等的——因为10≡1 mod9,所以任何10的幂次都≡1 mod9,比如10³=1000≡1 mod9,所以N=Σa_i×10^i ≡Σa_i×1=数字和S(N) mod9,反转数rev(N)=Σa_i×10^{d-i-1}≡Σa_i=S(N) mod9,所以N≡rev(N) mod9。
而题目要求rev(N)=2N,代入上面的结论:
N ≡2N mod9 → 两边减N得0≡N mod9,也就是N必须是9的倍数,这一步没问题,但还有更关键的矛盾:
第二步:数位进位的矛盾推导
假设N是d位数,最高位a₁(a₁≠0),最低位a_d。因为rev(N)=2N,所以:
- rev(N)的最高位是a_d,也就是2N的最高位是a_d;而2N是d位数(如果2N是d+1位,那反转数rev(N)是d位,不可能等于d+1位的2N),所以2×a₁ <10 →a₁只能是1、2、3、4。
- rev(N)的个位是a₁,也就是2N的个位是a₁;而2N的个位是2×a_d的个位,所以2×a_d的个位必须等于a₁。
- 同时,2N的最高位a_d ≥2×a₁(因为N≥a₁×10{d-1},所以2N≥2a₁×10{d-1},最高位至少是2a₁)。
现在我们把a₁的可能值(1-4)逐个验证:
- a₁=1:2×a_d的个位是1,但2乘任何数的个位都是偶数,不可能是1,直接排除;
- a₁=2:2×a_d的个位是2 →a_d可以是1或6。但根据上面的第3点,a_d≥2×2=4,所以a_d只能是6。现在看最高位的计算:2N的最高位是6,而2N的最高位是2×a₁ + 前一位的进位c,也就是2×2 +c=4+c=6 →c=2。但进位c是前一位乘2加进位后的十位,最大只能是1(因为单个数字乘2最多18,加进位1最多19,十位是1),不可能是2,矛盾,排除;
- a₁=3:2×a_d的个位是3,同样2乘任何数个位是偶数,不可能是奇数3,排除;
- a₁=4:2×a_d的个位是4 →a_d可以是2或7。根据第3点,a_d≥2×4=8,而2和7都小于8,矛盾,排除。
所有可能的最高位都推导出来矛盾,说明十进制下根本不存在这样的正整数N!
为什么你的代码跑不出来结果?
因为这样的数不存在,所以不管你把范围设到多大,暴力枚举永远找不到结果,只会白白浪费时间。
补充:如果换其他进制呢?
哦对了,如果你是好奇类似的数在其他进制下是否存在,比如在9进制下确实有这样的数,但十进制下确实没有。
所以总结一下:
- 不用再优化代码或者扩大范围了,十进制里没有满足rev(N)=2N的正整数;
- 用数学推导可以直接证明不存在,比暴力枚举高效一万倍。
备注:内容来源于stack exchange,提问作者Affana Barry




