Prime Sum

 Accept a number N up to 5 digits long in the positional numeral system formed by symbols 0, 1, ... 9, A, ..., Z. Also, accept another symbol S other than zero.

Considering N to be represented in the least base possible between 2 and 36, identify the smallest prime number greater than  N that contains at least one occurrence of S in it in base S + 1.

(Refer example section for a better understanding). Prime number should be identified with respect to Base 10 i.e. a regular prime number.

Constraints

  • Length of N <= 5
  • Max Base = 36
  • Face values for symbols:

Symbol => Value in base 10

0 => 0

1 => 1

2 => 2

….

9 => 9

A => 10

B => 11

….

Z => 35

Input Format

  • First line contains T, the number of test cases. Each test case contains:
  • One line containing two integers, N and S separated with space.

Output

  • Print the smallest prime number greater than or equal to N that contains at least one occurrence of S in it, in base S + 1.

Example Test Case 1

2
10 B
ZZ Z

Output

B
11Z

Explanation 1

The least possible base for N is 2 and its value in that base is 2. We want the smallest prime number in base 12 (1 more than the face value of B, 11) that contains symbol B and is greater than or equal to 2. The first few numbers in ascending order in base 12 containing face value B are B (value 11), 1B (value 1 * 12 + 11 = 23), 2B (value 2 * 12 + 11 = 35): of these the smallest number that is prime is 11, which is greater than N. Hence, the output is B.

Explanation 2

The least possible base for N is 36 and its value in that base is 35 * 36 ^1 + 35 = 1295. The first few numbers in ascending order in base 36 (1 more than the face value of Z, 35) containing face value Z and greater than N are 10Z (1 * 36^2 + 0*36^1 + 35 = 1331, non-prime), 11Z (1 * 36^2 + 1 * 36^1 + 35 = 1367, a prime). Hence, the output is 11Z.



Solution:



t = int(input())    #prime face

def isPrime(k):

    if(k==0 or k==1):

        return 0

    if(k==2 or k==3):

        return 1

    for i in range(2,int(k**0.5)+2):

        if(k%i == 0):

            return 0

    return 1

    

def toBase(x,b):

    n = x

    s=''

    ch="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    while n:

        t=n//b

        r=n%b

        s = ch[r]+s

        n = t

    return s

        


for T in range(t):

    ch="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

    N,S=input().split()

    base=ch.find(max(N))+1

    mn=int(N,base)

    sb=ch.find(max(S))+1

    while 1:

        if isPrime(mn) and S in toBase(mn,sb):

            print(toBase(mn,sb))

            break

        mn+=1

Comments

Post a Comment

Popular posts from this blog

Efficient Janitor

  The janitor of a high school is insanely efficient. By the end of the day, all of the waster from the trash cans in the school has been shifted into plastic bags which can carry waster weighting between 1.01 pounds and 3.00 pounds. All of the plastic bags must be dumped into the trash cans outside the school. The janitor can carry at most 3.00 pounds at once. One trip is described as selecting a few bags which together don't weigh more than 3.00 pounds, dumping them in the outdoor trash can and returning to the school. The janitor wants to make minimum number of trips to the outdoor trash can. Given the number of plastic bags, n and the weights of each bag, determine the minimum number of trips if the janitor selects bags in the optimal way. For example, given  n=5 , plastic bags weighing weights  [1.01, 1.99, 2.5, 1.5, 1.01] , the janitor can carry all of the trash out in 3 trips:  [1.01+1.99, 2.5, 1.5+1.01] Constraints 1 <= n <= 1000 1.01 <= weight <=...
Read more

Right Arrow Pattern

Write a program to print the Right Arrow Pattern. Input Format: Take an input Integer which is from stdin. Output Format: print Right Arrow pattern Example Input: 5 Output: ***** **** *** ** * ** *** **** ***** SOLUTION: n=int(input()) for i in range(n):     for j in range(2*i):      #for spaces as each i th row has 2*i spaces         print(" ",end="")     for k in range(n-i):     #for stars as each i th row has n-i stars         print("*",end="")          print("")                     # half pattern is completed here for i in range(2,n+1):     #range started from 2 as the single star at middle is already                                         ...
Read more

X Pattern

  Write a program to take String if the length of String is odd print X pattern otherwise print INVALID. Input Format: Take a String as input from stdin. Output Format: print the desired Pattern or INVALID. Example Input: edyst Output: e t d s y d s e t SOLUTION: s=input() l=len(s) if(l%2 != 0): for i in range(0,l): j=l-i-1 for k in range(0,l): if(k==i or k==j): print(s[k],end="") else: print(end=" ") print("") else: print("INVALID")
Read more