Python实现基础数学的解法之进位问题验证
例题：我们用S(n)表示正整数n的各位数字之和，有一个正整数a使得S(a），S(a+1)的最大公约数是一个奇素数，求最小的a、解：设a=c1c2 … ct99…9(k个9) k>=0 0<=ct<9 则a+1=c1c2 … ct-1(ct+1)00…0 所以 S(a)=c1+c2+ … +ct+9k S(a+1)=c1+c2+ … +ct+1 所以 S(a)=S(a+1)+9k-1 所以 d=(S(a),S(a+1))=(S(a),9k-1) =>d|9k-1 即求最小的a使d为奇素数，则k尽量小 若k=1 则d|8 d不存在 若k=2 则d|17 =>d 17 则 17|S(a+1)=c1+c2+ … +ct+1 => c1+c2+ … +ct>=16 =>a>=8899 若k>=3 则d|26 =>d=13 则13|S(a+1)=c1+c2+ … +ct+1 => c1+c2+ … +ct>=12 =>a>=48999 若k>=4 则a>=19999 综上所述 a最小值为8899 以下为验证a的最小值python编程:
st=[]for l in range(3,18): st.append(l) for o in range(2,l): if l%o==0 and l in st: st.remove(l)for i in range(0,10000): a=0 b=0 x=len(str(i)) y=len(str(i+1)) for j in range(1,x+1): a=i//10**(j-1)%10+a for u in range(1,y+1): b=(i+1)//10**(u-1)%10+b g=1 for k in range(int(a),1,-1): if a%k==0 and b%k==0: g=k if g in st: print(i) break
运行结果：