|
|
A101279
|
|
a(1) = 1; a(2k) = a(k), a(2k+1) = k.
|
|
6
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
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)
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)
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
If n is a power of 2 then k=1.
|
|
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 *)
|
|
PROG
|
(PARI) a(n)=(n/2^valuation(n, 2)-1)/2+if(n==2^valuation(n, 2), 1, 0) /* Ralf Stephan, Aug 21 2013 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|