# 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))