login
A340873
a(n) is the number of iterations of A245471 needed to reach 1 starting from n.
6
0, 1, 3, 2, 6, 4, 4, 3, 11, 7, 7, 5, 9, 5, 5, 4, 12, 12, 12, 8, 8, 8, 8, 6, 10, 10, 10, 6, 14, 6, 6, 5, 21, 13, 13, 13, 13, 13, 13, 9, 17, 9, 9, 9, 17, 9, 9, 7, 19, 11, 11, 11, 11, 11, 11, 7, 15, 15, 15, 7, 15, 7, 7, 6, 22, 22, 22, 14, 14, 14, 14, 14, 22, 14
OFFSET
1,3
COMMENTS
This sequence is well defined.
Sketch of proof:
- we focus on odd numbers n > 1,
- if the binary representation of n ends with k 0's and one 1:
in two steps we obtain a number with the same binary length as n
and ending with k-1 0's and one 1,
iterating again will eventually give a number ending with two or more 1's,
- if the binary representation of n ends with k 1's (k > 1):
in k+1 steps we obtain a number with a binary length strictly smaller
than that of n,
- so any odd number > 1 will eventually reach the number 1.
FORMULA
a(2*n) = a(n) + 1.
EXAMPLE
For n = 10:
- the trajectory of 10 is 10 -> 5 -> 14 -> 7 -> 8 -> 4 -> 2 -> 1,
- so a(10) = 7.
PROG
(PARI) a(n) = for (k=0, oo, if (n==1, return (k), n%2, n=bitxor(n, 2*n+1), n=n/2))
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Jan 31 2021
STATUS
approved