Cubic Square Skip


$2, 3, 5, 6, 7, 10, 11, 12, 13, \dots$ is the sequence of integers without all square and cube numbers. How to get the $2019^{th}$ number?  


Source: BdMO 2019 National Junior P5


Proof Based Problems  


  1 Upvote                    0 Downvote


Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

In this sequence,

$n$th term would be = $n+\lfloor \sqrt[2]{n} \rfloor+\lfloor \sqrt[3]{n} \rfloor - \lfloor \sqrt[6]{n} \rfloor+k$ where k is the number of square and cube from $n$ to $\lfloor \sqrt[2]{n} \rfloor+\lfloor \sqrt[3]{n} \rfloor - \lfloor \sqrt[6]{n} \rfloor$


Because, suppose there is a sequence $A=(a_1,a_2,a_3,...,a_n)$ and you remove $x$ terms and make it $B=(b_1,b_2,..b_{n-x})$


Now consider a term $a_i$ in $A$ which is also in $B$.

$a_i$ is $i^{th}$ position in $A$ and number of terms removed before $a_i$ is $y$


Now $i^{th}$ position in B would be $a_{i+y}$

Note that:

From $1$ to $n$ there are total $\lfloor \sqrt[2]{n} \rfloor+\lfloor \sqrt[3]{n} \rfloor-\lfloor \sqrt[6]{n}$


As there are $\lfloor \sqrt[2]{n} \rfloor$ square numbers,$\lfloor \sqrt[3]{n} \rfloor$ cubic and $\lfloor \sqrt[6]{n} \rfloor$ numbers both square and cubic from $1$ to $n$. (From set union theorem)


For this reason, as $1,2,3,...,n$ has been reduced by squares and cubic numbers,


$n^{th}$ term would be $n+\lfloor \sqrt[2]{n} \rfloor+\lfloor \sqrt[3]{n} \rfloor - \lfloor \sqrt[6]{n} \rfloor$

So, $2019^{th}$ term $=2019+\lfloor \sqrt[2]{2019} \rfloor+\lfloor \sqrt[3]{2019} \rfloor - \lfloor \sqrt[6]{2019} \rfloor+k$


$2019^{th}$ term $=2019+44+12-3+k=2072+k$

Here $k=1$($2025$ is a square)


Hence the $2019^{th}$ term would be $2073$.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial



Need a hint? Checkout the editorial.

View Editorial