# power factorability

royalchicken
Posers and Puzzles 06 Dec '02 23:23
1. royalchicken
CHAOS GHOST!!!
06 Dec '02 23:23
Given two natural numbers n and k, can you tell me approximately how many of the
integers &lt;= 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

(example: if n=10, k=2, then we must find all of the integers &lt;=10 that are not
divisible by a square. these are 2,3,5,6,7,10.)
2. Acolyte
07 Dec '02 09:181 edit
I know the number of primes =&lt; 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?
3. royalchicken
CHAOS GHOST!!!
07 Dec '02 21:57
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.
4. royalchicken
CHAOS GHOST!!!
07 Dec '02 23:163 edits
primes, let q(x) = # of primes &lt;=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
&quot;deep&quot; as the above result.