## ParthKohli one year ago @Kainui I think you'd like this.

1. ParthKohli

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$$?

2. ParthKohli

@ganeshie8

3. ParthKohli

$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$

4. ParthKohli

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

5. ParthKohli

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$$).

6. ParthKohli

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

7. ParthKohli

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

8. ganeshie8

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)$

9. ParthKohli

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

10. ParthKohli

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

11. ParthKohli

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

12. ganeshie8

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]

13. ParthKohli

Oh, that skipped me! Wow!!!

14. ParthKohli

Amazing!

15. ParthKohli

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.

16. ParthKohli

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

17. ParthKohli

I'm really bad at counting. :|

18. ParthKohli

$\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.

19. ParthKohli

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

20. ParthKohli

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

21. ParthKohli

Oh, nope.

22. ganeshie8

$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}$$

23. ParthKohli

Exactly...

24. ParthKohli

Oh, I got it. Thanks.

25. ParthKohli

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

26. ParthKohli

1997 distinct values?

27. ganeshie8

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

28. ganeshie8

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

29. ParthKohli

$\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?

30. ganeshie8
31. ParthKohli

Oh my, never mind...

32. ParthKohli

Goddammit.

33. ganeshie8

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

34. ParthKohli

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

35. ParthKohli

(?)

36. ParthKohli

Or am I misunderstanding what you're saying?

37. ganeshie8

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

38. ParthKohli

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

39. ParthKohli

Obviously, yes.

40. ParthKohli

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

41. ParthKohli

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

42. ganeshie8

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

43. ParthKohli

Yes, I have no idea how modular arithmetic works.

44. ganeshie8

eating dinner.. 10 mnts

45. ParthKohli

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

46. ganeshie8

you may use chinese remainder thm or go wid binary exponentiation

47. ganeshie8

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

48. ParthKohli

W|A returns 337.

49. Kainui

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}$