×

# BOBPRIME - Editorial

Author: Sarvesh Mahajan
Tester: Sai Sandeep

MEDIUM-HARD

# PREREQUISITES:

Inclusion-Exclusion,Mobius Function,Binary search

# PROBLEM:

Define degree of a number is the highest power of a prime in its prime factorisation. A bob-prime is a number having prime degree. Find kth smallest bob-prime.

# QUICK EXPLANATION:

Binary search for the answer. Denote f(x,deg) as the number of numbers <= x , having degree >= deg. f(x,deg) can be found using inclusion-exlusion or mobius function.

# EXPLANATION:

Let's convert the problem into a counting problem. Finding kth bob-prime is same as finding the first x such that there as less than or equal to k bob-primes less than it. Therefore, we can do a binary search for this x and the problem turns into finding the number of bob-primes less than a given number. The problem constraints guarantee that the answer is always < $10^{10}$. So this can be the upper limit for the binary search.
Let's say we have a function g(x,deg) which returns the number of numbers<=x having degree=deg. Then we can use the following pseudo-code to calculate the answer.

 def get(x): # Returns number of bob-primes<=x for(p in primes): ret+=g(x,p) return ret 

Note that we only need to iterate till primes<37 since 237 > 1010. Now the problem remains how to calculate g(x,deg).

# Calculating g(x,deg):

Let f(x,deg) return the number of numbers<=x having degree>=deg.
Then clearly g(x,deg)=f(x,deg+1)-f(x,deg).
f(x,deg) can be calculated by inclusion exclusion. We add the count of numbers<=x divisible by ${2^{deg}},{3^{deg}},{5^{deg}},{7^{deg}}$ and so on. But we are overcounting here. So we subtract the count of numbers<=x divisible by ${2^{deg}}{3^{deg}} etc.$

Therefore, f(x,deg)= $\lfloor{\frac{x}{2^{deg}}}\rfloor + \lfloor{\frac{x}{3^{deg}}}\rfloor + \lfloor{\frac{x}{5^{deg}}}\rfloor + ...- \lfloor{\frac{x}{2^{deg}3^{deg}}}\rfloor-\lfloor{\frac{x}{2^{deg}5^{deg}}}\rfloor- .... + \lfloor{\frac{x}{2^{deg}3^{deg}5^{deg}}}\rfloor...$

Note that the denominator grows very fast so the number of non-zero terms is relatively small. Also note that since deg>=2, we only need to consider primes till $10^{5}$, as any number greater than this will contribute only a zero term in the answer.

## Implementation details

We can calculate all prime numbers <= $10^{5}$ using sieve of Erastothenes.
We can generate the terms in denominator using recursion and prune the recursion tree by stopping when the denominator exceeds x. Also pre-compute values of prime powers<37. Refer author's solution for details.

Alternatively, if you are familiar with mobius function, you will notice that this inclusion-exclusion is implicit in the definition of mobius function. We can calculate the values of mobius function for all numbers <=$10^{5}$ and then,
f(x,deg)= $- \sum_{y=2}^{10^{5}} \mu (y) *(x/y^{deg})$.
For details regarding calculation of mobius function refer tester's solution.
Time Complexity: Let max denote the bob-prime corresponding to the largest value of k. Then time complexity is $O(T*log(max)*sqrt(max))$

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

1115
accept rate: 0%

19.5k348496536

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,047
×598
×79
×59

question asked: 29 Sep '16, 20:05

question was seen: 1,249 times

last updated: 16 Sep '17, 10:40