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?

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.