power factorability

Given two natural numbers n and k, can you tell me approximately how many of the
integers <= n are not divisble by the kth power of an integer? this must be
done in such a way that your formula/approximation gets arbitrarily close to the
correct answer as n increases.

(example: if n=10, k=2, then we must find all of the integers <=10 that are not
divisible by a square. these are 2,3,5,6,7,10.)

I know the number of primes =< n tends towards some function of n as n tends to infinity,
but I can't remember the function. Is this useful for obtaining the solution?

an interesting idea. i will give you a hint:

1. think in terms of zeta functions (this is the primary relationship that you
could say this has with the density of primes, although this problem is slightly
simpler)

i have a function that does estimate this. solving this one took 4 weeks.

to answer your question about what function approximates the frequency of
primes, let q(x) = # of primes <=x. (x is a continuous vairable). then:

1. q(x) ~ x/log x (to the base e)

2. q(x) = li(x) + O(f(x)) (for some decreasing smal function f)

3.the famous Riemann Hyptothesis can be rephrased to:

q(x) = li(x) + O(x^(1/2).log x)


where:

li(x) = INTEGRAL(1 to x) dt/log t

this has little to do with the answer to my puzzle except at a very complicated
level; a theorem which i had to prove to solve my puzzle can be considered as
"deep" as the above result.