# This script essentially uses ideas of Giovanni Resta. # Many thanks to him for sharing them! # The values of b, q, m, M indicated on the 16th line from the end of the script # can be replaced with other natural numbers satisfying 1<b<q, m<M. When running # the script, an interval containing m and M is examined and all natural numbers # n in it are found with the property that rebasing of n from base b to base q # produces a multiple of n. Running the script with the presently given values of # b, q, m, M shows that a(121)=2*a(119). Running it after replacing the values of # m and M with 4820*10**11 and 8703*10**11, respectively, shows the correctness # of the value of a(122) given in the b-file, and running the script with values # 8702*10**11 and 10**15 of them shows the non-existence of other terms <10^15. def rebase(x): """Does rebasing of x from base b to base q. For any natural number x, returns the one whose base q representation is by the same sequence of digits as the base b representation of x. """ u,y,i=x,0,0 while u>0: y=y+multiplied_q_to[i][u%b] u,i=u//b,i+1 return y def some_between(left,right): """Looks for a number n between left and right such that rebase(n) is a multiple of n. For any positive integers left and right with left<=right, returns some integer n such that left<=n<=rb and rebase(n) is a multiple of n, if such an n exists, otherwise returns 0. """ Left=rebase(left) if Left%left==0: z=left else: if left==right: z=0 else: Right=rebase(right) if Right%right==0: z=right else: st,z=[(left,Left)],0 st.append((right,Right)) while len(st)>1: l,L,r,R=st[0][0],st[0][1],st[1][0],st[1][1] if (L//r==R//l) or (r==l+1): st[0:1]=[] else: new=(l+r)//2 New=rebase(new) if New%new==0: z=new st[:]=[] else: st[0:2]=[st[0],(new,New),st[1]] return z def least_between(left,right): """Looks for the least n between left and right such that rebase(n) is a multiple of n. For any positive integers left and right with left<=right, returns the least integer n such that left<=n<=rb and rebase(n) is a multiple of n, if such an n exists, otherwise returns 0. """ if rebase(left)%left==0: z=left else: y=some_between(left,right) if y>0: while y>0: z=y y=some_between(left,y-1) else: z=0 return z def all_between(left,right): """Consecutively prints all n between left and right such that rebase(n) is a multiple of n.""" z=left while z<right: z1=least_between(z,right) if z1>0: print(z1) z=z1+1 else: z=right b,q,m,M=2,3,3832*10**11,4821*10**11 multiplied_q_to,i=[],0 while b**i<M+100: v=[] for k in range(b): v.append(k*q**i) multiplied_q_to.append(v) i=i+1 step=(M-m)//100 print("Starts checking.") rgt=m-1 for j in range(100): lft=rgt+1 rgt=lft+step all_between(lft,rgt) print(str(j+1)+" percent completed. Checked to "+str(rgt))