# factoring very very big random “numbers”

This is a variation on the theme of a rather flawed question that I asked months ago.

Imagine a doubly infinite sequence, i.e. each member has a successor and a predecessor.

Grab one term of the sequence and toss a coin to decide which congruence class mod $2$ it belongs to; then all the terms are alternately even or odd. Then randomly assign it to a congruence class mod $2^2$, each having probability $1/2^2$ of being chosen, then similarly with $2^3$, then $2^4$, and so on.

Then randomly assign it to a congruence class mod $3$, each having probability $1/3$ of being chosen, then mod $3^2$, each having probability $1/3^2$ of being chosen, then $3^3$, etc.

Then do the same with powers of $5$.

And so on: do this with each prime number.

Notice that with probability $1$, there is no member $n$ of this sequence for which there is some prime number $p$ such that $n$ is divisible by all powers of $p$. I.e. the multiplicity of every prime factor as a divisor of every member of the sequence is finite.

Because the harmonic series diverges to $\infty$, the expected number of prime factors of any one of these objects is $\infty$, so they are like "very very big" (infinite) positive integers, each having a prime factorization.

• The choice of a congruence class mod 9 is not independent of the choice of a congruence class mod 3, and so on. So the probability that the "number" we're looking at is congruent to 7 mod 9 is of course $1/9$, but the conditional probability that it's congruent to 7 mod 9, given that it's congruent to 2 mod 3, is $0$. And so on . . . . . .
We are looking at one term of the sequence, and doing some assignments. What is happening to the other terms? And if we have decided that the term $a$ is $\equiv 0\pmod{3}$, can we decide that $a\equiv 4\pmod{9}$? If so, how often can we change our minds? I am having trouble grasping the process. – André Nicolas Jul 17 '12 at 2:26
OK, so we are woking with $a_0$. What about the consistency question. If we decide that $a_0$ is divisible by $5$, can we later decide it is congruent to $16$ modulo $25$? – André Nicolas Jul 17 '12 at 3:13
I suspect you already know this, since it's probably part of the motivation for this construction: Since you've basically modeled the standard heuristic treatment of primes, you can transfer all sorts of results from that. For instance, the probability of a given term still being "prime" after you've tossed coins up to $p$ goes as $1/\log p$, the density of twin "primes" follows the first Hardy–Littlewood conjecture, and so on... – joriki Jul 17 '12 at 6:29