@Kainui I think you'd like this.

Question

parthkohli · Answer

Let $a_n$ be a sequence of real numbers defined by $a_1 = t$ and $a_{n+1} = 4a_n(1 - a_n)$ for $n > 1$. 

Find the last three digits of the  number of distinct values of $t$ such that $a_{1998} = 0$?

parthkohli · Answer

@ganeshie8

parthkohli · Answer

$$a_1 = t$$$$a_2 = 4t(1-t)$$$$a_3 = 16t(1-t)\left[1 - 4t(1-t) \right] = 16t(1-t)\cdot - (2t-1)^2 = -16t(1-t)(2t-1)^2$$

parthkohli · Answer

I guess we need to see a pattern and confirm our pattern by induction.

parthkohli · Answer

If not a pattern in our polynomials, we can at least try to see one in the number of distinct values of $t$ (and how repeated roots work with increasing $n$).

parthkohli · Answer

n           |        degree        |         distinct roots |
----------------------------------------
1           |            1            |             0                |
2           |            2            |             2                |
3           |            4            |             3                |
4           |            8            |             6                |

parthkohli · Answer

How about trying to see repeated roots?

0, 0, 1, 2, ...

ganeshie8 · Answer

just an observation
$$a_{n} =\sin^2{2^{n-1 }\theta} \implies  a_{n+1} = 4\sin^2(2^{n-1}\theta)(1-\sin^2(2^{n-1}\theta)) = \sin^2(2^n\theta)$$

It follows that
$$a_{1998}= \sin^2(2^{1997}\theta)$$

parthkohli · Answer

I noticed that at exactly the same moment as you posted it. Good observation. 

However, that would reserve our sequence to [-1,1].

parthkohli · Answer

It is still a useful thought. Maybe working with $\tan$ would help us achieve something?

parthkohli · Answer

Actually it would reserve our sequence to [0,1]...

ganeshie8 · Answer

we're interested in [0, 1] only because anything outside spits out numbers that are outside [0, 1] so all the terms of the sequence will be outside the interval [0, 1]

parthkohli · Answer

Oh, that skipped me! Wow!!!

parthkohli · Answer

Amazing!

parthkohli · Answer

So if $a_1 = t = \sin^2 \theta $ then we're interested in finding the unique values of $\sin^2 \theta$ such that $\sin(2^{1997}\theta) = 0$.

I think you just recovered my love for math.

parthkohli · Answer

$2^{1997}\theta$ should be a multiple of $\pi$...

parthkohli · Answer

I'm really bad at counting. :|

parthkohli · Answer

$$\theta = n\pi$$satisfies the equation and returns only one value for $\sin^2\theta$, i.e., 0. Now we've got to look at fractional values.

parthkohli · Answer

$$\theta = \pm \pi/2^{1997}, \pm  \pi/2^{1996}, \cdots ,\pm \pi/2^1$$Each pair returns one unique value of $\sin^2\theta$.

parthkohli · Answer

So far, we've calculated 1998 unique values of $\sin^2\theta$. Is that it?

parthkohli · Answer

Oh, nope.

ganeshie8 · Answer

$$t\in [0,1] \implies \theta \in [0,\frac{\pi}{2} ]$$

$$\sin(2^{1997}\theta) = 0 \implies  \theta = \frac{n\pi}{2^{1997}}$$
$n=0,1,2,\ldots, 2^{1996}$

parthkohli · Answer

Exactly...

parthkohli · Answer

Oh, I got it. Thanks.

parthkohli · Answer

I double-counted 0 at $\theta = 0 $ and $\pi$. :P

parthkohli · Answer

1997 distinct values?

ganeshie8 · Answer

that would be too less when you compose a quadratic 1998 times

ganeshie8 · Answer

also recall the fact that sin is one-to-one in the interval [0, pi/2]

parthkohli · Answer

$$\theta = \pm \pi/2^{1997}, \pm  \pi/2^{1996}, \cdots ,\pm \pi/2^1$$Now what you're saying is that I should multiply $\pi/2^{1997}$ by $n = 1, 2, 3,\cdots, 1996$
then $\pi/2^{1996}$ by $n = 1, 2, 3,\cdots, 1995 $ and so on, right?

ganeshie8 · Answer

http://gyazo.com/f22b532bddfbe6cd15af74145160b997

parthkohli · Answer

Oh my, never mind...

parthkohli · Answer

Goddammit.

ganeshie8 · Answer

find the values of $n$ such that $\theta \in [0,\pi/2]$

parthkohli · Answer

Yes, alright. So $2^{1997}$ distinct values.

parthkohli · Answer

(?)

parthkohli · Answer

Or am I misunderstanding what you're saying?

ganeshie8 · Answer

the solution i have says $2^{1996}+1$
so double check..

parthkohli · Answer

Oh my god, what is wrong with me...

parthkohli · Answer

Obviously, yes.

parthkohli · Answer

What are the last three digits of that? I don't know how modular arithmetic works.

parthkohli · Answer

Remind me to get some sleep after this one. Thanks.

ganeshie8 · Answer

work $$2^{1996}+1 \pmod{1000}$$

parthkohli · Answer

Yes, I have no idea how modular arithmetic works.

ganeshie8 · Answer

eating dinner.. 10 mnts

parthkohli · Answer

My ... what a beautiful solution you came up with.

ganeshie8 · Answer

you may use chinese remainder thm or go wid binary exponentiation

ganeshie8 · Answer

i don't see any other neat way to reduce 2^1996

parthkohli · Answer

W|A returns 337.

kainui · Answer

Is it possible to go backwards? Let's say $b_1=0$ and $b_{1998} = t$

$$b_{n+1} = \frac{1 \pm \sqrt{1-b_n}}{2}$$