My Journey with the Average Divisability of Numbers

One day I was playing with some numbers (sometimes boredom is good for finding creative stuff to do, which school creates the perfect environment for), I noticed that for a positive odd integer n; \(n^2 - 1\) can always be divided by 4 (not 2). This is almost irrelevant to what I actually found, but this started something, which is me trying to mass test this with code. I wrote some code in C (actually I first wrote in Python, but then switched to C for the great performance boost), the results were unexpected to me. Indeed all of them divide by 4 (and also 8), but this was because the structure of odd numbers which is 2n - 1, so 1 minus the square of for this number would be:

$$ 4n^2 - 4n = 4(n^2 - n) $$

If n is an odd number the square of it would also be odd, and substracting odd numbers from odd numbers gives us even numbers, in the case that is is even, then obviously the square also would be, and subtracting even from even also gives us even numbers. So in every case it must be divisible by \(2^3\), or 8.

What came next was surprising to me though. When I switched from looking for twos to threes (checking for 3, 9, 27 etc.) The average of how many times the number could be divided was 1, and when I switched to fives it was 0.5, and for sevens it was 1/3. It seemed that the average for the nth prime was \(\frac{1}{p-1}\). I was just dreaming, it wasn’t about primes, it was about odd numbers because odd numbers weren’t messed up by the squares like even ones. After a while thinking about this I decided to try this on plain numbers (without the squaring and decrementing part), now it was more clear, for any number x to check the number of perfect divisions, the average was \(\frac{1}{x-1}\). At this point text was getting hard and I wanted this on formula, so I wrote it like this:

$$ \lim _{n \to \infty} $$ $$ n! \parallel x^y $$ $$ \frac{1}{x-1} = \frac{y}{n} $$

I was eagerly searching for a reason why this could have happen, I was searching the internet only to find nothing. One day, it came to me, and here is the explanation: It is about probability actually. Let’s select 3 as the number to check. The probability that any integer is a multiple of 3 is 1/3, and the probability of it being a multiple of 3^2 is 1/9… Some of you might have understood where this is going, the sum of infinite geometric series are equal to (1/3) / (1 - 1/3) which is equal to 1/2 or 0.5.

When I finally found the reason for this I noticed how much I spent time on computing the numbers, I tried to not talk much about the computing of these numbers but I spent too much time on writing the C code and making it run on bigger scales. At the end making it run on bigger scales didn’t give me much, I just saw the average get closer and closer to 0.5, or the number I expected. Instead of trying to compute, if I thought on the reason from the start I could have found this earlier. This has been a lesson for me and I wanted to share it.