/sci/ - Science & Math

>>4684498 i think i got this
first divide n to 2^k *m where m is an odd number. now the remainder is eventually constant iff it's eventuall constant for both (mod 2^k) and (mod m)
for the even remainder it's obvious. for m, since it's coprime with 2, we can use euler and say that the series is eventually constant iff the series (mod phi(m) ) is eventually constant
enter induction

>>4684498
We've seen this problem here before.
Don't remember the proof tho.

>>4684595
what's with people and saying how to prove instead of proving?
it really rustles my jimmies

>>4684803
i only left out the obvious stuff, i think
for the 2^k part, wait until the point where the tower surpasses k (as integers) from there on it's a constant 0
for the induction part, phi(m) < m <= n, and the base case for n=1 is constant from the start.

>>4684827
still, it's better to prove it
in a test, you cant just say "here's how i'd prove it", you have to do it
i know your contribution is valid, but it just sucks because i know nobody is gonna pick up on what you said and actually prove

>>4686142
Not the person you were responding to, but I would argue that's only because tests have to be graded quickly. In general, giving instructions on how to prove something is sufficient to communicate a proof.

>>4684498
wait a sec
>second line
is it 2,..,(mod n) or is it 2,... = (modn)
i'm a bit confused

>>4686339

le epic /g/ raid xD

2^1 (mod 3) = 2, 2^2 (mod 3) = 1. Doesn't that instantly kill this proposition?

>>4686673
no, because it says 'eventually constant'

obviously for an < n, an mod n = an, and n can be arbitrarily large
i think the problem consists in proving that an mod n is constant for any an >= n

>>4686756
damn, replace an with ai

>>4686756
Yeah, but I found a (nontrivial) CYCLE. Which means it will never be constant. For all even i, a_i = 1 (mod 3), and for all odd i, a_i = 2 (mod 3).

>>4686820
a_3 = 2^(2^2) = 2^4 = 16
i is odd
16 mod 3 = 1 mod 3

it's not a cycle
try finding an i >= 2 for which a_i =/= 1 mod 3 and then we'll talk

>>4686868
that happens because you thought getting the square would do the same to the mod as multiplying by two, but it doesnt, getting the square does nothing to the mod if the number is bigger than n, this fact, if proven, would solve the problem

>>4686884
its not getting the square, actually, but it is practically it, since 2^2 = 2*2

2^(2^2) = 2^(2*2) = (2^2)^2

>>4686887
actually that's wrong, since 2^4 =/= 2*4
damn, why can't i express myself right?

>>4686894
its not necessarily getting the square, but if not, then it is getting the square of the square of the square, or something
kthx

>>4686884

that fact is not true in general (x =/= x^2 mod p) in general.

a_i mod n = x

proposition: a_i^2 mod n = x, for any a_i >= n

a_i mod n = x
n*k+x=a_i, k is integer
a_i^2 = (n*k+x)^2 = n^2k^2 + 2nkx + x^2
a_i^2 mod n = n^2k^2 + 2nkx + x^2 mod n = x^2 mod n, since n^2k^2 and 2nkx have n as a factor

now this consists in proving that x^2 mod n = x = a_i - n*k

x^2 = (a_i - n*k)^2 = a_i^2 - 2a_i*n*k +n^2k^2
x^2 mod n = a_i^2 mod n
holy shit this isnt working

hmm, it also consists in proving that x^2 = x+n*r, r integer

lets try a proof by anti-contradiction
(x^2)^2 mod n = (x+n*r)^2 mod n = x^2 +2nrx + n^2r^2 mod n = x^2 mod n
there you have it, if x^2 mod n = x mod n, then x^4 mod n = x^2 mod n = x mod n
so say we get sqrt(ai) > n
if (sqrt(ai))^2 mod n = ai mod n = sqrt(ai) mod n, then ai^2 mod n = ai mod n = sqrt(ai) mod n, and in this case ai mod n = x

I think i might have a proof, first, lets get any 2^k bigger than n, then let's say that 2^k mod n = x, this means that 2^k = x+a*n (for an integer a >= 1 and k is another element from the sequence), then let's check the next term (2^k)^2 (as it have been proofed in other comments) , (2^k)^2 mod p = y+b*n (for an integer b >= 1), then (2^k)^2 = (x+a*n)^2 = y+b*n.
x^2+2*a*n+a^2*n^2 = y+b*n. now let's apply mod n at both sides. the result is x^2 mod n = y mod n, (where x 2^k mod n and y = 2^2^k mod n), this means that 2^k and 2^2^k are congruent with mod n.

>>4686983
if at the end you had x mod n = y mod n then yes, but you're still missing x^2 mod n = x mod n, which i proved at >>4686973 not for x>n, but for x=ai mod n and ai>n

Here's my crack at it:
Assuming that the proposition is true, there must be some term 2^a congruent k mod n such that (2^a)^2 is also congruent k mod n. By squaring the first equation, we find that k = k^2. Thus, the only potential solutions are for k = 0 or 1.
Obviously, whenever n is even, the remainder of (2^a)/n will be 0. When n is odd, by euler's theorem the remainder will be one when the exponent a is a multiple of the totient of n.

Here's my crack at it:
Assuming that the proposition is true, there must be some term 2^a congruent k mod n such that (2^a)^2 is also congruent k mod n. By squaring the first equation, we find that k = k^2. Thus, the only potential solutions are for k = 0 or 1.
Obviously, whenever n is even, the remainder of (2^a)/n will be 0. When n is odd, by euler's theorem the remainder will be one when the exponent 2^a is a multiple of the totient of n.

Here's my crack at it:
Assuming that the proposition is true, there must be some term 2^a congruent k mod n such that (2^a)^2 is also congruent k mod n. By squaring the first equation, we find that k = k^2. Thus, the only potential solutions are for k = 0 or 1.
Obviously, whenever n is even, the remainder of (2^a)/n will be 0. When n is odd, by euler's theorem the remainder will be one when the exponent a is a multiple of the totient of n.

>>4684827
This is induction at its finest.

It's constant mod 1, since it's always 0.
It's eventually constant mod i+1, by strong induction, since <span class="math"> 1 \leq \phi (i+1) \leq i, 2^{a_i} = 2^{a_i \mod \phi (i+1)} [/spoiler] which is eventually periodic.

>>4684827
This is induction at its finest.

It's constant mod 1, since it's always 0.
It's eventually constant mod i+1, by strong induction. Suppose the sequence is eventually constant mod each integer between 1 and i. Since <span class="math"> 1 \leq \phi (i+1) \leq i, 2^{a_i} = 2^{a_i mod \phi (i+1)} [/spoiler] where by inductive hypothesis <span class="math"> a_i mod \phi(i+1)[/spoiler] is eventually periodic.

Stupid not knowing what \mod is.

>>4684827
This is induction at its finest.

It's constant mod 1, since it's always 0.
It's eventually constant mod i+1, by strong induction. Suppose the sequence is eventually constant mod each integer between 1 and i. Since <span class="math"> 1 \leq \phi (i+1) \leq i, a_{k+1} = 2^{a_k} \equiv 2^{a_k\ mod\ \phi (i+1)} (mod\ i+1) [/spoiler] where by inductive hypothesis <span class="math"> a_i\ mod\ \phi(i+1)[/spoiler] is eventually constant, making the sequence eventually constant.

Stupid not knowing what \mod is.

>>4684827
This induction argument was already a proof, you guys.

It's constant mod 1, since it's always 0.
It's eventually constant mod i+1, by strong induction. Suppose the sequence is eventually constant mod each integer between 1 and i. Since <span class="math"> 1 \leq \phi (i+1) \leq i, a_{k+1} = 2^{a_k} \equiv 2^{a_k\ mod\ \phi (i+1)} (mod\ i+1) [/spoiler] where by inductive hypothesis <span class="math"> a_k\ mod\ \phi(i+1)[/spoiler] is eventually constant, making the sequence eventually constant.

Sorry about all the edits to clean it up.

>>4687380
This is only a clarification of the other person's post, not a full proof. We can already disregard cases where i+1 is even, since we proved it for the odd component of i+1, and we know that mod i+1, the sequence will just be constant mod that odd component, and constant mod a power of 2 (eventually 0 mod the power of 2) so it'll be constant mod i+1 by the Chinese Remainder Theorem.

>>4687396
The first post I was discussing a case which only applies when i+1 is odd. The second post, that one, applies when i+1 is even. Together, they make a valid induction argument that applies for all n.

>>4684498
I'm really confused. I wrote a program to check it with n = 7 and it goes from 2, to 4, to 2, and repeats.

I am right in saying the first 3 elements are 2, 4, and 16 right? It's not staying constant. Am I doing something wrong?

foreignfag here.

just to make this clear
"... is eventually constant"
means:
For any n there is an k, such that the sequence a_i is constant for all i>k
!?!

>>4687739
yes, except its the sequence a_i mod n

>>4687751

yeah, of course its mod(a_i,n) , my fault.

my question was about the word "eventually"

thanks