Discovering an Algorithm in 2021.

Algebra Level 5

Let $S_n$ be the set of all the numbers of the form $\epsilon_n\sqrt{3+\epsilon_{n-1}\sqrt{3+...+\epsilon_2\sqrt{3+\epsilon_1 \sqrt{3}}}}$ where the number of radicals is an arbitrary non-negative integer number $n$ and $\epsilon_k=\pm 1$ for any non-negative integer $k$ less than or equal to $n.$ If you can express the elements of $S_{12}$ like a finite increasing sequence of numbers $\{r_0, r_1, r_2, ..., r_{m-1}\},$ where $m$ is the number of distinct numbers in $S_{12},$ then find $\lfloor -1000r_{2021}\rfloor,$ otherwise, enter 555.

Note : $\lfloor x \rfloor$ denotes the floor of the number $x.$

The answer is 835.

3 solutions

Alexander McDowell
Jan 9, 2021

Let $E_n$ represent the set of possible $\epsilon_k$ for an integer $k$ less than equal to $n$ where the corresponding $r_m$ is sorted from lowest to highest (I will abbreviate $-1$ as $-$ and $1$ as $+$ ). For instance, $E_2 = \{[-, +], [-, -], [+, -], [+, +]\}$ with corresponding set of $r_m$ of $\left\{-\sqrt{3+\sqrt{3}},-\sqrt{3-\sqrt{3}},\sqrt{3-\sqrt{3}},\sqrt{3+\sqrt{3}}\right\}$ . The $i$ th element of $E_n$ corresponds to $\epsilon_{n - i + 1}$ (e.g: 1st element equals $\epsilon_n$ and last element equals $\epsilon_1$ ). I started by listing out $S_n$ for various small values of $n$ using brute-force:

$n$	$E_n$
1	$\{[-], [+]\}$
2	$\{[-, +], [-, -], [+, -], [+, +]\}$
3	$\{[-, +, +], [-, +, -], [-, -, -], [-, -, +], [+, -, +], [+, -, -], [+, +, -], [+, +, +]\}$

Using a Python script, I also computed $E_4$ and $E_5$ but I figured that the sizes of these sets would be too large to display in this post ( $|E_4| = 16$ and $|E_5| = 32$ ).

After listing these sets, I noticed several repeated patterns. First, look at the last number of each of the sets ( $\epsilon_1$ ) with $n > 1$ . For $E_2$ , the sequence of $\epsilon_1$ values is $\{+, -, -, +\}$ . For $E_3$ , the sequence is $\{+, -, -, +, +, -, -, +\}$ . In general for $n > 1$ , $\epsilon_1$ alternates between groups of two $-$ and groups of two $+$ beginning with a group of 1 $+$ . We can model this sequence for the $i$ th ( $i \geq 1$ ) set of $E_n$ given $n > k$ with the function $f_{1}\left(i\right)=\left(-1\right)^{\operatorname{floor}\left(\frac{\operatorname{mod}\left(i,4\right)}{2}\right)}$ (check values yourself to confirm that it works).

Next, we'll look at the sequence of ( $\epsilon_2$ ) with $n > 2$ . For $E_3$ , the sequence is $\{+, +, -, -, -, -, +, +\}$ . For $E_4$ , the sequence is $\{+, +, -, -, -, -, +, +, +, +, -, -, -, -, +, +\}$ . In general for $n > 2$ , $\epsilon_2$ alternates between groups of four $-$ and groups of four $+$ beginning with a group of 2 $+$ . We can model this sequence for the $i$ th ( $i \geq 1$ ) set of $E_n$ given $n > k$ with the function $f_{2}\left(i\right)=\left(-1\right)^{\operatorname{floor}\left(\frac{\operatorname{mod}\left(i+1,8\right)}{4}\right)}$

Looking at the sequences for $\epsilon_3$ and $\epsilon_4$ , it turns out that for $n > k$ , $\epsilon_k$ alternates between groups of $2^k$ $-$ and groups of $2^k$ $+$ beginning with a group of $2^{k -1}$ $+$ . We can generalize this with the function $\displaystyle f\left(i,k\right)=\left(-1\right)^{\displaystyle \operatorname{floor}\left(\frac{\operatorname{mod}\left(i+2^{k-1}-1,2^{k+1}\right)}{2^{k}}\right)}$ to find the value of $\epsilon_k$ for the $i$ th ( $i \geq 1$ ) set of $E_n$ given $n > k$ .

Now what about $k = n$ ? Well, let's look at the sequences of $\epsilon_n$ for each $E_n$ . For $E_1$ , the sequence of $\epsilon_1$ is $\{-, +\}$ , for $E_2$ , the sequence of $\epsilon_2$ is $\{-, -, +, +\}$ , and for $E_3$ , the sequence of $\epsilon_3$ is $\{-, -, -, -, +, +, +, +\}$ . We quickly see that the sequence for $\epsilon_n$ starts with $2^{n - 1}$ groups of $-$ followed by $2^{n - 1}$ groups of $+$ . The general formula for $\epsilon_n$ for the $i$ th ( $i \geq 1$ ) set of $E_n$ is $g\left(i,n\right)=\left(-1\right)^{\displaystyle 1+\operatorname{floor}\left(\frac{i-1}{2^{\left(n-1\right)}}\right)}$ .

We now have the tools we need to compute $r_{2021}$ for $n = 12$ . Firstly, we generate the 2022th index of $E_{12}$ (since $r$ starts counting at 0 not 1) using $f(2022, k)$ with $1 \leq k < 12$ and $g(2022, 12)$ . This means that $\epsilon_1 = f(2022, 1)$ , $\epsilon_2 = f(2022, 2)$ , $\epsilon_3 = f(2022, 3)$ , ..., $\epsilon_{12} = g(2022, 12)$ . This list of $\epsilon_k$ is $[-1, -1, -1, 1, -1, 1, 1, 1, 1, 1, -1, -1]$ . Plugging this into the nested radical expression (I used a Python script for this) gives $r_{2021} = -0.835422$ . Thus, $\lfloor -1000r_{2021} \rfloor = \boxed{835}$ .

I imagine that the proof for why this pattern emerges is more complicated than simply identifying the pattern.

Wonderful work, @Alexander McDowell !

Arturo Presa - 5 months ago

Jose Presa
Feb 6, 2021

using System;
using System.Collections.Generic;
using System.Linq;

namespace RadicalCalculator
{
    public class RadicalValueCalculator
    {
        private static readonly int _epsilonLength = 12;

        public static int[] GenerateEpsilonCombinationFor(int i)
        {
            var stringForm = Convert.ToString(i, 2).PadLeft(12, '0');
            var result = stringForm.Select(b => b == '0' ? -1 : 1).ToArray();
            return result;
        }

        public static IEnumerable<int[]> GenerateAllEpsilonCombinations()
        {
            var setSize = (int)Math.Pow(2, _epsilonLength);

            for (int i = 0; i < setSize; i++)
                yield return GenerateEpsilonCombinationFor(i);
        }

        public static double CalculateRadicalFor(int[] epsilons)
        {
            if (epsilons.Length != _epsilonLength)
                throw new Exception("Wrong size array");

            double result = 0;

            for (int i=0; i < _epsilonLength; i++)
            {
                result = epsilons[i] * Math.Sqrt(3 + result);
            }

            return result;
        }

        public static double FinalCalculation()
        {
            var allEpsilonArrays = GenerateAllEpsilonCombinations().ToList();
            var allRadicalResults = allEpsilonArrays.Select(a => CalculateRadicalFor(a)).OrderBy(v => v).ToArray();
            var result = Math.Floor(allRadicalResults[2021] * -1000);
            return result;
        }
    }

    public class Tests
    {
        [Test]
        public void EndToEndTest()
        {
            Assert.AreEqual(835, RadicalValueCalculator.FinalCalculation());
        }
    }
}

Arturo Presa
Jan 9, 2021

Given an arbitrary positive integer number $n$ , we can define the following function $f_n: S_n\rightarrow \{0, 1, 2, ..., 2^n-1\}$ by the following rule $f_n(a_n\sqrt{3+ a_{n-1}\sqrt{3+...+ a_1\sqrt{3}}})= (\overline{\alpha_n \alpha_{n-1} ... \alpha_1})_2,$ where the expression in the right side of the following equation is a binary number defined on the following way For any integer $k$ greater than or equal to 1 and less than $n$ , $\alpha_k=\begin{cases} 1, & \text{ if}\; a_n a_{n-1}...a_k=1 \\ 0, & \text{ if}\; a_na_{n-1}...a_k=-1. \end{cases}$ We can see that $f_n$ is well-defined and has an inverse function that can be defined in the following way $f_n^{-1} (\overline{\alpha_n\alpha_{n-1} ... \alpha_1})_2=a_n\sqrt{3+ \frac{a_{n-1}}{a_n}\sqrt{3+...+ \frac{a_1}{a_2}\sqrt{3}}},$ where
$a_k=\begin{cases} 1, & \text{ if}\; \alpha_k=1 \\ -1, & \text{ if}\; \alpha_k=0. \end{cases}$ Now, we are going to use Mathematical Induction to prove the following equivalence.

$a_n\sqrt{3+ a_{n-1}\sqrt{3+...+ a_1\sqrt{3}}}<b_n\sqrt{3+ b_{n-1}\sqrt{3+...+ b_1\sqrt{3}}} \iff$ $f_n(a_n\sqrt{3+ a_{n-1}\sqrt{3+...+ a_1\sqrt{3}}})<f_n(b_n\sqrt{3+ b_{n-1}\sqrt{3+...+ b_1\sqrt{3}}})\;\;\;\;\;\;\;(*)$ Notice that the symbol "<" represent the regular order of the set of numbers. Of course, this property is obviously true when $n=1.$

Assume that the equivalence is true if $n=k,$ and we must prove that it is true when $n=k+1.$ To prove (*) for $n=k+1$ let us consider two numbers $a_{k+1}\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}}$ and $b_{k+1}\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}}$ in $S_{k+1}$ . Let us consider also that $f_{k+1}(a_{k+1}\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}})=(\overline{\alpha_{k+1}\alpha_k ... \alpha_1})_2$ and $f_{k+1}(b_{k+1}\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}} )=(\overline{\beta_{k+1} \beta_k ... \beta_1})_2,$ where the $\alpha_k's$ and the $\beta_k's$ are defined as we did it above. We are going to divide the proof in the following cases.

Case 1. $a_{k+1}=-1$ and $b_{k+1}=1.$

The equivalence (*) is true due to the fact that $(a_{k+1}=-1\; \text{ and} \;b_{k+1}=1) \iff (\alpha_{k+1}=0 \;\text{and}\; \beta_{k+1} =1)$

Case 2. $a_{k+1}=b_{k+1}=1.$ In this case, it is easy to see that if $f_{k+1}(\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}})=(\overline{1 \alpha_k ... \alpha_1})_2$ and $f_{k+1}(\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}} )=(\overline{1 \beta_k ... \beta_1})_2,$ then $f_k( a_{k}\sqrt{3+...+ a_1\sqrt{3}})=(\overline{ \alpha_k ... \alpha_1})_2$ and $f_k( b_{k}\sqrt{3+...+ b_1\sqrt{3}})=(\overline{\beta_k ... \beta_1})_2,$ and vice-versa.

Then we can prove the equivalence (*) for $n=k+1$ in the following way. The condition $\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}}<\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}}$ is equivalent to $a_{k}\sqrt{3+...+ a_1\sqrt{3}}< b_{k}\sqrt{3+...+ b_1\sqrt{3}}$ by the definition of the order on $M^{k+1}.$ Using the hypothesis of induction the last inequality is equivalent to $(\overline{ \alpha_k ... \alpha_1})_2<(\overline{\beta_k ... \beta_1})_2,$ and this one is equivalent to $f_{k+1}(\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}})<f_{k+1}(\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}}).$

Case 3. $a_{k+1}=b_{k+1}=-1.$ In this case, it also easy to see that $f_{k+1}(-\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}})=(\overline{\alpha_k, ..., \alpha_{1}})_2$ and $f_{k+1}( -\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}})=(\overline{\beta_k ... \beta_{1}})_2.$ In turn, these two equations are equivalent to $f_{k}( a_{k}\sqrt{3+...+ a_1\sqrt{3}})=(\overline{t_k ..., t_{1}})_2$ and $f_{k}( b_{k}\sqrt{3+...+ b_1\sqrt{3}})=(\overline{t_k, ..., t_{1}})_2,$ where $t_k=\begin{cases} 0, & \text{ if}\; \alpha_k=1 \\ 1, & \text{ if}\; \alpha_k=0. \end{cases}$ and $s_k=\begin{cases} 0, & \text{ if}\; \beta_k=1 \\ 1, & \text{ if}\; \beta_k=0. \end{cases}$ Now the equivalence (*) can be proved in a simple way for $n=k+1.$ The condition $-\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}}<-\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}}$ is equivalent to $b_{k}\sqrt{3+...+ b_1\sqrt{3}}< a_{k}\sqrt{3+...+ a_1\sqrt{3}}.$ The last inequality is equivalent to $f_{k}( b_{k}\sqrt{3+...+ b_1\sqrt{3}})<f_{k}( a_{k}\sqrt{3+...+ a_1\sqrt{3}}),$ by the hypothesis of induction, and using the definitions of the $t_k's$ and $s_k's$ that we introduced above , this last inequality is equivalent to $f_{k+1}(-\sqrt{3+ a_{k}\sqrt{3+...+ a_1\sqrt{3}}})<f_{k+1}(-\sqrt{3+ b_{k}\sqrt{3+...+ b_1\sqrt{3}}}).$

Then the proof of (*) is complete.

From the property (*), we can obtain that $f_n$ is not only bijective, but it also keeps the order. Therefore, in the case that $n=12,$ we have that $l_k=f_{12}^{-1}(k),$ where $k$ is an integer satisfying $0\leq k\leq 2^{12}-1=4095.$ Now using that $f_{12}^{-1}((\overline{\alpha_1 ... \alpha_{11}})_2)=(a_{12}\sqrt{3+ \frac{a_{11}}{a_{12}}\sqrt{3+...+ \frac{a_1}{a_2}\sqrt{3}}})$ as it was defined above, and that the binary representation of 2021 is $(\overline{011111100101})_2,$ we obtain that $f_{12}^{-1}(2021)=-\sqrt {3 -\sqrt {3+\sqrt{3+\sqrt{3+\sqrt{3+\sqrt{3+\sqrt{3-\sqrt{3+\sqrt{3-\sqrt{3-\sqrt{3-\sqrt{ 3}}}}}}}}}}}}=-0.8354...$ So the answer is $\boxed {835}.$

Discovering an Algorithm in 2021.

The answer is 835.

3 solutions

0 pending reports