# This script essentially uses ideas of Giovanni Resta. # Many thanks to him for sharing them! 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,i=left,s+1 while z<right: z1=least_between(z,right) if z1>0: print(str(i)+" "+str(z1)) i=i+1 z=z1+1 else: z=right b,q,m,M,s=2,6,0,10**7,1 multiplied_q_to,i=[],0 while b**i<M-1: v=[] for k in range(b): v.append(k*q**i) multiplied_q_to.append(v) i=i+1 print(str(s)+" 0") all_between(1,M-1)