A061313 -id:A061313 - cp's OEIS frontend

A008687 Number of 1's in 2's complement representation of -n.

0, 1, 1, 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

Offset: 0

R. H. Hardin

a(A127904(n)) = n and a(m) < n for m < A127904(n). - Reinhard Zumkeller, Feb 05 2007
a(n) = A000120(A010078(n)), n>0; a(n) = A023416(A004754(n-1)), n>1. - Reinhard Zumkeller, Dec 04 2015
Conjecture: a(n)+1 is the length of the Hirzebruch (negative) continued fraction for the Stern-Brocot tree fraction A007305(n)/A007306(n). - Andrey Zabolotskiy, Apr 17 2020
Terms a(n); n >= 2 can be generated recursively, as follows. Let S(0) = {1}, then for k >=1, let S(k) = {S(k-1)+1, S(k-1)}, where +1 means +1 on every term of S(k-1); see Example. Each step of the recursion gives the next 2^k terms of the sequence. - David James Sycamore, Jul 15 2024

			Using the above recursion for a(n); n >= 2, we have:
 S(0) = {1} so a(2) = 1;
 S(1) = {2,1} so a(3,4) = 2,1;
 S(2) = {3,2,2,1}, so a(5,6,7,8) = 3,2,2,1;
As irregular table the sequence for n >= 2 begins:
  1;
  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,3,3,4,3,3,2,5,4,4,3,4,3,3,2,4,3,3,2,3,2,2,1;
and so on (the k-th row contains 2^k terms; k>=0). - _David James Sycamore_, Jul 15 2024

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Michael Gilleland, Some Self-Similar Integer Sequences
Wikipedia, Two's complement

This is Guy Steele's sequence GS(4, 3) (see A135416).
Cf. A000120, A004754, A010078, A023416, A290251.
Cf. A007305, A007306, A061313, A088696.

a008687 n = a008687_list !! n
a008687_list = 0 : 1 : c [1] where c (e:es) = e : c (es ++ [e+1,e])
-- Reinhard Zumkeller, Mar 07 2011

a[0] = 0; a[1] = 1; a[n_] := a[n] = Mod[n,2] + a[Mod[n,2] + Floor[n/2]]; Array[a, 96, 0] (* Jean-François Alcover, Aug 12 2017, after Reinhard Zumkeller *)

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

a(n) = A023416(n-1) + 1.
a(n) = if n<=1 then n else (n mod 2) + a((n mod 2) + floor(n/2)). - Reinhard Zumkeller, Feb 05 2007
a(n) = if n<2 then n else a(ceiling(n/2)) + n mod 2. - Reinhard Zumkeller, Jul 25 2006
Min{m: a(m)=n} = if n>0 then A083318(n-1) else 0. - Reinhard Zumkeller, Jul 25 2006

A056791 Weight of binary expansion of n + length of binary expansion of n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Sep 01 2000

			12 = 1100 in binary, so a(12)=2+4=6.

Michael De Vlieger, Table of n, a(n) for n = 0..16384
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
Index to sequences related to the complexity of n

Equals A056792 + 1.
Equals A014701 + 2.
Cf. A061313, A037861.

Table[If[n==0,1,s=IntegerDigits[n,2];Total@s+Length@s],{n,0,100}] (* Giorgos Kalogeropoulos, Sep 13 2021 *)

a(n) = if (n==0, 1, my(b=binary(n)); vecsum(b) + #b); \\ Michel Marcus, Sep 13 2021

def a(n): b = bin(n)[2:]; return b.count('1') + len(b)
print([a(n) for n in range(87)]) # Michael S. Branicky, Sep 13 2021

a(n) = a((n - n mod 2) / (2 - n mod 2)) + 1 for n>0, a(0)=1. - Reinhard Zumkeller, Jul 29 2002

a(2n) = a(n)+1, a(2n+1) = a(n)+2. G.f.: 1 + 1/(1-x) * sum(k>=0, (2t+t^2)/(1+t), t=x^2^k). For n>0, a(n) = 2*A000120(n) + A080791(n) = A000120(n) + A029837(n). - Ralf Stephan, Jun 14 2003

More terms from James Sellers, Sep 06 2000 and from David W. Wilson, Sep 07 2000

A119477 a(1)=1, a(n) = a((n+1)/2) + 2 if n is odd, a(n) = a(n/2) + 1 if n is even.

Original entry on oeis.org

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

Offset: 1

Zak Seidov, May 22 2006

nonn

Cf. A061313, A119476.

a[1]=1;a[n_]:=a[n]=If[OddQ[n],a[(n+1)/2]+2,a[n/2]+1]; Table[a[n],{n,300}]

a(n) = A061313(n) + 1. - Philippe Deléham, Nov 03 2008

A261723 Interleave 2^n + 2 and 2^n + 1.

Original entry on oeis.org

4, 3, 6, 5, 10, 9, 18, 17, 34, 33, 66, 65, 130, 129, 258, 257, 514, 513, 1026, 1025, 2050, 2049, 4098, 4097, 8194, 8193, 16386, 16385, 32770, 32769, 65538, 65537, 131074, 131073, 262146, 262145, 524290, 524289, 1048578, 1048577, 2097154, 2097153, 4194306, 4194305, 8388610, 8388609

Offset: 1

Alonso del Arte, Aug 29 2015

There is only one fundamental difference between the x + 1 problem and the 3x + 1 problem, that being one of definition: if x is odd, then the next value is x + 1 rather than 3x + 1. But there are also important differences between the two problems, such as that with the x + 1 problem it is easy to prove that every positive integer x reaches 1 after a finite number of iterations.
As with the 3x + 1 problem, the minimum necessary number of iterations is obvious: given an arbitrary positive n, it will take at least floor(log_2(n)) iterations to reach 1, especially if n is a power of 2 to begin with.
But with the x + 1 problem, it is almost as easy to determine the maximum number of iterations needed to reach 1: 2*ceiling(log_2(n)). This is the case when n is one of the odd numbers in this sequence, in which case there are no consecutive halving steps prior to reaching 4.
If an initial 1 and 2 are added to this sequence, the complete x + 1 trajectory of any number in this sequence can be obtained by reading backwards from that number.
A061313(n) = number of steps to reach 1 when starting with n. - Reinhard Zumkeller, Sep 05 2015

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (0,3,0,-2).

Cf. A000051, A052548, A061313.

a261723 n = a261723_list !! (n-1)
a261723_list = concat $ transpose [tail a052548_list, tail a000051_list]
-- Reinhard Zumkeller, Sep 05 2015

&cat[[2^n+2, 2^n+1]: n in [1..30]]; // Vincenzo Librandi, Aug 31 2015

A261723:=n->(2^((n+1)/2)+2)*(1-(-1)^n)/2+(2^(n/2)+1)*(1+(-1)^n)/2: seq(A261723(n), n=1..60); # Wesley Ivan Hurt, Sep 06 2015

Flatten[Table[{2^n + 2, 2^n + 1}, {n, 25}]]

Vec(-x*(4*x^3+6*x^2-3*x-4)/((x-1)*(x+1)*(2*x^2-1)) + O(x^100)) \\ Colin Barker, Aug 31 2015

a(2n - 1) = 2^n + 2, a(2n) = 2^n + 1.
a(1) = 4, a(2n) = 2a(n - 1), a(2n + 1) = a(n - 1) - 1.
a(1) = 4, a(n) = a(n - 1) - 1 if a(n - 1) is even, a(n) = 2a(n - 1) if a(n - 1) is odd.
a(n) = 3*a(n-2) - 2*a(n-4) for n > 4. - Colin Barker, Aug 31 2015
G.f.: -x*(4*x^3+6*x^2-3*x-4) / ((x-1)*(x+1)*(2*x^2-1)). - Colin Barker, Aug 31 2015
a(n) = (2^((n+1)/2)+2)*(1-(-1)^n)/2+(2^(n/2)+1)*(1+(-1)^n)/2. - Wesley Ivan Hurt, Sep 06 2015
E.g.f.: sqrt(2)*sinh(sqrt(2)*x) + cosh(sqrt(2)*x) + 2*sinh(x) + cosh(x) - 2. - Robert Israel, Sep 06 2015

Two incorrect terms corrected by Colin Barker, Aug 31 2015

A080816 Triangle read by rows in which n-th row gives trajectory of n (omitting n itself) under the map k -> k+1 if k odd, k -> k/2 if k even.

Original entry on oeis.org

1, 4, 2, 1, 2, 1, 6, 3, 4, 2, 1, 3, 4, 2, 1, 8, 4, 2, 1, 4, 2, 1, 10, 5, 6, 3, 4, 2, 1, 5, 6, 3, 4, 2, 1, 12, 6, 3, 4, 2, 1, 6, 3, 4, 2, 1, 14, 7, 8, 4, 2, 1, 7, 8, 4, 2, 1, 16, 8, 4, 2, 1, 8, 4, 2, 1, 18, 9, 10, 5, 6, 3, 4, 2, 1, 9, 10, 5, 6, 3, 4, 2, 1, 20, 10, 5, 6, 3, 4, 2, 1, 10, 5, 6, 3, 4, 2, 1, 22

Offset: 1

Cino Hilliard, Mar 26 2003

			7 -> 8 -> 4 -> 2 -> 1, so the 7th row is 8,4,2,1.

Cino Hilliard, The x+1 conjecture

Cf. A061313 (row lengths).

Table[Rest[NestWhileList[If[OddQ[#],#+1,#/2]&,n,#>1&]],{n,30}] //Flatten (* Harvey P. Dale, Dec 04 2016 *)

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

A308431 For any Gaussian integer z, let f(z) = z / (1+i) when z is a multiple of 1+i and f(z) = z+1 otherwise (where i denotes the imaginary unit). a(n) gives the number of iterations of the map f, starting with n, needed to reach a cycle.

Original entry on oeis.org

0, 2, 1, 6, 5, 9, 8, 11, 10, 10, 9, 12, 11, 14, 13, 11, 10, 15, 14, 12, 11, 14, 13, 18, 17, 15, 14, 19, 18, 21, 20, 10, 9, 22, 21, 11, 10, 13, 12, 17, 16, 14, 13, 18, 17, 20, 19, 15, 14, 21, 20, 16, 15, 18, 17, 21, 20, 19, 18, 22, 21, 24, 23, 14, 13, 25, 24

Offset: 0

Rémy Sigrist, May 26 2019

nonn

Iterating the map f always ends in one of the following cycles: (0) or (-i, -i+1).
We can build a variant of this sequence by replacing the constant 1+i appearing in the name by any Gaussian integer, say d, such that gcd(Re(d), Im(d)) = 1 and norm(d) > 1.
This sequence has similarities with A061313.

			For n = 4:
- 4 is a multiple of 1+i, hence f(4) = 4/(1+i) = 2-2*i,
- 2-2*i is a multiple of 1+i, hence f(2-2*i) = (2-2*i)/(1+i) = -2*i,
- -2*i is a multiple of 1+i, hence f(-2*i) = -2*i/(1+i) = -1-i,
- -1-i is a multiple of 1+i, hence f(-1-i) = (-1-i)/(1+i) = -1,
- -1 is not multiple of 1+i, hence f(-1) = -1+1 = 0,
- 0 belongs to the cycle (0), hence a(4) = 5.

Cf. A061313.

a(z) = for (k=0, oo, if (z==0||z==-I||z==-I+1, return (k), if ((real(z)+imag(z))%2, z++, z/=(1+I))))

A080821 Primes in the accumulated tally of steps in the x+1 problem: Repeat until 1 is reached: if x is even divide by 2, otherwise add 1.

Original entry on oeis.org

11, 19, 29, 41, 83, 113, 167, 173, 199, 307, 367, 383, 463, 487, 521, 607, 617, 691, 701, 769, 809, 881, 929, 967, 977, 1423, 1567, 1579, 1627, 1753, 2029, 2063, 2087, 2207, 2239, 2251, 2297, 2341, 2383, 2393, 2467, 2477, 2579, 2657, 2789, 2833, 3001, 3533

Offset: 1

Cino Hilliard, Mar 26 2003

Sum of reciprocals for the x+1 problem is around 0.318.
Sum of reciprocals for the 3x+1 problem is around 0.1116.
The number of steps for the x+1 problem starting at n is A061313(n). The partial sums of A061313 are the sequence 0, 1, 4, 6, 11, 15, 19, 22, 29, 35, 41, ... Selecting the primes from these builds the current sequence. - R. J. Mathar, Feb 01 2008

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

cp's OEIS Frontend

A008687 Number of 1's in 2's complement representation of -n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

A056791 Weight of binary expansion of n + length of binary expansion of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A119477 a(1)=1, a(n) = a((n+1)/2) + 2 if n is odd, a(n) = a(n/2) + 1 if n is even.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A261723 Interleave 2^n + 2 and 2^n + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A080816 Triangle read by rows in which n-th row gives trajectory of n (omitting n itself) under the map k -> k+1 if k odd, k -> k/2 if k even.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A308431 For any Gaussian integer z, let f(z) = z / (1+i) when z is a multiple of 1+i and f(z) = z+1 otherwise (where i denotes the imaginary unit). a(n) gives the number of iterations of the map f, starting with n, needed to reach a cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A080821 Primes in the accumulated tally of steps in the x+1 problem: Repeat until 1 is reached: if x is even divide by 2, otherwise add 1.

Views

Author

Keywords

Comments

Programs

PARI