Coming home I whipped up a python scriplet that basically did that for the first million digits and found that none of them were divisible by 3 (they weren't divisible by 7 either but I figured I would stick with 3 first). Now we know that n^2 is sometimes divisible by 3 (9, 36, 81 all being examples) and we know that a series that is always divisible by 3 is 3m (two series never divisible by three are 3m+1 and 3m+2). So from this I infer that the series n^2+1 only falls inside of the series 3m+1 and 3m+2 and never on 3m... and n^2 falls on 3m or 3m+1 (since if it fell on 3m+2 then n^2+1 would push those values to 3m). Ok but why?
Looking over the series I came up with the following:
n 1 2 3 4 5 6 7 8 9 10
n^2 1 4 9 16 25 36 49 64 81 100
m{3m+1/3m} 0 1 3 5 8 12 16 21 27 33
diff between m 1 2 2 3 4 4 5 6 6
Ok now I just have more silly numbers and probably a wild goose chase but it is interesting that the series of 3m/3m+1 growth grows in a regular pattern. Anyway, just an odd thing non-fedora related (i hope).
6 comments:
n^2 + 1 = 3m would mean that 2 is a quadratic residue mod 3. But there are only (p - 1)/2 quadratic residues for an odd prime modulus. For 3, the sole quadratic residue is 1...
To see why, look at the field Z/pZ. The squares 1^2, 2^2,..., (p-1)/2 ^2 enumerate all the quadratic residues mod p. They are all different, since x^2 = y^2 implies (x + y)(x - y) = 0, ie x must be y or -y.
The fact that (n^2+1) is never divisible by 3 can be proven like this:
Two small reminders:
* "X is divisible by 3" <=> X % 3 == 0 (using the C notation)
* (A * B) % 3 == (((A % 3) * (B % 3)) % 3)
Therefore, (n^2)%3 == ((n%3)^2)%3, and we have three cases to consider:
* n%3 == 0, then (n^2)%3 == 0
* n%3 == 1, then (n^2)%3 == 1
* n%3 == 2, then (n^2)%3 == 4%3 == 1
We see that (n^2)%3 != 2, therefore (n^2+1)%3 != 0, hence (n^2+1) is never divisible by 3.
As for "diff between m", start with differences between n^2:
* (n+1)^2 == n^2 + (2n+1)
Your "diff between m" is thus (2n+1)/3, except for rounding. Similarly to the above, you can determine the structure of (2n+1)%3. Looking at this will reveal the reason why two out of three values are repeated, details left as an exercise :)
Its all about the modulus of 3 and the quadratic equation.
Take n=a*3+b where a is any integer
take b as 0, 1 or 2
Now n^2=9*a^2+6*a*b+b^2=3*C+b^2
b^2 is either 0, 1, 4
4=3+1
when b=0 n^2=3c
when b=1 n^2=3c+1
when b=2 n^2=3c+1
Now m=n^2+1=3*c+b^2+1
when b=0 n^2+1=3c+1
when b=1 n^2+1=3c+2
when b=2 n^2+1=3c+2
Hi,
You have discovered modulo arithmetic :)
Basically you are saying n^2 +1 != 0 mod 3
You can just try this for small values of n:
n = 0 value = 0*0+1 = 1
n = 1 value = 1*1+1 = 2
n = 2 value = 2*2+1 = 5 = 2 mod 3
The secret is any polynomial will also repeat with n mod 3. This is because you can rewrite n' as (n + 3a) where a is an integer.
Substitute this into your original equation:
(n + 3a)^2 + 1 mod 3
becomes:
n^2 + 2 * 3a + 3a * 3a + 1 mod 3
becomes:
n^2 + 3*(2a + 3a) + 1 mod 3
But mod 3 the second term is 0. So:
n^2 + 1 mod 3
Hence the repeating 1 2 2 results for n mod 3
Regards,
DDD
P.S The maths was way easier than logging into this comments system :)
The difference between two squares is always 2n+1. Since we are just looking at how far from a multiplier by 3 we are we can just mod 3 the numbers. This gives a pattern of 0,2,1,0,2,1,0,2,1...
A number 0 (an increase by a multiplier of 3) says the next number will have the same offset as the last. A number of 1 says the offset will increase by 1. And a value of 2 says the offset will decrease by one.
So 0, -1, +1, 0, -1, +1.... will be stuck dithering back and forth between the two places.
The mod 5 of the sequence (0, 2, 4, 1, 3, 0, 2...) is interesting because it happens to a mod 5 number (as 0+2+4+1+3=10) just before getting the next zero, thus spending two turns at zero and explaining why two of the five numbers in the sequence are divisible by five.
Thanks guys. I appreciate the help.
Post a Comment