SOLUTION: Cai writes down the list of positive integers, excluding squares and cubes. His sequence starts 2, 3, 4, 6, 7, 10, 11, ... What is the 10000th term in Cai's list?

Algebra ->  Sequences-and-series -> SOLUTION: Cai writes down the list of positive integers, excluding squares and cubes. His sequence starts 2, 3, 4, 6, 7, 10, 11, ... What is the 10000th term in Cai's list?      Log On


   

Question 1207578: Cai writes down the list of positive integers, excluding squares and cubes. His sequence starts
2, 3, 4, 6, 7, 10, 11, ...
What is the 10000th term in Cai's list?
Found 2 solutions by ikleyn, Edwin McCravy:
Answer by ikleyn(52754) About Me  (Show Source):
You can put this solution on YOUR website!
.
Cai writes down the list of positive integers, excluding squares and cubes. His sequence starts
2, 3, 4, 6, 7, 10, 11, ...
What is the 10000th term in Cai's list?
~~~~~~~~~~~~~~~~~~~~~


The problem in the post is posed incorrectly.

Indeed, the Cai's final list contains the number 4 (as it is written in the post),
which is the square and, THEREFORE, must be excluded.



Answer by Edwin McCravy(20054) About Me  (Show Source):
You can put this solution on YOUR website!
Ikleyn, this student simply typed a 4 when he or she meant to type a 5. 

He/she meant 2, 3, 5, 6, 7, 10, 11, ...  and accidentally typed a 4 instead 
of a 5.

Here is my solution:

We want the 10000th positive non-square-non-cube integer. Let's abbreviate
"positive-non-square-non-cube integer" as "PNSNCI". 

Let's begin by finding the number of PNSNCI's less than or equal to 10000.
We start with the 10000 integers, 
1,2,...,9999,10000.
Then since sqrt%2810000%29=100, we will subtract the 100 squares, 
12,22,...,992,1002,

Then since root%283%2C10000%29=%2221.5...%22, we will also subtract the 21 cubes, 
13,23,...,203,213,

But when we have subtracted those, we will have subtracted the squares that are
also cubes twice!  So we must count those "square-cubes" and add them back to
the total so that, in effect, we will have subtracted them only once, not twice. 
Note that every "square-cube" is a 6th power.

Since root%286%2C10000%29=%224.6...%22, we will add back the 4 square-cubes, 
16,26,36,46.

[Here, notice that we are using the thinking process of the inclusion-exclusion
principle.]

So the number of PNSNCI's from 1 to 10000 is 10000-100-21+4 = 9883

So the 9883rd term is 9999, (because 10000 is a square).

However we want the 10000th term, not the 9883rd term. We need some more PNSNCI's 

We find that the next square above 10000 is 1012=10201
We find that the next cube above 213 is 223=10648
We find that the next 6th power (square-cube) is 56=15625.
The least of these is 10201.
Therefore all the positive integers 9883,9884,...,10200, are PNSNCI's!

So let n be the 10000th term. As long as n does not exceed 10200, we can
eliminate the same squares and cubes from n as we eliminated from 10000 to find
the 9883rd term. So

n-100-21+4 = 10000
n-117 = 10000
n = 10117. 

We see that 10117 does not exceed 10200. [If it had we would have had to include
at least another square to eliminate.] 

Now let's check.

We begin with 1,2,...,10016,10117.
Then since sqrt%2810117%29=%22100.5...%22, we subtract the 100 squares, 
12,22,...,992,1002,

Then since root%283%2C10117%29=%2221.6...%22, we subtract the 21 cubes, 
13,23,...,203,213,

But by subtracting those, we will have subtracted the squares that are also
cubes twice!  So we must count those square-cubes and add them back to the
total.  Every "square-cube" is a 6th power.

Since root%286%2C10117%29=%224.6...%22, we add back the 4 square-cubes, 
16,26,36,46.

So 10117-100-21+4 = 10000.

So that shows that the 10000th PNSNCI is 10117.

Edwin