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.
LINKS
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))
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Jan 31 2021
STATUS
approved