- 06 Dec '02 23:23Given 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.) - 07 Dec '02 21:57an 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. - 07 Dec '02 23:16 / 3 editsto 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.