OFFSET
1,3
COMMENTS
In other words, number of steps to reach 1 starting from n and using the process: x -> x-1 if n is odd and x -> x/2 otherwise.
a(n) = number of 0's + twice number of 1's (disregarding the leading digit 1) in the binary expansion of n, i.e., A007088(n). - Lekraj Beedassy, May 28 2010
From Daniel Forgues, Jul 31 2012: (Start)
For the binary Fibonacci rabbits sequence (A036299) (cf. OEIS Wiki link below) we have the substitution/concatenation rule: a(n), n >= 3, may be obtained by the concatenation of a(n-1) and a(n-2), with a(1) = 0, a(2) = 1. Thus, using . (dot) as the concatenation operator, we have the recursive substitution/concatenation
a(n) = a(n-0)
a(n) = a(n-1).a(n-2)
a(n) = a(n-2).a(n-3).a(n-3).a(n-4)
a(n) = a(n-3).a(n-4).a(n-4).a(n-5).a(n-4).a(n-5).a(n-5).a(n-6)
which suggests the sequence
{0}
{1, 2}
{2, 3, 3, 4}
{3, 4, 4, 5, 4, 5, 5, 6}
whose concatenation gives A014701 (this sequence).
Number of multiplications to compute n-th power by the Chandah-sutra method, also called left-to-right binary exponentiation:
x^1 = x^( 1_2) = (x) (0 prod)
x^2 = x^( 10_2) = (x^2) (1 prod)
x^3 = x^( 11_2) = (x^2) * (x) (2 prod)
x^4 = x^( 100_2) = (x^2)^2 (2 prod)
x^5 = x^( 101_2) = (x^2)^2 * (x) (3 prod)
x^6 = x^( 110_2) = (x^2)^2 * (x^2) (3 prod)
x^7 = x^( 111_2) = (x^2)^2 * (x^2) * (x) (4 prod)
x^8 = x^(1000_2) = ((x^2)^2)^2 (3 prod) (End)
From Ya-Ping Lu, Mar 03 2021: (Start)
Index at which record m occurs is A052955(m).
First appearance of m in the sequence (or the record value m) is at n = 2^(m/2 + 1) - 1 for even m, and at n = 3*2^((m - 1)/2) - 1 for odd m.
The last appearance of m in the sequence is at n = 2^m. (End)
a(n) is the digit sum of n-1 in bijective base-2. Since the Fibonacci number F(m) can be defined as the number of ways to compose m as the sum of 1s and 2s, we get that m appears F(m) times in the sequence. - Oscar Cunningham, Apr 14 2024
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..16384 (first 1000 terms from T. D. Noe)
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, On the Salient Regularities of Strings of Assembly Theory, Preprints (2024). See pp. 12, 14.
C. K. Caldwell, The Prime Glossary, binary exponentiation
Hermann Gruber and Markus Holzer, Optimal Regular Expressions for Palindromes of Given Length, Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, Article No. 53, pp. 53:1-53:15, 2021.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From N. J. A. Sloane, Feb 03 2013
Szymon Łukaszyk and Wawrzyniec Bieniawski, Assembly Theory of Binary Messages (How to Assemble a Black Hole and Use it to Assemble New Binary Information?), Preprints (2024).
OEIS Wiki, Binary Fibonacci rabbits sequence
FORMULA
a(n) = floor(log_2(n)) + (number of 1's in binary representation of n) - 1. - Corrected (- 1 at end) by Daniel Forgues, Aug 01 2012
a(2^n) = n, a(2^n-1) = 2*(n-1), and for n >= 2, log_2(n) <= a(n) <= 2*log_2(n) - 1. - Robert FERREOL, Oct 01 2014
Let u(1) = 1, u(2*n) = u(n)+1, u(2*n+1) = u(2*n)+1; then a(1) = 0 and a(n) = u(n-1). - Benoit Cloitre, Dec 19 2002
G.f.: -2/(1-x) + (1/(1-x)) * Sum_{k>=0} (2*x^2^k + x^2^(k+1))/(1+x^2^k). - Ralf Stephan, Aug 15 2003
From {0}, apply the substitution rule (n -> n+1, n+2) repeatedly, giving {{0}, {1, 2}, {2, 3, 3, 4}, {3, 4, 4, 5, 4, 5, 5, 6}, ...} and concatenate. - Daniel Forgues, Jul 31 2012
a(n) >= A003313(n). - Charles R Greathouse IV, Jan 03 2018
a(n) = a(floor(n/2)) + 1 + (n mod 2) for n > 1. - Pablo Hueso Merino, Oct 28 2020
a(n+1) = max_{1<=i<=n} (H(i) + H(n-i)) where H(n) denotes the Hamming weight of n (A000120(n)). See Lemma 8 in Gruber/Holzer 2021 article. - Hermann Gruber, Jun 26 2024
EXAMPLE
5 -> 4 -> 2 -> 1 so 3 steps are needed to reach 1 hence a(5)=3; 9 -> 8 -> 4 -> 2 -> 1 hence a(9)=4.
MAPLE
A014701 := proc(n) local j, k; j := n; k := 0; while(j>1) do if j mod 2=1 then j := j-1 else j := j/2 fi; k := k+1 od end;
# second Maple program:
a:= n-> add(i+1, i=Bits[Split](n))-2:
seq(a(n), n=1..128); # Alois P. Heinz, Aug 30 2021
MATHEMATICA
a[n_] := DigitCount[n, 2] /. {x_, y_} -> 2x + y - 2; Array[a, 100] (* Robert G. Wilson v, Jul 31 2012 *)
PROG
(Haskell)
a014701 1 = 0
a014701 n = a007953 $ a007931 (n - 1)
-- Reinhard Zumkeller, Oct 26 2012
(PARI) a(n)=hammingweight(n)+logint(n, 2)-1 \\ Charles R Greathouse IV, Dec 29 2016
(Python)
def a(n):
if n==1:
return 0
return a(n//2)+1+n%2
for i in range(1, 60):
print(a(i), end=", ")
# Pablo Hueso Merino, Oct 28 2020
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
James Kilfiger (jamesk(AT)maths.warwick.ac.uk)
STATUS
approved