A008687 -id:A008687 - cp's OEIS frontend

A061313 Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2.

0, 1, 3, 2, 5, 4, 4, 3, 7, 6, 6, 5, 6, 5, 5, 4, 9, 8, 8, 7, 8, 7, 7, 6, 8, 7, 7, 6, 7, 6, 6, 5, 11, 10, 10, 9, 10, 9, 9, 8, 10, 9, 9, 8, 9, 8, 8, 7, 10, 9, 9, 8, 9, 8, 8, 7, 9, 8, 8, 7, 8, 7, 7, 6, 13, 12, 12, 11, 12, 11, 11, 10, 12, 11, 11, 10, 11, 10, 10, 9, 12, 11, 11, 10, 11, 10, 10, 9, 11, 10

Offset: 1

Henry Bottomley, Jun 06 2001

Also number of steps to get from n to 1 by process of adding 1 if odd, or dividing by 2 if even.
It is straightforward to prove that the number n appears F(n) times in this sequence, where F(n) is the n-th Fibonacci number (A000045). - Gary Gordon, May 31 2019
Conjecture: a(n)+2 is the sum of the terms of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - Andrey Zabolotskiy, Apr 17 2020

			a(2) = 1 since 2 = 1*2, a(3) = 3 since 3 = 1*2*2-1, a(11) = 6 since 11 = (1*2*2-1)*2*2-1.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Index to sequences related to the complexity of n

Cf. A056792, A006577, A029837, A000045.

Cf. A007305, A007306, A008687.

a061313 n = fst $ until ((== 1) . snd) (\(u, v) -> (u + 1, f v)) (0, n)
   where f n = if r == 0 then n' else n + 1  where (n', r) = divMod n 2
-- Reinhard Zumkeller, Sep 05 2015

f[n_] := Block[{c = 0, m = n}, While[m != 1, If[ EvenQ[m], While[ EvenQ[m], m = m/2; c++ ], m++; c++ ]]; Return[c]]; Table[f[n], {n, 1, 100}]

a(n)=if(n<2,0,s=n; c=1; while((s+s%2)/(2-s%2)>1,s=(s+s%2)/(2-s%2); c++); c)

xpcount(n) = { p = 1; for(x=1,n, p1 = x; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1; ct++) ); print1(ct, ", ") ) }

a(n) = if(n--,2*(logint(n,2)+1)) - hammingweight(n); \\ Kevin Ryde, Oct 21 2021

a(2n) = a(n)+1; a(2n+1) = a(n+1)+2; a(1) = 0.
Is Sum_{k=1..n} a(k) asymptotic to C*n*log(n) where 3 > C > 2? - Benoit Cloitre, Aug 31 2002
G.f.: x/(1-x) * Sum_{k>=0} (x^2^k + x^2^(k+1)/(1+x^2^k)). - Ralf Stephan, Jun 14 2003
a(n) = A080791(n-1) + A029837(n). - Ralf Stephan, Jun 14 2003
a(n) = 2*A023416(n-1) + A000120(n-1) = A023416(A062880(n)) = A023416(A000695(n)) + 1. - Ralf Stephan, Jul 16 2003
a(n) = A119477(n) - 1. - Philippe Deléham, Nov 03 2008

A290253 Triangle read by rows. Row n consists of the parts, ordered nonincreasingly, of the integer partition having viabin number n.

Original entry on oeis.org

0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 3, 1, 2, 2, 2, 3, 2, 3, 3, 4, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 2, 1, 3, 2, 1, 3, 3, 1, 4, 1, 2, 2, 2, 2, 3, 2, 2, 3, 3, 2, 4, 2, 3, 3, 3, 4, 3, 4, 4, 5, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 3, 1, 1, 1, 2, 2, 2, 1, 1, 3, 2, 1, 1, 3, 3, 1, 1, 4, 1, 1, 2, 2, 2, 2, 1, 3, 2, 2, 1, 3, 3, 2, 1, 4, 2, 1, 3, 3, 3, 1, 4, 3, 1, 4, 4, 1, 5, 1, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2

Offset: 0

Emeric Deutsch, Aug 23 2017

The viabin number of an integer partition is defined in the following way. Consider the southeast border of the Ferrers board of the integer partition and consider the binary number obtained by replacing each east step with 1 and each north step, except the last one, with 0. The corresponding decimal form is, by definition, the viabin number of the given integer partition. "Viabin" is coined from "via binary". For example, consider the integer partition [2,2,2,1]. The southeast border of its Ferrers board yields 10100, leading to the viabin number 20.
Number of entries in row n is A290251(n).
In the Maple program the command vitopart(n) yields the integer partition having viabin number n.

			Row 25 is 3,2,2. Indeed, the binary form of 25 is 11001. Consequently, the southeast border of the Ferrers board of the associated partition is EENNEN, where E and N are the steps [1,0] and [0,1], respectively. This leads to the partition [3,2,2].
Triangle begins:
0,
1;
1,1;
2;
1,1,1;
2,1;
2,2;
3;

Alois P. Heinz, Rows n = 0..4095, flattened

Row sums give A161511.
Row lengths give A008687(n+1).
Cf. A253563, A290251.

# (due to W. Edwin Clark)
vitopart := proc (n) local L, i, j, N, p, t; N := 2*n; L := ListTools:-Reverse(convert(N, base, 2)); j := 0; for i to nops(L) do if L[i] = 0 then j := j+1; p[j] := numboccur(L[1 .. i], 1) end if end do; sort([seq(p[t], t = 1 .. j)], `>=`) end proc:
# second Maple program:
T:= proc(n) local m; m:= n; [0]; while m>0 do `if`(1=
      irem(m, 2, 'm'), map(x-> x+1, %), [%[], 0]) od: %[]
    end:
seq(T(n), n=0..50);  # Alois P. Heinz, Aug 23 2017

T[n_] := Module[{L = IntegerDigits[2n, 2], j = 0, p}, Do[If[L[[i]] == 0, j++; p[j] = Count[L[[;;i]], 1]], {i, 1, Length[L]}]; Array[p, j] // Reverse];
Table[T[n], {n, 0, 50}] // Flatten (* Jean-François Alcover, Aug 06 2024, after W. Edwin Clark *)

A010078 Shortest representation of -n in 2's-complement format.

Original entry on oeis.org

1, 2, 5, 4, 11, 10, 9, 8, 23, 22, 21, 20, 19, 18, 17, 16, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 191, 190, 189

Offset: 1

Leonid Broukhis

			In binary:
  a(   1_2) =    1_2,
  a(  10_2) =   10_2,
  a( 011_2) =  101_2,
  a( 100_2) =  100_2,
  a(0101_2) = 1011_2,
  a(0110_2) = 1010_2,
  a(0111_2) = 1001_2,
  a(1000_2) = 1000_2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..8192
R. Stephan, Some divide-and-conquer sequences ...
R. Stephan, Table of generating functions

Cf. A004754 (terms sorted), A008687 (binary weight).

a010078 = x . subtract 1 where
   x m = if m == 0 then 1 else 2 * x m' + 1 - b
            where (m',b) = divMod m 2
-- Reinhard Zumkeller, Feb 21 2014

Array[2^(Ceiling[Log2[#] + 1]) - # &, 67] (* Michael De Vlieger, Oct 15 2018 *)

a(n) = if(n--, bitneg(n,2+logint(n,2)), 1); \\ Kevin Ryde, Apr 14 2021

a(n) = 2^(ceiling(log_2(n)+1)) - n.
a(n) = b(n-1), where b(n) = 1 if n = 0, otherwise 2*b(floor(n/2)) + 1 - n mod 2. - Reinhard Zumkeller, Feb 19 2003
G.f.: (x/(1-x)) * (1/x + Sum_{k>=0} 2^k*(x^2^k + 2x^2^(k+1))/(1+x^2^k)). - Ralf Stephan, Jun 15 2003
a(1) = 1; for n > 1, a(2n-1) = 2*a(n) + 1; for n >= 1, a(2n) = 2*a(n). - Philippe Deléham, Feb 29 2004

A080801 Similar to A080799 but count only addition steps.

Original entry on oeis.org

2, 1, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1, 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2, 6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4

Offset: 1

Cino Hilliard, Mar 25 2003

Cino Hilliard, The x+1 conjecture

xpcount2(n,p) = { for(x=1,n, p1 = x; f=0; ct=0; while(p1>1, if(p1%2==0,p1/=2; ct++,p1 = p1*p+1;); if(p1==7, p2=7; if(p2%2==0,p2/=2,p2 = p2*p+1); if(p2 ==8 && p1 ==7,f=1) ); ); if(f,print1(ct" ")) ) }

a(n) = A008687(n+2) = A023416(n+1) + 1.

A259043 a(n) = if n < 10 then n else a(floor(n/10) + n mod 10) + n mod 10.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 5, 7, 9, 11, 13, 15, 17, 10, 2, 4, 6, 8, 10, 12, 14, 16, 9, 12, 3, 5, 7, 9, 11, 13, 15, 8, 11, 14, 4, 6, 8, 10, 12, 14, 7, 10, 13, 16, 5, 7, 9, 11, 13, 6, 9, 12, 15, 18, 6, 8, 10, 12, 5, 8, 11, 14, 17, 20, 7, 9, 11, 4, 7

Offset: 0

Reinhard Zumkeller, Jun 17 2015

a(A259046(n)) = n and a(m) != n for m < A259046(n).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000

Cf. A076314, A007953, A008687, A259046.

a259043 x = if x < 10 then x else a259043 (x' + d) + d
            where (x', d) = divMod x 10

a(n) = if (n<10, n, my(u=n%10); a(n\10 + u) + u); \\ Michel Marcus, Jan 23 2022

A303476 Square array T(n, k) read by antidiagonals, n > 0 and k > 0: T(n, k) is the number of distinct shuffles of the words corresponding to the binary representations of n and of k.

Original entry on oeis.org

1, 2, 2, 1, 2, 1, 3, 3, 3, 3, 2, 3, 1, 3, 2, 2, 4, 6, 6, 4, 2, 1, 3, 3, 3, 3, 3, 1, 4, 4, 3, 7, 7, 3, 4, 4, 3, 4, 1, 6, 4, 6, 1, 4, 3, 3, 6, 10, 10, 6, 6, 10, 10, 6, 3, 2, 4, 6, 4, 4, 3, 4, 4, 6, 4, 2, 3, 6, 6, 9, 11, 4, 4, 11, 9, 6, 6, 3, 2, 4, 3, 7, 8, 10, 1

Offset: 1

Rémy Sigrist, Apr 24 2018

A shuffle of two words is formed by interspersing their characters into a new word, keeping the characters of each word in order. Leading zeros are ignored.

			Array T(n, k) begins:
  n\k|   1   2   3   4   5   6   7   8   9  10  11  12
  ---+------------------------------------------------
    1|   1   2   1   3   2   2   1   4   3   3   2   3
    2|   2   2   3   3   4   3   4   4   6   4   6   4
    3|   1   3   1   6   3   3   1  10   6   6   3   6
    4|   3   3   6   3   7   6  10   4   9   7  13   6
    5|   2   4   3   7   4   6   4  11   8   8   6  10
    6|   2   3   3   6   6   3   4  10  12   7   9   6
    7|   1   4   1  10   4   4   1  20  10  10   4  10
    8|   4   4  10   4  11  10  20   4  13  11  24  10
    9|   3   6   6   9   8  12  10  13   9  15  14  18
   10|   3   4   6   7   8   7  10  11  15   8  14  11

Rémy Sigrist, C++ program for A303476

Cf. A008687, A193020.

T(n, k) = T(k, n).
T(n, n) = A193020(n).
Apparently T(n, 1) = A008687(n + 1).
T(2^i, 2^j) = 1 + max(i, j) for any i >=0 and j >= 0.
T(n, k) = 1 iff n = 2^i - 1 and k = 2^j - 1 for some i > 0 and j > 0.
T(2^i, 2^j - 1) = binomial(i + j, j) for any i >= 0 and j > 0.

cp's OEIS Frontend

A061313 Minimal number of steps to get from 1 to n by (a) subtracting 1 or (b) multiplying by 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

PARI

Formula

A290253 Triangle read by rows. Row n consists of the parts, ordered nonincreasingly, of the integer partition having viabin number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A010078 Shortest representation of -n in 2's-complement format.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A080801 Similar to A080799 but count only addition steps.

Views

Author

Keywords

Links

Programs

PARI

Formula

A259043 a(n) = if n < 10 then n else a(floor(n/10) + n mod 10) + n mod 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

PARI

A303476 Square array T(n, k) read by antidiagonals, n > 0 and k > 0: T(n, k) is the number of distinct shuffles of the words corresponding to the binary representations of n and of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula