# Help Needed from Math Enthusiasts

In the MAT (perhaps the TMUA as well), there's this annoying type of question where given that $f(x)$ is a function on positive integers defined by

- $f(1) =$ some initial value
- $f(2n) = \dotsc$, recursively
- $f(2n + 1) = \dotsc$, recursively

Find the sum of ... Or, find the largest term... Or, blah blah blah.

An example practice problem is below and will hopefully help to illustrate my message.

> The function f(n) is defined for positive integers n by f(1) = 1 and for n >= 2 by
$f(2n) = 4f(n)$
$f(2n + 1) = \frac{f(n)}{2}$

For how many integers $1 \le n \le 50$ is $f(n) \le 10$?

How would you approach this style of question? It seems like in some cases, you must trial and error on **a lot of values** of x fed into the function and from there spot patterns. Is this the most efficient way to work through the question?
(edited 1 month ago)
Original post by timthedev07
In the MAT (perhaps the TMUA as well), there's this annoying type of question where given that $f(x)$ is a function on positive integers defined by
- $f(1) =$ some initial value
- $f(2n) = \dotsc$, recursively
- $f(2n + 1) = \dotsc$, recursively
Find the sum of ... Or, find the largest term... Or, blah blah blah.
How would you approach this style of question? It seems like in some cases, you must trial and error on **a lot of values** of x fed into the function and from there spot patterns. Is this the most efficient way to work through the question?

If would depend on the form of the function, but as you say, putting some small values in to spot a pattern (or two ...) and generalising from that is usually the way to go. You had an example in the unedited version of the OP. From a quick scribble it wasnt quite working, but iterating to an even index gave a geometric (4*) growth so that sequence would exceed 10 relatively quickly, and iterating to an odd index roughly corresponded to 1/x or x/2 depending on the size of x and would only exceed the inequality when x~+/-sqrt(2). But Id not fully worked it through and was going to come back to it, but its gone.
(edited 1 month ago)
Original post by mqb2766
If would depend on the form of the function, but as you say, putting some small values in to spot a pattern (or two ...) and generalising from that is usually the way to go. You had an example in the unedited version of the OP. From a quick scribble it wasnt quite working, but iterating to an even index gave a geometric (4*) growth so that sequence would exceed 10 relatively quickly, and iterating to an odd index roughly corresponded to 1/x or x/2 depending on the size of x and would only exceed the inequality when x~+/-sqrt(2). But Id not fully worked it through and was going to come back to it, but its gone.

Just after posting it I realized that I had the wrong question (the later part was from a different problem). I will now post the original and correct one.
Original post by timthedev07
In the MAT (perhaps the TMUA as well), there's this annoying type of question where given that $f(x)$ is a function on positive integers defined by
- $f(1) =$ some initial value
- $f(2n) = \dotsc$, recursively
- $f(2n + 1) = \dotsc$, recursively
Find the sum of ... Or, find the largest term... Or, blah blah blah.
An example practice problem is below and will hopefully help to illustrate my message.
> The function f(n) is defined for positive integers n by f(1) = 1 and for n >= 2 by
$f(2n) = 4f(n)$
$f(2n + 1) = \frac{f(n)}{2}$
For how many integers $1 \le n \le 50$ is $f(n) \le 10$?
How would you approach this style of question? It seems like in some cases, you must trial and error on **a lot of values** of x fed into the function and from there spot patterns. Is this the most efficient way to work through the question?

From the form of the function, its fairly clear that the appropriate subsequences are geometric with ratio 4 (iterate to an even index) or 1/2 (iterate to an odd index), so its shouldnt be that hard? Really for each index youre counting the number of odd and even iterations and noting that 2 odds and 1 even leave the number unchanged and having 2 more evens means its > 10 and youve a max of 5 iterations to get to 50.

So you could have straight 2,3,4,5 even maps corresponding to n=4,8,16,32. 4 or 3 even maps with 1 odd one, so n=24,48,20,40, ... With 2 odd ones, youd need to have 3 even so a few of those would not be valid and no 3 odd ones would be valid

Edit - a bit more systematic way of considering the odd/even maps would be to iterate out the even maps so n=2,4,8,16,32 and think about how to get the intermediate values. So consider n=17..31. n=16 is given by 4 iterations of the even map so f(16)=4^4=256. All the values from 17 to 31 will be given by 4 iterations of odd/even maps. 17 is eeeo, 18 is eeoe, 19 is eeoo, 20 is eoee, 21 is eoeo .... So really its just a binary pattern where you count the number of 1 and 0s and they determine whether e-o/2>=2 (for > 10). Or equivalently
n = 2,3
e,o = (1,0),(0,1)
n=4..7
e,o = (2,0),2*(1,1),(0,2)
n=8..15
e,o = (3,0),3*(2,1),3*(1,2),(0,3)
....
(edited 4 weeks ago)
Original post by mqb2766
From the form of the function, its fairly clear that the appropriate subsequences are geometric with ratio 4 (iterate to an even index) or 1/2 (iterate to an odd index), so its shouldnt be that hard? Really for each index youre counting the number of odd and even iterations and noting that 2 odds and 1 even leave the number unchanged and having 2 more evens means its > 10 and youve a max of 5 iterations to get to 50.
So you could have straight 2,3,4,5 even maps corresponding to n=4,8,16,32. 4 or 3 even maps with 1 odd one, so n=24,48,20,40, ... With 2 odd ones, youd need to have 3 even so a few of those would not be valid and no 3 odd ones would be valid
Edit - a bit more systematic way of considering the odd/even maps would be to iterate out the even maps so n=2,4,8,16,32 and think about how to get the intermediate values. So consider n=17..31. n=16 is given by 4 iterations of the even map so f(16)=4^4=256. All the values from 17 to 31 will be given by 4 iterations of odd/even maps. 17 is eeeo, 18 is eeoe, 19 is eeoo, 20 is eoee, 21 is eoeo .... So really its just a binary pattern where you count the number of 1 and 0s and they determine whether e-o/2>=2 (for > 10). Or equivalently
n = 2,3
e,o = (1,0),(0,1)
n=4..7
e,o = (2,0),2*(1,1),(0,2)
n=8..15
e,o = (3,0),3*(2,1),3*(1,2),(0,3)
....

Right, with some practice of other questions I can see where your logic is coming from. Thanks for the detailed response!
Original post by timthedev07
Right, with some practice of other questions I can see where your logic is coming from. Thanks for the detailed response!

NP. Really its a binary / nCr / pascals triangle question and the hint was the fact that /2 and 4* cancel when you do two iterations of odd compared to even and you do the same number of iterations on each range [2^n, 2^(n+1)-1]. Though they could have made the upper limit 63, instead of 50.

I take it you noticed the similarity (roughly) with the famous collatz problem.
(edited 4 weeks ago)
Original post by mqb2766
NP. Really its a binary / nCr / pascals triangle question and the hint was the fact that /2 and 4* cancel when you do two iterations of odd compared to even and you do the same number of iterations on each range [2^n, 2^(n+1)-1]. Though they could have made the upper limit 63, instead of 50.
I take it you noticed the similarity (roughly) with the famous collatz problem.

That helps! This is definitely worth looking back at and I will take some more time to ponder on it. Thanks again for helping!

Speaking of the Collatz conjecture yes, at first glance it did remind me of it! I still remember playing with it in Python at year 10 hahaha.
Original post by timthedev07
That helps! This is definitely worth looking back at and I will take some more time to ponder on it. Thanks again for helping!
Speaking of the Collatz conjecture yes, at first glance it did remind me of it! I still remember playing with it in Python at year 10 hahaha.

There a decent (simple) simulator at
https://www.dcode.fr/collatz-conjecture
and if you want to try and partially analyse it (rather than program a simulation), think about why it has exponential subsequences when you start with n=31. Theres quite a bit of simple analysis you can do.
(edited 4 weeks ago)
Yes, I remember having used this site for other purposes, but this is a great one!

Looking back at my 3-year-old repo, another interesting discovery was that the frequency of the digits 0 to 9 in order seems to be decreasing for large samples. Perhaps another fun phenomenon to think about...