A080791 -id:A080791 - cp's OEIS frontend

A068052 Start from 1, shift one left and sum mod 2 (bitwise-XOR) to get 3 (11 in binary), then shift two steps left and XOR to get 15 (1111 in binary), then three steps and XOR to get 119 (1110111 in binary), then four steps and so on.

1, 3, 15, 119, 1799, 59367, 3743271, 481693095, 123123509927, 62989418816679, 64491023022979239, 132015402419352060071, 540829047855347718631591, 4430403202865824763042320551, 72583450474242118015031400337575, 2378466805556971511916001231449723047

Offset: 0

Antti Karttunen, Feb 13 2002

a(n) = each row of A053632 reduced mod 2 and interpreted as a binary number.

Antti Karttunen, Table of n, a(n) for n = 0..64

Same sequence shown in binary: A068053.

Cf. A000120, A003987, A028362 (using + instead of XOR), A048675, A053632, A080791, A248663, A285101, A285102, A285103, A285105.

with(gfun,seriestolist); [seq(foo(map(`mod`,seriestolist(series(mul(1+(z^i),i=1..n),z,binomial(n+1,2)+1)),2)), n=0..20)];
foo := proc(a) local i; add(a[i]*2^(i-1),i=1..nops(a)); end;
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1,
      (t-> Bits[Xor](2^n*t, t))(a(n-1)))
    end:
seq(a(n), n=0..16);  # Alois P. Heinz, Mar 07 2024

FoldList[BitXor[#, #*#2]&, 1, 2^Range[20]] (* Paolo Xausa, Mar 07 2024 *)

a(n) = if(n<1, 1, bitxor(a(n - 1), 2^n*a(n - 1))); \\ Indranil Ghosh, Apr 15 2017, after formula by Antti Karttunen

a(0) = 1; for n > 0, a(n) = a(n-1) XOR (2^n)*a(n-1), where XOR is bitwise-XOR (A003987).
a(n) = A248663(A285101(n)) = A048675(A285102(n)).
A000120(a(n)) = A285103(n). [Number of ones in binary representation.]
A080791(a(n)) = A285105(n). [Number of nonleading zeros.]

Formulas added by Antti Karttunen, Apr 15 2017

A372516 Number of ones minus number of zeros in the binary expansion of the n-th prime number.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, May 13 2024

sign

Absolute value is A177718.

			The binary expansion of 83 is (1,0,1,0,0,1,1), and 83 is the 23rd prime, so a(23) = 4 - 3 = 1.

The sum instead of difference is A035100, firsts A372684 (primes A104080).
The negative version is A037861(A000040(n)).
Restriction of A145037 to the primes.
The unsigned version is A177718.
- Positions of zeros are A177796, indices of the primes A066196.
- Positions of positive terms are indices of the primes A095070.
- Positions of negative terms are indices of the primes A095071.
- Positions of negative ones are A372539, indices of the primes A095072.
- Positions of ones are A372538, indices of the primes A095073.
- Positions of nonnegative terms are indices of the primes A095074.
- Positions of nonpositive terms are indices of the primes A095075.
A000120 counts ones in binary expansion (binary weight), zeros A080791.
A030190 gives binary expansion, reversed A030308.
A035103 counts zeros in binary expansion of primes, firsts A372474.
A048793 lists binary indices, reverse A272020, sum A029931.
A070939 gives length of binary expansion.
A101211 lists run-lengths in binary expansion, row-lengths A069010.
A372471 lists the binary indices of each prime.
Cf. A000043, A003714, A005940, A059305, A061712, A066195, A071814, A211997, A372429, A372517, A372686.

Table[DigitCount[Prime[n],2,1]-DigitCount[Prime[n],2,0],{n,100}]
DigitCount[#,2,1]-DigitCount[#,2,0]&/@Prime[Range[100]] (* Harvey P. Dale, May 09 2025 *)

a(n) = A000120(A000040(n)) - A080791(A000040(n)).
a(n) = A014499(n) - A035103(n).
a(n) = A145037(A000040(n))

A252735 a(1) = 0; for n > 1: a(2n) = a(n), a(2n+1) = 1 + a(A064989(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 21 2014

nonn

Consider the binary tree illustrated in A005940: If we start from any n, computing successive iterations of A252463 until 1 is reached (i.e., we are traversing level by level towards the root of the tree, starting from that vertex of the tree where n is located at), a(n) gives the number of odd numbers > 1 encountered on the path (i.e., excluding the final 1 from the count but including the starting n if it was odd).

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Essentially one less than A061395.
Cf. A252464, A252736.
Cf. A000120, A005940, A064989, A080791, A156552, A243071, A252462, A252464, A252736.
Cf. also A246369.

a252735[n_] := Prepend[Rest@Array[PrimePi[FactorInteger[#][[-1]][[1]]] - 1 &, n], 0]; a252735[108] (* Michael De Vlieger, Dec 21 2014, after Stefan Steinerberger at A061395 *)

a(1) = 0; for n > 1: a(2n) = a(n), a(2n+1) =  1 + a(A064989(n)).
a(n) = A080791(A156552(n)). [Number of nonleading 0-bits in A156552(n).]
Other identities:
For all n >= 2:
a(n) = A061395(n) - 1.
a(n) = A000120(A243071(n)) - 1. [One less than the binary weight of A243071(n).]
a(n) = A252464(n) - A252736(n) - 1.

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

Original entry on oeis.org

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

A252736 a(1) = a(2) = 0; for n > 2: a(2n) = 1 + a(n), a(2n+1) = a(A064989(2n+1)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Dec 21 2014

nonn

Consider the binary tree illustrated in A005940: If we start from any n, computing successive iterations of A252463 until 1 is reached (i.e., we are traversing level by level towards the root of the tree, starting from that vertex of the tree where n is located), a(n) gives the number of even numbers > 2 encountered on the path (i.e., excluding the 2 from the count but including the starting n if it was even).

The number of pairs in any factorization tree of n. For example, a possible factorization tree of 12 is 12 -> (4*3) -> (2*2)*3. There are 2 pairs in this factor tree: (4*3) and (2*2). Thus, a(12) - 1 = 3 - 1 = 2. - Melvin Peralta, Aug 29 2016

Antti Karttunen, Table of n, a(n) for n = 1..8192

Essentially one less than A001222.
Cf. A000120, A005940, A064989, A080791, A156552, A243071, A252464, A252735.
Cf. also A246370.

a[1] = a[2] = 0; a[n_] := a[n] = If[EvenQ@ n, 1 + a[n/2], a[Times @@ Power[Which[# == 1, 1, # == 2, 1, True, NextPrime[#, -1]] & /@ First@ #, Last@ #] &@ Transpose@ FactorInteger@ n]]; Array[a, 120] (* Michael De Vlieger, Aug 30 2016 *)

a(1) = a(2) = 0; for n > 2: a(2n) = 1 + a(n), a(2n+1) =  a(A064989(2n+1)).
a(n) = A080791(A243071(n)). [Number of nonleading 0-bits in A243071(n).]
Other identities. For all n >= 2:
a(n) = A000120(A156552(n)) - 1. [One less than the binary weight of A156552(n).]
a(n) = A252464(n) - A252735(n) - 1.
a(n) = A001222(n) - 1.

A257510 Number of nonleading zeros in factorial base representation of n (A007623).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Apr 27 2015

Sequence starts from n=1, because 0 is an ambiguous case.

Antti Karttunen, Table of n, a(n) for n = 1..10080

Cf. A227157 (numbers n such that a(n) = 0), A227187 (n for which a(n) > 0).
Cf. A007623, A060130, A084558, A230403.
Cf. also A257511.
Cf. also A023416, A080791 (analogous sequences for base-2), A055641 (for base-10).

factBaseIntDs[n_] := Module[{m, i, len, dList, currDigit}, i = 1; While[n > i!, i++]; m = n; len = i; dList = Table[0, {len}]; Do[currDigit = 0; While[m >= j!, m = m - j!; currDigit++]; dList[[len - j + 1]] = currDigit, {j, i, 1, -1}]; If[dList[[1]] == 0, dList = Drop[dList, 1]]; dList]; s = Table[FromDigits[factBaseIntDs[n]], {n, 120}]; Last@ DigitCount[#] & /@ s (* Michael De Vlieger, Apr 27 2015, after Alonso del Arte at A007623 *)

(define (A257510 n) (let loop ((n n) (i 2) (s 0)) (cond ((zero? n) s) (else (loop (floor->exact (/ n i)) (+ 1 i) (+ s (if (zero? (modulo n i)) 1 0)))))))

a(n) = A084558(n) - A060130(n).
Other identities and observations:
For all n >= 0, a(A000142(n+1)) = n. [(n+1)! gives the position where n first appears.]
For all n, a(n) >= A230403(n).

A092339 Number of adjacent identical digits in the binary representation of n.

Original entry on oeis.org

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

Offset: 0

Ralf Stephan, Mar 18 2004

In binary: number of 00 blocks plus number of 11 blocks. (Note: the blocks can overlap. See the example below.)

			60 in binary is 111100, it has 4 blocks of adjacent digits, so a(60)=4.
Equally, 60's binary Gray code expansion is A003188(60)=34, 100010 in binary, which contains four zeros.

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 84.

Cf. A005811.

a(n)=local(v); v=binary(n); sum(k=1, length(v)-1, v[k]==v[k+1])

a(n)=if(n<1,0,if(n%2==0,a(n/2)+(n>0&&(n/2)%2==0),a((n-1)/2)+((n-1)/2)%2))

(define (A092339 n) (A080791 (A003188 n))) ;; Antti Karttunen, Jul 05 2013

Recurrence: a(2n) = a(n) + [n even], a(2n+1) = a(n) + [n odd].
a(n) = A014081(n) + A056973(n).
For n>0, A227185(n) = a(n)+1.
a(n) = A080791(A003188(n)) [because the sequence gives the number of nonleading zeros in binary Gray code expansion of n] - Antti Karttunen, Jul 05 2013

A108730 Triangle read by rows: row n gives the list of the number of zeros following each 1 in the binary representation of n.

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Jun 22 2005

This is probably the simplest method for putting the nonnegative integers into one-to-one correspondence with the finite sequences of nonnegative integers and is the standard ordering for such sequences in this database.
This sequence contains every finite sequence of nonnegative integers.
This can be regarded as a table in two ways: with each weak composition as a row, or with the weak compositions of each integer as a row. The first way has A000120 as row lengths and A080791 as row sums; the second has A001792 as row lengths and A001787 as row sums. - Franklin T. Adams-Watters, Nov 06 2006
Concatenate the base-two positive integers (A030190 less the initial zero). Left to right and disallowing leading zeros, reorganize the digits into the smallest possible numbers. These will be the base-two powers-of-two of A108730. - Hans Havermann, Nov 14 2009
T(2^(n-1),0) = n-1 and T(m,k) < n-1 for all m < 2^n, k <= A000120(m). When the triangle is seen as a flattened list, each n occurs first at position n*2^(n-1)+1, cf. A005183. - Reinhard Zumkeller, Feb 26 2012
Equals A066099-1, elementwise. - Andrey Zabolotskiy, May 18 2018

			Triangle begins:
  0
  1
  0,0
  2
  1,0
  0,1
  0,0,0
  3
For example, 25 = 11001_2; following the 1's are 0, 2 and 0 zeros, so row 25 is 0, 2, 0.

Franklin T. Adams-Watters, Table of n, a(n) for n = 1..5120 (through 10 bit numbers)

Cf. A066099 (main entry for compositions), A007088, A000120, A080791, A001792, A001787, A124735.

import Data.List (unfoldr, group)
a108730 n k = a108730_tabf !! (n-1) !! (k-1)
a108730_row = f . group . reverse . unfoldr
   (\x -> if x == 0 then Nothing else Just $ swap $ divMod x 2) where
   f [] = []
   f [os] = replicate (length os) 0
   f (os:zs:dss) = replicate (length os - 1) 0 ++ [length zs] ++ f dss
a108730_tabf = map a108730_row [1..]
a108730_list = concat a108730_tabf
-- Reinhard Zumkeller, Feb 26 2012

row[n_] := (id = IntegerDigits[n, 2]; sp = Split[id]; f[run_List] := If[First[run] == 0, run, Sequence @@ Table[{}, {Length[run] - 1}]]; len = Length /@ f /@ sp; If[Last[id] == 0, len, Append[len, 0]]); Flatten[ Table[row[n], {n, 1, 41}]] (* Jean-François Alcover, Jul 13 2012 *)

row(n)=my(v=vector(hammingweight(n)),t=n); for(i=0,#v-1,v[#v-i] = valuation(t,2); t>>=v[#v-i]+1); v \\ Charles R Greathouse IV, Sep 14 2015

Edited by Franklin T. Adams-Watters, Nov 06 2006

A120511 a(n) = min{j>0 : A006949(j) = n}.

Original entry on oeis.org

1, 3, 6, 7, 11, 12, 14, 15, 20, 21, 23, 24, 27, 28, 30, 31, 37, 38, 40, 41, 44, 45, 47, 48, 52, 53, 55, 56, 59, 60, 62, 63, 70, 71, 73, 74, 77, 78, 80, 81, 85, 86, 88, 89, 92, 93, 95, 96, 101, 102, 104, 105, 108, 109, 111, 112, 116, 117, 119, 120, 123, 124, 126, 127, 135

Offset: 1

Frank Ruskey and Chris Deugau (deugaucj(AT)uvic.ca), Jun 20 2006

nonn

Antti Karttunen, Table of n, a(n) for n = 1..10000
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences
C. Deugau and F. Ruskey, Complete k-ary Trees and Generalized Meta-Fibonacci Sequences, J. Integer Seq., Vol. 12. [This is a later version than that in the GenMetaFib.html link]
B. Jackson and F. Ruskey, Meta-Fibonacci Sequences, Binary Trees and Extremal Compact Codes, Electronic Journal of Combinatorics, 13 (2006), R26.
Index entries for sequences related to binary expansion of n

Cf. A006949, A120522, A007814, A023416, A036987, A080791, A005408.
a(n) = one less than A233273(n-1).
Cf. A241218.

import Data.List (elemIndex); import Data.Maybe (fromJust)
a120511 = (+ 1) . fromJust . (`elemIndex` (tail a006949_list))
-- Reinhard Zumkeller, Apr 17 2014

p := proc(n)
if n=1 then return 1; end if;
for j from p(n-1)+1 to infinity do
if A006949(j) = n then return j; fi; od;
end proc;

a[n_] := 2 n - 1 + DigitCount[2 n - 1, 2, 0]; Array[a, 100] (* Jean-François Alcover, Feb 01 2018, after Reinhard Zumkeller *)

{ A120511(n) = local(t,k); t=binary(n); k=valuation(n,2); 2*n + #t - sum(i=1,#t,t[i]) - k - (n==2^k) } /* Max Alekseyev, Sep 18 2009 */

(define (A120511 n) (+ n n (A080791 n) (- (A007814 n)) (- (A036987 (- n 1)))))
(define (A120511 n) (+ (A005408 (- n 1)) (A080791 (- n 1))))
;; Based on above PARI-program and its further reduction, from Antti Karttunen, Dec 12 2013

G.f.: P(z) = (z/(1-z)) * (1 + Sum_{k=0..ceiling(n/2)} z^(2^m) * (1 + 1/(1 - z^(2^m)))).
It appears that a(n) = a(ceiling(n/2)) + n. - Georgi Guninski, Sep 08 2009
From Max Alekseyev, Sep 08 2009: (Start)
This can be proved as follows. Let b=A006949. It is known that b(n) = b(n-1-b(n-1)) + b(n-2-b(n-2)) and b(n-1) <= b(n) <= b(n-1)+1.
The following claims are trivial:
Claim 1. For any n, b(a(n))=n.
Claim 2. If m=a(n) for some n, then a(b(m))=m.
Claim 3. Let m=a(n). Then b(m)=n and b(m-1)=n-1, implying that b(m+1) = b(m-b(m)) + b(m-1-b(m-1)) = 2*b(m-n) is an even number.
Claim 4. Each even number in A006949 is repeated at least two times while each odd number in A006949 appears only once.
Proof. If n is even, then for m=a(n), we have b(m)=n and b(m+1)=n (from Claim 3), i.e., n is repeated at least twice. If n is odd, then for m=a(n), we cannot have b(m+1)=n since by Claim 3 b(m+1) must be even. QED
Consider two cases:
1) If n is odd, then b(m+1) = n+1 = 2*b(m-n), i.e., b(m-n) = (n+1)/2. Claim 4 also implies b(m-2) = n-1. Therefore n = b(m) = b(m-1-b(m-1)) + b(m-2-b(m-2)) = b(m-n) + b(m-n-1). Since n is odd, we have b(m-n-1) < b(m-n) and thus a(b(m-n)) = m-n.
2) If n is even, then b(m+1) = n = 2*b(m-n), i.e., b(m-n) = n/2. Claim 4 also implies b(m-3) = b(m-2) = n-2. Therefore n-1 = b(m-1) = b(m-2-b(m-2)) + b(m-3-b(m-3)) = b(m-n) + b(m-n-1). Since n-1 is odd, we have b(m-n-1) < b(m-n) and thus a(b(m-n)) = m-n.
Combining these two cases, we have b(m-n) = ceiling(n/2) and furthermore m-n = a(b(m-n)) = a(ceiling(n/2)) or a(n) = a(ceiling(n/2)) + n.
QED
This implies explicit formulas for both sequences.
Let z(n) be the number of zero bits in the binary representation of n. Then
A120511(n) = 2n + z(n) - k - [n==2^k], where k = valuation(n,2), i.e., the maximum power of 2 dividing n.
Note that k <= z(n) <= log_2(n)-1, implying that 2n-1 <= A120511(n) <= 2n + log_2(n) - 1.
Since A006949(m) equals the largest n such that A120511(n) <= m (and thus A120511(n+1) > m), from 2n-1 <= A120511(n) <= m it follows that A006949(m) <= (m+1)/2. Similarly, from m < A120511(n+1) < 2(n+1) + log_2(n+1) - 1 <= 2(n+1) + log_2((m+1)/2+1) - 1, it follows that A006949(m) >= (m - log_2(m+3)) / 2. Therefore | A006949(m) - m/2 | <= log_2(m+3)/2, which gives an interval of just logarithmic length to search for the value of A006949(m).
(End)
From p. 25 of the revised version of the Deugau-Ruskey paper, we have p(n) = s*ceiling(log_k n) + (kn-d-1)/(k-1) where d is the sum of the digits of the k-ary expression of n-1. In the present case s = 1 and k = 2. - Frank Ruskey, Sep 11 2009
From Antti Karttunen, Dec 12 2013: (Start)
a(n) = 2n + A080791(n) - A007814(n) - A036987(n-1) [This is essentially Max Alekseyev's above formula represented with A-numbers].
a(n) = A005408(n-1) + A080791(n-1) = A233273(n-1) - 1. [The above formula reduces to this, because A080791(n) - A080791(n+1) = 1 - (A007814(n+1) + A036987(n)) and A080791(2n+1) = A080791(n).]
(End)
a(n) = 2*n - 1 + A023416(2*n-1). - Reinhard Zumkeller, Apr 17 2014

Edited by Max Alekseyev, Sep 16 2009

More terms from Max Alekseyev, Sep 18 2009

A253556 a(1) = 0; after which, a(2n) = a(n), a(2n+1) = 1 + a(A250470(n)).

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Jan 12 2015

nonn

Consider the binary tree illustrated in A252753 and A252755: If we start from any n, computing successive iterations of A253554 until 1 is reached (i.e., we are traversing level by level towards the root of the tree, starting from that vertex of the tree where n is located at), a(n) gives the number of odd numbers > 1 encountered on the path (i.e., excluding the final 1 from the count but including the starting n if it was odd).

Antti Karttunen, Table of n, a(n) for n = 1..8192

One less than A253558.
Powers of two, A000079, gives the positions of zeros.
Cf. A000120, A080791, A252753, A252754, A252755, A252756, A253554, A253555, A253557, A253559.
Differs from A252735 for the first time at n=21, where a(21) = 1, while A252735(21) = 3.

a(1) = 0; after which, a(2n) = a(n), a(2n+1) = 1 + a(A250470(n)).
a(n) = A253555(n) - A253557(n).
a(n) = A253558(n) - 1.
a(n) = A080791(A252754(n)). [Number of nonleading 0-bits in A252754(n).]
Other identities. For all n >= 2:
a(n) = A000120(A252756(n)) - 1. [One less than the binary weight of A252756(n).]

cp's OEIS Frontend

A068052 Start from 1, shift one left and sum mod 2 (bitwise-XOR) to get 3 (11 in binary), then shift two steps left and XOR to get 15 (1111 in binary), then three steps and XOR to get 119 (1110111 in binary), then four steps and so on.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A372516 Number of ones minus number of zeros in the binary expansion of the n-th prime number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A252735 a(1) = 0; for n > 1: a(2n) = a(n), a(2n+1) = 1 + a(A064989(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

A252736 a(1) = a(2) = 0; for n > 2: a(2n) = 1 + a(n), a(2n+1) = a(A064989(2n+1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A257510 Number of nonleading zeros in factorial base representation of n (A007623).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A092339 Number of adjacent identical digits in the binary representation of n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

PARI