More thinking about number bases.
So...ok, I was reacting with surprise that all these prime numbers, when you square them and subtract 1 you get a number divisible by 24, so dividing by 24 is fairly easy in every prime base so far.
Turns out that's just a rule That's true for every prime (other than 2 and 3). Consider...
p^2 - 1 = (p+1)(p-1)
Since there is a number divisible by 3 once every 3, and since p is not divisible by 3, one of p+1 or p-1 is divisible by 3.
Both p+1 and p-1 by definition are divisible by 2. Because they are two consecutive even numbers, this ALSO means one of them is divisible by 4.
Therefore (p+1)(p-1) will
always be divisible by 2*4*3 = 24.
---
OK, so there's one other interesting observation I had.
I started looking at factorials, and how factorials look in various bases. This is actually the first time I've been impressed with base 12, cause, take 10 factorial, for example, it's got 2 * 4 * 2 * 8 * 2 (from 2, 4, 6, 8, and 10) = 2^8. And it's got 3 * 3 * 9 (from 3, 6 and 9) which is 2^4. So we end up with four leading zeroes, and then just 5*5*7. (Which in base 12 is like...127
And I started wondering if this is a general property. Like if you take factorial(x) will you in general have roughly twice as many 2s and 3s in the divisor. And......the answer is actually yes. Let's go through a proof.
So...every second number is divisible by 2. So that's one two for every 2 numbers, 1/2.
But also, every fourth number is divisible by 4, which means divisible by an extra 2. So there's an extra 2 for every 4 numbers, add 1/4 density.
And so on and so forth. divisible by 8 numbers add another two in every 1/8 numbers.
Which gives us...
1/2 + 1/4 + 1/8 ....
But we know the formula for
1 + a + a^2 ... = 1/(1-a)
Therefore on average the density of 2s is
1/2 * (1/(1-1/2) = 1
There is on average 1 two divisor in every number.
And in general for any number this will be
1/n * (1/(1-1/n)) = 1/n * (n/(n-1)) = 1/(n-1)
So for example, for 3 we get a density of 1/2
On average the density of 3 prime factors is once every two numbers.
For 5 we get 1/4. There is a 5 prime factor once every four numbers
For 7 we get 1/6. There is a 7 prime factor once every six numbers.
So the next base up that would get all the ratios right for factorials after base 12 would be 2^4 * 3^2 * 5^1 = 720. Yep, base 720, that would be uhh...large. Incidentially 720 is also 6 factorial.
---
OK, one last observation.
I've been discussing how b+1 has special properties, the number expressed as "11" in any base, and this stems partially from the fact that (b+1)*(b-1) = b^2 - 1.
But there's another equation like that.
b^3 - 1 = (b-1)*(b^2+b+1)
So like "111" should have some special properties too. Only going to be relevant for smaller bases, but lets see if I can figure this out.
Um...yeah, so divisibility test...just replace your b^3 with b^3 - 1 right? So we have 999, which we know is divisible by 111, so we're left with a +1 three digits over.
So for a six digit number cdefgh, we can reduce this to a three digit number (f+c)(g+d)(h+e), and then if that is divisible by 111 then you are good. And then for digits 7-9 you end up adding.
Hmm...this is still a bit disappointing, though as a trick, cause we need to do 3 digit addition and subtraction. With 11 we got to do single digit addition. Can I not reduce this at least to double digit somehow?
k = b^2 + b + 1
b^2 = k - b - 1
xb^2 + yb + z = k + (y-x)b + (z-x)
OK, so we take the leading digit, and subtract it from the first two digits.
Um...is this even useful? OK, let me try a base 10 example, just multiply a random number by 111, get 264573717
So 9 digit number, let's reduce this to a 3 digit number
front digit: 2+5+7 = 14
middle digit: 6+7+1 = 14
final digit: 4+3+7 = 14
And then...well yeah, that's divisible by 111. And if you subtract the front digit from the other two, you get 00.
OK, I mean, that actually doesn't seem so bad as a divisibility test.
And obviously 1/111 has a reasonably nice repeat pattern. 0.009009...
OK, I guess for small bases at least we should take a look at the "111" number to see if it's anything highly useful.
2: 111 is 7. But it's also 8-1 so yeah, already knew binary handled 7 well.
3: 111 is 13. OK yes, we did previously establish that 13 divides fairly nice in base 3.
4: 111 is 21. I mean, 21 not a super important number, but an additional freebie for base 2 essentially. Base 2 already handles 3 and 7 reasonably nicely, but I guess it wasn't guaranteed to combine them nicely, so yeah, there you go, 1/21 has a nice simple pattern too.
5: 111 is 31. Eh, it's a prime. Not a very useful prime.
6: 111 is 43. Also a prime. Also not a very useful prime.
7: 111 is 57. 19*3. Also not very nice or useful.
8: 111 is 73. Again, mostly just some free bonuses for base 2. But...not the most useful prime.
9: 111 is 91. 7*13. Nothing really new. Base 3 already handles 13 well, and this is so large compared to 7 so it's not even that big of a help. Although I guess it does let you reduce the divisibilty test of 7 to a...two digit number base 9 (four digit number base 3). Eh...better than nothing I guess.
10: 111 is 111. 3*37. Meh. Base 10 is already decent at handling 3, and handling 37 is just not that helpful.
11: 111 is 133. 7*19. Well, ok, this is probably one of the reasons why 1/7 is not so bad in base 11. This should also mean that 1/19 is not so bad in base 11.
12: 111 is 157. A mediocre prime.
13: 111 is 183. 3*61. Eh, nah, 13 already has much easier ways to test for 3.
14: 111 is 211. Not a very useful prime.
Wow, ok, well, the identity exists, but it's mostly not very useful because 111 is always odd in every base, and often just a large rarely used prime, or something the base can already handle some easier way.
And it's a bit redundant looking at 1111, because 1111 in every base = 101*11. Numbers I typically already do look at.
Actually, something that's jumping out at me as a little weird is that none of these are divisible by 5. In fact, let me check...yeah, out to 40 none of these are divisible by 5. None of these are divisible by 11 either. We see 3, 7, 13, 19. None of these are divisible by 17. None of these are divisible by 23. What the heck? What is this pattern?
---
OK, let's look at 5, and specifically mod 5.
1^2 = 1
2^2 = 4
3^2 = 4
4^2 = 1
f(x) = x^2 + x + 1
f(1) = 3
f(2) = 2
f(3) = 3
f(4) = 1
Well that proves that it will never happen for 5, but what's the pattern here? Let's look at mod(11).
1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 5
5^2 = 3
6^2 = 3
7^2 = 5
8^2 = 9
9^2 = 4
10^2 = 1
Mmm...well I can see that none of these work, but I'm not seeing the pattern. Maybe try reframing this as f(x) = x*(x+1)
f(0) = 0
f(1) = 2
f(2) = 6
f(3) = 1
f(4) = 9
f(5) = 8
f(6) = 9
f(7) = 1
f(8) = 6
f(9) = 2
f(10) = 0
So I mean, hmm, I notice it's symmetrical. Every number happens twice. f(1) = f(11-2). f(2) = f(11-3). Is this always true?
f(x) = f(k-x) mod(k)?
x(x+1) = (k-x)(k-x-1)?
We can cancel out the k stuff since that will disappear out the modulo. So we're left with
x^2 + x = x^2 + x
So ok yes, only half of the values will get used up.
OK, let's look at some primes where this does work.
3 works cause 1*2+1 = 3
7 works cause 2*3+1 = 7
13 works cause 3*4+1 = 13
19 works...why does 19 work? Hmm...let's look at the modulo.
f(1) = 2
f(2) = 6
f(3) = 12
f(4) = 1
f(5) = 11
f(6) = 4
f(7) = 18
19 works because 7*8 = 56. and 57 = 19*3.
23 doesn't work.
29 doesn't work.
31 works cause 5*6+1 = 31.
37 works because of 10*11+1.
43 works because of 6*7+1 = 43.
What the hell is this sequence? It's not alternating every second prime or anything? Hmm...searching for this sequence specifically, it seems to be this sequence:
https://oeis.org/A007645"Generalized cuban primes: primes of the form x^2 + xy + y^2"
or primes == 0 or 1 (mod 3)
So...yes "primes of the form x^2 + xy + y^2", that's basically my equation there, just with y=1, so this very much looks like the right track.
3, 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, 103
Testing up to 103, yes, all of these work.
On them being 1 mod 3...so...other than 2 and 3, all primes are of the form 6m+1 or 6m-1. Somehow all of the 6m+1 primes work for this, and all of the 6m-1 primes do not. Can I figure out why...?
Hmm...well anecdotally I do notice that x(x+1) is often divisible by 6. 2*3 = 6. 3*4 = 12. 5*6 = 30. 6*7 = 42.
OK, so for starters, the ones in this sequence that aren't divisible by 6, like 4*5 = 20. 1*2 = 2. 7*8 = 56. I notice that when you add one to these they seem to be divisible by 3. (3, 21, 57). Is this always true? (3k+1)(3k+2)+1 = (3k)^2 + 3(3k) + 3. Yes, this is always true. n^2 + n will always either be divisible by 6, or when it's not divisible by 6, n^2+n+1 is divisible by 3 (and thus not prime unless it's 3).
So that explains why n^2+n+1 can sometimes be a prime of the form 6m+1 and never be a prime of the form 6m-1. But how do we handle the cases where we need modulo rollover like 19?
n^2+n needs to be 18 (mod 19)
We find our answer in the form of 7*8 = 56 = 18 (mod 19).
Hmm...ok, so we roll over twice mod 19, and every time we roll over, we take -1 relative to if we just rolled with 18. So in this case we end up with -2. Since we're in a funny case of n where n is not divisible by 3, that means n^2+n+1 is divisible by 3, which by extension means n^2+n-2 is divisible by 6.
So ok, in the case where one of our multipliers is 3, and the modulo prime is of the form 6m+1, we will get n^2+n lining up with 6m+1. And all multipliers higher than this that we know of so far are of the form 6m+1, so you would roll all the way around.
What about an opposite case, a prime of the form 6m-1. Let's just take 17. We know that n^2+n+1 will never be 17, and we can similarly show that there will never be a multiple like 7 which allows 17 to work, as we will roll the modulo function exactly 6 times and be back to numbers that are only divisible by 3 or 6, and you can't add one to those to get a number of the form 6m-1. But what about the case of 3 being the only other divisor?
So we're looking for a reason why 3*(6m-1) can never be equal to n(n+1)+1 with 6m-1 being prime
We obviously need n(n+1) to not be divisible by 3 so that adding 1 to it will make it divisible by 3. So we've got n(n+1) = (3k+1)(3k+2) = 9k^2 + 9k + 2. And then we add 1 to get n(n+1)+1.
Divide both sides by 3.
Which leaves us with 6m-1 = 3k^2+3k + 1
Moving the -1 to the other side we have
6m = 3k^2+3k +2
But that right side is definitely not divisible by 3.
OK cool, well, I don't know how to prove that all primes 6m+1 have a solution, but I am at least convinced primes of the form 6m-1 can never be one of the divisors.
Anyway, so yeah, longwinded way of showing 111 in every base will often be kinda not very useful, and can only have prime factors in the form of 3 and 6m+1.
