2
$\begingroup$

For random natural number $N_0 > 1$, we find $N_1$ by the rule:

$N_{i+1} = \frac{N_i}{2}$ if $N_i$ is even

$N_{i+1} = 3N_i + 1$ if $N_i$ is odd

If $N_1$ isn't equal to $1$, we find $N_2$ by applying the same rule on $N_1$.

$N_0$ is at a distance $X$ from $1$, when after exactly $X$ applications of the rule, we get $1$ for the first time.

What's the amount of natural numbers at distance 61 from 1 ?

$\endgroup$
  • $\begingroup$ This stems from the $3n+1$ conjecture! $(+1)$ :D $\endgroup$ – Feeds Apr 11 at 11:48
  • $\begingroup$ Clarification needed: is the final question "what is the sum of all the natural numbers that are a distance of 61 from 1?", or does this mean "how many natural numbers are a distance of 61 from 1?" $\endgroup$ – Hugh Apr 11 at 21:03
  • $\begingroup$ It's asking how many (count) $\endgroup$ – Kradec na kysmet Apr 12 at 6:57
9
$\begingroup$

I don't know if this is strictly a puzzle but more of a computational programming exercise.

Many people on this site will already be familiar with the iterative function in the set-up to this problem as that from the famous Collatz conjecture. As you would expect, much research has been conducted into the properties of this function and there is even an entry on OEIS which describes the number of numbers that are exactly $n$ steps away from $1$, see here.

The value for $61$ is not listed here but they do give functions in a few different languages to obtain the number of steps for arbitrary $n$, and, saying that, it's not terribly difficult to write one yourself, for which the result is

$$1040490$$

Some other interesting things

This is a nice graph from Wikipedia showing the numbers which are within $20$ steps of $1$: enter image description here Also, the general pattern of the sequence tends to settle into exponential growth with ratio between adjacent terms thought to approach $\frac{3 + \sqrt{21}}{6}$, which is something I didn't know before.

$\endgroup$
  • $\begingroup$ The link you shared is for just 3*x + 1 $\endgroup$ – Kradec na kysmet Apr 11 at 11:51
  • 2
    $\begingroup$ @Kradecnakysmet It's sometimes called the "3x+1" problem but the set-up is as you've described. $\endgroup$ – hexomino Apr 11 at 11:53
  • $\begingroup$ How did you count it so fast, is there formula for it ? $\endgroup$ – Kradec na kysmet Apr 11 at 12:23
  • $\begingroup$ Here's one interesting way to look at this issue: once you hit 2^X, you are X steps away from 1. The only way to get to 1 is to be at 2, then 4, etc. So, really your somewhat random walk ends on any power of 2. $\endgroup$ – Jim Apr 11 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.