Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. Standard member royalchicken
    06 Dec '02 23:23
    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.)
  2. Donation Acolyte
    Now With Added BA
    07 Dec '02 09:18 / 1 edit
    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?
  3. Standard member royalchicken
    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

    i have a function that does estimate this. solving this one took 4 weeks.
  4. Standard member royalchicken
    07 Dec '02 23:16 / 3 edits
    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)


    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.