Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!

Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.

Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.

One problem with prime numbers is that there are too many of them. Let's introduce the following notation: π(n) — the number of primes no larger than n, rub(n) — the number of palindromic numbers no larger than n. Rikhail wants to prove that there are a lot more primes than palindromic ones.

He asked you to solve the following problem: for a given value of the coefficient A find the maximum n, such that π(n) ≤ A·rub(n).


-----Input-----

The input consists of two positive integers p, q, the numerator and denominator of the fraction that is the value of A ($A = \frac{p}{q}$, $p, q \leq 10^{4}, \frac{1}{42} \leq \frac{p}{q} \leq 42$).


-----Output-----

If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).


-----Examples-----
Input
1 1

Output
40

Input
1 42

Output
1

Input
6 4

Output
172

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Number theory

Implementation

Complete search


Solutions:
import sys
input = sys.stdin.readline

def rr(n):
	a = set([])
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			a.add(p)
	return a

def pal(a):
	if str(a) == str(a)[::-1]:
		return 1
	return 0
(p, q) = list(map(int, input().split()))
n = 1500000
a = rr(n)
b = []
c = 0
d = 0
for i in range(1, n + 1):
	if i in a:
		c += 1
	d += pal(i)
	b.append([c / d, i])
e = -1
for i in range(len(b) - 1, -1, -1):
	if b[i][0] <= p / q:
		e = b[i][1]
		break
if e == -1:
	print('Palindromic tree is better than splay tree')
else:
	print(e)


n = 12 * 10 ** 5
(p, q) = map(int, input().split())
pr = [0] * n
pr[1] = 1
for i in range(2, n):
	if pr[i] == 1:
		continue
	for j in range(2 * i, n, i):
		pr[j] = 1
res = 'Palindromic tree is better than splay tree'
rub = pi = 0
for i in range(1, n):
	if pr[i] == 0:
		pi += 1
	if str(i) == str(i)[::-1]:
		rub += 1
	if pi * q <= rub * p:
		res = i
print(res)


(p, q) = map(int, input().split())
n = 1200000
t = [0, q] * 600000
for i in range(3, 1096, 2):
	if t[i]:
		for j in range(i * i, n, i):
			t[j] = 0
(t[1], t[2]) = (-p, q - p)
for i in range(3, 10):
	t[i] -= p
for i in range(1, 1000):
	u = str(i)
	v = u[::-1]
	for j in '0123456789':
		k = int(u + j + v)
		if k < n:
			t[k] -= p
	t[int(u + v)] -= p
j = s = 0
for (i, q) in enumerate(t):
	s += q
	if s <= 0:
		j = i
print(j)


pr = [0] * 1300000

def prime():
	pr[1] = 1
	for i in range(2, 1300000):
		if pr[i] == 1:
			continue
		for j in range(2 * i, 1300000, i):
			pr[j] = 1

def palindrom(s):
	s = str(s)
	return s == s[::-1]
(p, q) = list(map(int, input().split()))
res = 'Palindromic tree is better than splay tree'
rub = 0
pi = 0
prime()
for i in range(1, 1200000):
	if pr[i] == 0:
		pi += 1
	if palindrom(i):
		rub += 1
	if pi * q <= rub * p:
		res = i
print(res)


n = 2 * 10 ** 6 + 10 ** 5
(p, q) = list(map(int, input().split(' ')))
pi = 0
si = 0
pr = [0] * n
pr[1] = 1
for i in range(2, n):
	if pr[i] == 0:
		for j in range(i * i, n, i):
			pr[j] = 1
res = 'Palindromic tree is better than splay tree'
for i in range(1, n):
	if pr[i] == 0:
		pi += 1
	j = str(i)
	if j == j[::-1]:
		si += 1
	if q * pi <= si * p:
		res = i
print(res)


import sys
(p, q) = map(int, sys.stdin.readline().split())

def prime(n):
	for div in range(2, int(n ** 0.5) + 1):
		if n % div == 0:
			return False
	return True

def palindrom(n):
	n = str(n)
	for pos in range((len(n) + 1) // 2):
		if n[pos] != n[-1 - pos]:
			return False
	return True

def findMaxN(p, q):
	A = p / q
	n = 1
	pN = 0
	rubN = 1
	checkAgain = False
	while True:
		n += 1
		if prime(n):
			pN += 1
			checkAgain = True
		if palindrom(n):
			rubN += 1
			checkAgain = True
		if checkAgain:
			checkAgain = False
			if pN > A * rubN:
				break
	good_n = n - 1
	check_to = n + 10000
	delta = 0
	last_good = False
	while n < check_to:
		n += 1
		delta += 1
		if prime(n):
			pN += 1
			checkAgain = True
		if palindrom(n):
			rubN += 1
			checkAgain = True
		if checkAgain:
			checkAgain = False
			if pN <= A * rubN:
				good_n = n
				check_to += delta
				delta = 0
				last_good = True
			elif last_good:
				last_good = False
				good_n = n - 1
	return good_n

def doTest():
	assert findMaxN(1, 1) == 40
	assert findMaxN(1, 42) == 1
	assert findMaxN(6, 4) == 172
doTest()
print(findMaxN(p, q))


(p, q) = map(int, input().split())
L = 2 * 10 ** 6 + 10 ** 5
P = [0] * L
for i in range(2, L, 1):
	if P[i] == 0:
		for j in range(i * i, L, i):
			P[j] = 1
ans = -1
P[1] = 1
cnta = 0
cntb = 0
for i in range(1, L):
	if P[i] == 0:
		cnta += 1
	j = str(i)
	if j == j[::-1]:
		cntb += 1
	if cnta * q <= p * cntb:
		ans = i
print(ans)


(p, q) = (int(x) for x in input().split())
top = 1200000
isPrime = [1] * top
isPrime[1] = 0
palindromic = 1
res = 1
for i in range(2, top):
	if str(i) == str(i)[::-1]:
		palindromic += 1
	if isPrime[i]:
		for j in range(i * i, top, i):
			isPrime[j] = 0
	isPrime[i] += isPrime[i - 1]
	if q * isPrime[i] <= p * palindromic:
		res = i
print(res)


def primes2(limit):
	if limit < 2:
		return []
	if limit < 3:
		return [2]
	lmtbf = (limit - 3) // 2
	buf = [True] * (lmtbf + 1)
	for i in range((int(limit ** 0.5) - 3) // 2 + 1):
		if buf[i]:
			p = i + i + 3
			s = p * (i + 1) + i
			buf[s::p] = [False] * ((lmtbf - s) // p + 1)
	return [2] + [i + i + 3 for (i, v) in enumerate(buf) if v]
ps = primes2(12 * 10 ** 6)

def rub2(n):
	lst_odd = []
	lst_even = []
	for head in range(1, n):
		head_str = str(head)
		tail_str = head_str[::-1]
		lst_even.append(int(head_str + tail_str))
		lst_odd.append(int(head_str[:-1] + tail_str))
	lst = lst_odd + lst_even
	lst.sort()
	return lst
rs = rub2(12 * 10 ** 2)
(p, q) = map(int, input().split())
idxp = len(ps) - 1
idxr = len(rs) - 1
pi = ps[idxp]
ri = rs[idxr]
while q * (idxp + 1) > p * (idxr + 1):
	if pi < ri:
		idxr -= 1
	elif pi > ri:
		idxp -= 1
	else:
		idxr -= 1
		idxp -= 1
	prev_pi = pi
	prev_ri = ri
	pi = ps[idxp]
	ri = rs[idxr]
print(max(prev_pi - 1, prev_ri - 1))


def is_palindrome(num):
	copia = num
	if num < 10:
		return True
	nums = []
	while True:
		nums.append(copia % 10)
		copia //= 10
		if copia == 0:
			break
	digitos = len(nums) // 2
	j = len(nums) - 1
	for i in range(digitos):
		if nums[i] != nums[j]:
			return False
		j -= 1
	return True
primes = [True] * 2000000
primes[0] = False
num = input().split()
num = [int(num[0]), int(num[1])]
resultado = 0
i = 0
countPrimes = 0
countPali = 0
while i < 2000000:
	if primes[i]:
		countPrimes += 1
		if i * i < 2000000:
			for j in range(i, 2000000, i + 1):
				primes[j] = False
	if str(int(str(i + 1)[::-1])) == str(i + 1):
		countPali += 1
	res = countPali * num[0] / num[1]
	if res >= countPrimes:
		resultado = i + 1
	i += 1
if resultado == 0:
	print('Palindromic tree is better than splay tree')
else:
	print(resultado)


def main():
	(p, q) = list(map(int, input().split()))
	lim = 1179860
	sieve = [0, q] * (lim // 2)
	for i in range(3, int(lim ** 0.5) + 1, 2):
		if sieve[i]:
			for j in range(i * i, lim, i):
				sieve[j] = 0
	(sieve[1], sieve[2]) = (-p, q - p)
	for i in range(3, 10):
		sieve[i] -= p
	for s in map(str, list(range(1, 1000))):
		ss = (s, s[::-1])
		for m in ('', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'):
			i = int(m.join(ss))
			if i < lim:
				sieve[i] -= p
	res = b = 0
	for (i, a) in enumerate(sieve):
		b += a
		if b <= 0:
			res = i
	print(res)

def __starting_point():
	main()
__starting_point()


(p, q) = map(int, input().split())
n = 1200000
s = [0] * n
t = [q] * n
for i in range(3, int(n ** 0.5) + 1, 2):
	(u, v) = (i * i, 2 * i)
	if t[i]:
		t[u::v] = [0] * ((n - u - 1) // v + 1)
for i in range(4, n, 2):
	t[i] = 0
t[0] = t[1] = 0
for i in range(1, 10):
	s[i] = p
for i in range(1, 1000):
	a = str(i)
	b = a[::-1]
	for j in '0123456789':
		c = int(a + j + b)
		if c < n:
			s[c] = p
	s[int(a + b)] = p
for i in range(n - 1):
	t[i + 1] += t[i]
for i in range(n - 1):
	s[i + 1] += s[i]
j = 0
for (i, (u, v)) in enumerate(zip(t, s)):
	if u <= v:
		j = i
print(j)


crivo = [True] * 2000001
crivo[0] = False
crivo[1] = False
for i in range(2, 2001):
	if crivo[i]:
		for j in range(i * i, 2000001, i):
			crivo[j] = False
(a, b) = map(float, input().split())
prime = 0
palindromo = 0
control = False
y = -1
for i in range(1, 2000000):
	if crivo[i]:
		prime += 1
	if str(int(str(i)[::-1])) == str(i):
		palindromo += 1
	if palindromo * (a / b) >= prime:
		y = i
if y >= 0:
	print(y)
else:
	print('Palindromic tree is better than splay tree')