A059905 Index of first half of decomposition of integers into pairs based on A000695.

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

Offset: 0

Author

Marc LeBrun, Feb 07 2001

Keywords

• easy
• nonn
• look

Comments

One coordinate of a recursive non-self-intersecting walk on the square lattice Z^2.

Examples

			A000695(a(14)) + 2*A000695(A059906(14)) = A000695(2) + 2*A000695(3) = 4 + 2*5 = 14.
If n=27, then b_0=1, b_1=1, b_2=0, b_3=1, b_4=1. Therefore a(27) = b_0 + b_2*2 + b_4*2^2 = 5. - _Vladimir Shevelev_, Nov 13 2008
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..8192
• G. M. Morton, A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, IBM, 1966, with a(n) being section 5.1 step (c).
• Index entries for sequences related to coordinates of 2D curves

Crossrefs

Cf. A000695, A030308, A059906, A057300, A077957.

Programs

Maple

f:= proc(n) local L; L:= convert(n,base,2); add(L[2*i+1]*2^i,i=0..floor((nops(L)-1)/2)) end;
map(f, [$0..256]); # Robert Israel, Aug 12 2015

Mathematica

a[n_] := Module[{P}, (P = Partition[IntegerDigits[2n, 2]//Reverse, 2][[All, 2]]).(2^(Range[Length[P]]-1))]; Array[a, 100, 0] (* Jean-François Alcover, Apr 24 2019 *)

PARI

A059905(n) = { my(t=1,s=0); while(n>0, s += (n%2)*t; n \= 4; t *= 2); (s); }; \\ Antti Karttunen, Apr 14 2018

Python

def a(n): return sum([(n>>2*i&1)<Indranil Ghosh, Jun 25 2017, after Ruby code by Peter Kagey

Python

def A059905(n): return int(bin(n)[:1:-2][::-1],2) # Chai Wah Wu, Jun 30 2022

Ruby

def a(n)
  (0..n.bit_length/2).to_a.map { |i| (n >> 2 * i & 1) << i}.reduce(:+)
end # Peter Kagey, Aug 12 2015

Formula

n = A000695(a(n)) + 2*A000695(A059906(n)).

To get a(n), write n as Sum b_j*2^j, then a(n) = Sum b_(2j)*2^j. - Vladimir Shevelev, Nov 13 2008

a(n) = Sum_{k>=0} A030308(n,k)*A077957(k). - Philippe Deléham, Oct 18 2011

G.f.: (1-x)^(-1) * Sum_{j>=0} 2^j*x^(2^j)/(1+x^(2^j)). - Robert Israel, Aug 12 2015

a(n) = A059906(2*n). - Velin Yanev, Dec 01 2016