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