A101279 a(1) = 1; a(2k) = a(k), a(2k+1) = k.

1, 1, 1, 1, 2, 1, 3, 1, 4, 2, 5, 1, 6, 3, 7, 1, 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15, 1, 16, 8, 17, 4, 18, 9, 19, 2, 20, 10, 21, 5, 22, 11, 23, 1, 24, 12, 25, 6, 26, 13, 27, 3, 28, 14, 29, 7, 30, 15, 31, 1, 32, 16, 33, 8, 34, 17, 35, 4, 36, 18, 37, 9, 38, 19, 39, 2, 40, 20, 41, 10

Offset: 1

Author

N. J. A. Sloane, May 22 2006; definition corrected May 23 2006

Keywords

• nonn

Comments

From Jeremy Gardiner, Mar 22 2015: (Start)

For n > 2 write n, n-1 in binary, then align bits from the left and take contiguous matching bits as a binary number.

For example:

n = 19 10011

n-1 = 18 10010

a(n) = 9 1001

Also arrange the positive integers as a binary tree rooted at 1 as shown:

1

|

2................../ \..................3

| |

4......../ \........5 6......../ \........7

/ \ / \ / \ / \

/ \ / \ / \ / \

/ \ / \ / \ / \

8 9 10 11 12 13 14 15

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

Each branch doubles the number above at the left fork or doubles and adds 1 at the right fork. Then for n > 2, a(n) is the greatest common ancestor of n and n-1, a(n) = gca(n,n-1).

(End)

From David James Sycamore, Mar 07 2023: (Start)

The following identical sequences, {b(n)} and {c(n)}, are the same as a(n+1) for n >= 1.

b(1) = 1, then reverse the conditions in Name: b(2k) = k, b(2k+1) = b(k).

c(1) = 1, then if c(n) is a first occurrence, c(n+1) = c(c(n)), else if c(n) has occurred previously, c(n+1) = n - c(n-1).

These are fractal sequences (b(2m+1) = c(2m+1), m >= 1, recovers the originals). Also {b(n)} and {c(n)} interleave A000027 with the present sequence.

(End)

Examples

			If n is a power of 2 then k=1.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A003602, A025480.

cf. A000027, A000079, A007283, A070939, A119387. - David James Sycamore, Mar 07 2023

Programs

Maple

a:=array(0..200); a[1]:=1; M:=200; for n from 2 to M do if n mod 2 = 1 then a[n]:=(n-1)/2; else a[n]:=a[n/2]; fi; od: [seq(a[n],n=1..M)];

Mathematica

a[1] = 1; a[n_] := a[n] = If[OddQ@n, (n - 1)/2, a[n/2]]; Array[a, 84] (* Robert G. Wilson v, May 23 2006 *)

PARI

a(n)=(n/2^valuation(n,2)-1)/2+if(n==2^valuation(n,2),1,0) /* Ralf Stephan, Aug 21 2013 */

Formula

a((n+1)/2) = A028310(n) if n is odd and a(n/2) = a(n) if n is even; thus this is a fractal sequence. - Robert G. Wilson v, May 23 2006; corrected by Clark Kimberling, Jul 07 2007

a(n) = A025480(n) + A036987(n) = (n/2^A007814(n) - 1)/2 + (n == 2^A007814(n)). - Ralf Stephan, Aug 21 2013

If n is a power of 2, A070939(a(n)) = 1, otherwise A070939(a(n)) = A119387(n-1).

Numbers m for which a(m) = 1 are A000079(m) and A007283(m), a(2^m + 1) = 2^(m-1); m >= 1. - David James Sycamore, Mar 07 2023