Induction or function? (corrected)

Let's divide $1994$ by $2$ consecutively, selecting only quotients.

$1994, 997, 498, 249, 124, 62, 31, 15, 7, 3, 1, 0.$

Then, determine $n$ to the numbers repectively: $1, 2, 4, 8, 16, 32, 65, 131, 262, 525, 1050, \quad \text{and} \quad 2101.$

Thus, the answer is $\boxed{2101}.$

Notice that: $f(1)=0, f(2)=1, f(3)=0, f(4)=3, f(5)=2, f(6)=1,$

$f(7)=0, f(8)=7...$ .

Using our imagination a bit, we claim that $f(2^m+k)=2^m-k-1$ , for $0\le{k}<2^m-1$ . We'll proceed by induction.

Suppose $f(2^m)=2^m-1$ , then

$f(2^{m+1})=2f(2^m)+1=2(2^m-1)+1=2^{m+1}-1$ ,

thus, our inductive assumption is correct for every power of $2$ . Now, suppose our assumption is true for every number $s\le{2^m+k}$ , with $0\le{k}<2^m-1$ . Let's see what happens with $s=2^m+k+1$ . If $k+1$ is even,

$f(2^m+k+1)=2f\left(2^{m-1}+\dfrac{k+1}{2}\right)+1=$

$2\left(2^{m-1}-\dfrac{k+1}{2}-1\right)+1=2^m-(k+1)-1$ .

If $k+1$ is odd,

$f(2^m+k+1)=2f\left(2^{m-1}+\dfrac{k}{2}\right)=$ $2\left(2^{m-1}-\dfrac{k}{2}-1\right)+1=2^m-(k+1)-1$ ,

which proves our assumption.However, we want $f(n)=1994$ , so, we have to find $m$ and $k$ such that $2^m-k-1=1994$ , or, $k=2^m-1995$ . Then, the minimum value of $n$ is obtained when $m=11$ and $k=53$ . The desired value is, thus, $n=2^{11}+53=2101$ .

We claim the following: if we represent $n$ in binary without any leading 0, then $f(n)$ is obtained by swapping all 0's to 1's and vice versa (and removing all initial 0's caused). The proof is by strong induction. The base case $f(1) = 0$ is given, so let's assume it has been proven for all $n < k$ and we want to prove it for $n = k$ . Suppose $k = 2p + q$ where $p \in \mathbb{N}$ and $q \in \{0, 1\}$ (exists by division algorithm). Then $f(k) = 2 f(p) + (1-q)$ . Observe that in binary, $2 f(p) + (1-q)$ is obtained by writing $f(p)$ in binary, followed by one additional digit $1-q$ . By our strong induction used on $n = p$ (valid because $p \le \frac{k}{2} < k$ ), $f(p)$ is the binary digits of $p$ flipped (0's swapped with 1's), and $1-q$ is $q$ flipped. This means $f(k)$ is exactly writing out the digits of $p$ flipped, followed by $q$ flipped. But this is simply writing out the digits of $k$ flipped. This proves the claim.

Now since $1994 = 11111001010_2$ , our desired $n$ must be in the form $\ldots 00000110101_2$ . However, the ellipsis part cannot be zero; if it is, then $n = 110101_2$ and $f(n) = 001010_2$ instead. So the ellipsis part must be at least 1, giving $100000110101_2 = \boxed{2101}$ which is indeed a solution.

Induction by binary structure of $n$

Any positive integer $n$ can be written uniquely in binary expansion, $n = a_0 + 2a_1 + 4a_2 + \cdots + 2^ka_k + \cdots + 2^{d-1}a_{d-1} + 2^d,\ \ \ a_i \in \{0, 1\}.$ This is equivalent to the calculation $1 \stackrel{\times 2 + a_{d-1}}\mapsto \cdot \stackrel{\times 2 + a_{d-2}}\mapsto \cdots \stackrel{\times 2 + a_0}\mapsto n.$ The recursion relations of $f$ show that $f(k\times 2 + a) = f(k)\times 2 + (1-a),$ so that we get $1 \stackrel{\times 2 + 1 - a_{d-1}}\mapsto \cdot \stackrel{\times 2 + 1 - a_{d-2}}\mapsto \cdots \stackrel{\times 2 + 1 - a_0}\mapsto f(n).$ This translates to $f(n) = (1 - a_0) + 2(1 - a_1) + 4(1 - a_2) + \cdots + 2^{d-1}(1 - a_{d-1} + 2^d\cdot 0) \\ = (1 + 2 + 4 + \cdots 2^d) - (a_0 + 2a_1 + 4a_2 + \cdots + 2^{d-1}a_{d-1} + 2^d) \\ = 2^{d+1} - 1 - n.$ Since $n \geq 2^d$ , it follows that $f(n) < 2^d$ . Conversely, $n = 2^{d+1} - 1 - f(n).$ Here, $d$ is any number with the property $f(n) < 2^d$ .

Apply this to $f(n) = 1994$ . Since $2^{10} < 1994 < 2^{11}$ , we need $d = 11$ at least. With this choice, $n = 2^{12} - 1 - 1994 = 4095 - 1994 = \boxed{2101}.$

The function is an increasing saw function as shown in the figure. The maxima of $f(n)$ occur when $n$ are powers of 2 and $f(2^k) = 2^k -1$ , then $f(n)$ decreases by 1 as $n$ increases by 1, such that $f(2^k + j) = 2^k - 1 - j$ , until when $n=2^{k+1}-1$ or $j = 2^k-1$ when $f(2^{k+1}-1) = 0$ . Next then $f(2^{k+1}) = 2^{k+1}-1$ .

Let us first prove $f(2^k) = 2^k - 1$ for all $k \ge 1$ by induction. For $k=1$ , $f(2) = 1 =2^1 - 1$ , hence the claim is true. Assuming the claim is true for $k$ , then $f(2^{\color{#D61F06}k+1}) = f(2\cdot 2^k) = 2f(2^k) + 1 = 2(2^k - 1) + 1 = 2^{\color{#D61F06}k+1} - 1$ . Therefore, the claim is also true for $k+1$ , hence true for all $k \ge 1$ .

From $f(2n+1) = 2f(n) = f(2n) - 1$ . This means that $f(m+1)=f(m)-1$ , if $m$ is even. Now consider, $f(2(2n)) = 2f(2n) + 1$ , $\implies f(2(2n)+1) = 2f(2n)$ . And $f(2(2n+1)) = 2f(2n+1)+1 = 2f(2n) - 1$ , $\implies f(4n+2) = f(4n+1) - 1$ . $\implies f(m+1) = f(m)-1$ , if $m$ is odd. Therefore,

$\begin{cases} f(n) = n - 1 & \text{if }n = 2^k \text{, where }k \in \mathbb N \\ f(n+1) = f(n) - 1 & \text{if }n \ne 2^k \end{cases} \\ \implies f(n) = 2^{\left \lfloor \log_2 n \right \rfloor} - 1 - \left(n-2^{\left \lfloor \log_2 n \right \rfloor}\right) = 2^{\left \lfloor \log_2 n \right \rfloor + 1} -n-1$

This implies that if $f(n) = N$ , $\implies n = 2^k-1+(2^k - N) = 2^{k+1} - N - 1$ , where $k = \left \lceil \log_2 N \right \rceil$ . Therefore for $N = 1994$ , $k=11$ and $n = 4096-1994-1 = \boxed{2101}$ .

We write $1994=2\cdot(2\cdot (2\cdot (2\cdot (2\cdot(2\cdot(2\cdot(2\cdot 7+1)+1)))+1))+1)$ . It's easily to find that $8$ is the smallest number such that $f(8)=7$ . Using the definition of $f$ as well as the backward substitution, we have $1994=2\cdot(2\cdot (2\cdot (2\cdot (2\cdot(2\cdot(2\cdot(2\cdot f(8)+1)+1)))+1))+1)= 2\cdot(2\cdot (2\cdot (2\cdot (2\cdot(2\cdot(2\cdot f(16)+1)))+1))+1)=\cdots=f(2101)$ .

Although some programs have already been posted, here is a short implementation of this function (Python):

1

f=lambda n: 2 * f(n - n % 2 >> 1) + ~n % 2 if ~-n else 0

This basically defines a recursive lambda-function that returns $0$ if $n$ is $1$ (to avoid booleans – which are subclasses of integers anyway – I used the bitwise complement of the negative of $n$ to check if it is $1$ , that is $-(-n - 1)$ , which only evaluates to $0$ , a falsy value, if $n$ is $1$ ). Then, if $n$ is odd, then the function returns $2\:f(\lfloor \frac{n-1}{2}\rfloor)$ , otherwise $1+ 2\:f(\lfloor \frac{n}{2}\rfloor)$ . Because we check the parity of $n$ , the $\lfloor \cdot\rfloor$ aren't even required, but I included them anyway because that's what my program does.

To see the smallest integer $n$ that satisfies the condition $f(n)=1994$ , you can simply run the following snippet after defining the above function:

1
2
3

int = 1
while f(int) != 1994: int += 1;
print(int)

Check it out online!

Of course, this implementation yields our correct result, 2101 .

Here's a C program to compute the answer...

/* File:          Br.c
   Compile with:  gcc Br.c -O3 -o Brill
   Run with:      ./Brill
   Output:        n = 2101 gives f(n) = 1994
*/

#include<stdio.h>

int f(int);


int main() {

    int n = 0, ans = 0;

    while(ans != 1994) {
        n++;
        ans = f(n);
    }

    printf("n = %d gives f(n) = %d\n", n, ans);

    return 0;
}


int f(int n) {

    if(n==1) {
        return 0;
    } else if(n%2 == 0) {
        return 2 * f(n/2) + 1;
    } else {
        return 2 * f( (n-1) / 2);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

# -*- coding: utf-8 -*-
"""
Created on Thu Jan 18 18:58:23 2018
@author: Michael Fitzgerald
"""

# https://brilliant.org/weekly-problems/2018-01-15/advanced/?p=3

i = 1
y = {i:0}
val = 1994

while i > 0:
    i += 1
    if i%2 == 0:
        y[i] = 2*y[i/2]+1
    else:
        y[i] = 2*y[(i-1)/2]
    if y[i] == val:
        print i
        print y
        break

1

2101

{1: 0, 2: 1, 3: 0, 4: 3, 5: 2, 6: 1, 7: 0, 8: 7, 9: 6, 10: 5, 11: 4, 12: 3, 13: 2, 14: 1, 15: 0, 16: 15, 17: 14, 18: 13, 19: 12, 20: 11, 21: 10, 22: 9, 23: 8, 24: 7, 25: 6, 26: 5, 27: 4, 28: 3, 29: 2, .................................................... , 2008: 39, 2009: 38, 2010: 37, 2011: 36, 2012: 35, 2013: 34, 2014: 33, 2015: 32, 2016: 31, 2017: 30, 2018: 29, 2019: 28, 2020: 27, 2021: 26, 2022: 25, 2023: 24, 2024: 23, 2025: 22, 2026: 21, 2027: 20, 2028: 19, 2029: 18, 2030: 17, 2031: 16, 2032: 15, 2033: 14, 2034: 13, 2035: 12, 2036: 11, 2037: 10, 2038: 9, 2039: 8, 2040: 7, 2041: 6, 2042: 5, 2043: 4, 2044: 3, 2045: 2, 2046: 1, 2047: 0, 2048: 2047, 2049: 2046, 2050: 2045, 2051: 2044, 2052: 2043, 2053: 2042, 2054: 2041, 2055: 2040, 2056: 2039, 2057: 2038, 2058: 2037, 2059: 2036, 2060: 2035, 2061: 2034, 2062: 2033, 2063: 2032, 2064: 2031, 2065: 2030, 2066: 2029, 2067: 2028, 2068: 2027, 2069: 2026, 2070: 2025, 2071: 2024, 2072: 2023, 2073: 2022, 2074: 2021, 2075: 2020, 2076: 2019, 2077: 2018, 2078: 2017, 2079: 2016, 2080: 2015, 2081: 2014, 2082: 2013, 2083: 2012, 2084: 2011, 2085: 2010, 2086: 2009, 2087: 2008, 2088: 2007, 2089: 2006, 2090: 2005, 2091: 2004, 2092: 2003, 2093: 2002, 2094: 2001, 2095: 2000, 2096: 1999, 2097: 1998, 2098: 1997, 2099: 1996, 2100: 1995, 2101: 1994}

f(1)=0 f(2)=1 f(3)=0 f(4)=3 f(5)=2 f(6)=1 f(7)=0 f(8)=7 f(9)=6

We can see that : For every natural r > 0 and natural a in range [0; 2^r[

n= 2^r+a

F(2^r + a) = 2^r - (a+1)

1994=2048-53=2^11-54= 2^r - (53 + 1)

So n=2^11=2048+53=2101

Here is my Brute solution to this problem:

Given:

$f(1)=0, f(2n)=2f(n)+1; f(2n+1)=2f(n);$

Where n∈N,f(n)∈Z*,Notice that 2n is even while 2f(n)+1 is odd, and 2n+1 is odd while 2f(n) is even;

We can rewrite this function as:

$f(1)=0; f(n)=2f(n/2)+1,n=2k,k∈N; f(n)=2f((n-1)/2), n=2k+1,k∈N;$

Since f(n)=1994,1994 is even,

thus 2f((n-1)/2)=1994,

f((n-1)/2)=997,

let n1=(n-1)/2,f(n1)=997;

Since 997 is odd,

2f(n1/2)+1=997;

thus f(n1/2)=498,

let n2=n1/2,

f(n2)=498,

.........And so on.

Until we find f(n11)=0;

Since we are finding the smallest n,even if there are multiple n11∈N such that f(n11)=0,we take the smallest value,thus n11=1;

And we are going all the way back:

n11=n10/2,

thus n10=2n11=2;

n10=n9/2,

n9=2n10=4;

n9=n8/2,

n8=2n9=8;

n8=n7/2,

n7=2n8=16;

n7=n6/2,

n6=2n7=32;

n6=(n5-1)/2,

n5=2n6+1=65;

............

Until we get n1=1050,

Since n1=(n-1)/2,

Thus n=2101;

And finally we are done.

Although it's a method that needs least consideration,but it would drive you crazy if you are dealing with bigger numbers by hand.

It's better to use a calculator or program when using this method.

A python solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def main():
    y=[0]
    n=1
    while y[n-1]!=1994:
        if n%2 == 0:
            y.append(2*y[(n)//2]+1)
        else:
            y.append(2*y[(n-1)//2])
        n=n+1
    print('(',n-1,',',y[n-1],')')
main()

1994=997.2 997=2.498+1 498=2.249 249=2.124+1 124=2.62 62=2.31 31=15.2+1 15=7.2+1 7=3.2+1 3=2.1+1

F(2)=2.0+1 F(4)=2.1+1 F(8)=2.3+1 F(16)=15 F(32)=31 F(65)=62 F(131)=124 F(262)=249 F(525)=498 F(1050)=997 F(2101)=1994