More sensible heuristics

If you’re not familiar with the problem I’m semipublicly trying to solve, please start reading here. Coming to think about it, this is basically just another polymath-project. With the only difference that not a lot of people participate Hopefully that’ll change though. Anyway, the heuristics and assumptions in the previous post may seem a bit weird, so I try to make things more senseful here; let $n$ be given. Assume $a_ip_i^{k_i} \le n < (a_i+1)p_i^{k_i}$ with $1 \le a_i < p_i$ and where the $p_i$ run over all primes such that $2 < p_i < n$ . Then $g_n = 1$ if, and only if $p_i$ does not divide $X_{a_i}$ for all $i$ . Let $f(p)$ be the amount of $a$ for which $a < p$ and $p | X_a$ (so $f(p)$ is the function we want an decent upper bound on). Then the ‘chance’ that $p$ doesn’t divide $X_n$ (assuming for simplicity that $P(a_i = x) = \dfrac{1}{p-1}$ for all $x$ , $1 \le x \le p-1$ ), equals $\dfrac{p - 1 - f(p)}{p - 1}$ . The reasonable assumption (and possibly not even that hard to make rigorous) seems that $a_i$ and $a_j$ are independent for $i \neq j$ . So the ‘chance’ that $p_i$ does not divide $X_{a_i}$ for all $i$ , should be $\displaystyle \prod_{2 < p_i < n} \left(1 - \dfrac{f(p)}{p-1}\right)$ . And if we have a good upper bound on $f(p)$ , say $f(p) = O(\log p)$ , then we should be able to show that this product doesn’t go to $0$ fast enough to prevent $g_n = 1$ from happening.

About these ads

This entry was posted on October 20, 2010 at 20:05 and is filed under Problem Solving. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Woett's Blog

More sensible heuristics

Like this:

Leave a Reply Cancel reply

Follow “Woett's Blog”